My Math Forum Collatz, a pigeonhole approach

 Number Theory Number Theory Math Forum

August 30th, 2014, 02:53 AM   #31
Senior Member

Joined: Mar 2012

Posts: 572
Thanks: 26

Quote:
 Originally Posted by CRGreathouse (There's a side problem where my Internet connection has been lost, and I'm forced to post from places other than home. This means I don't have access to PARI/GP or my other specialized software. Hopefully the situation will be repaired next week.)
Very frustrating for you. No rush at my end.

 August 30th, 2014, 06:16 AM #32 Global Moderator     Joined: Nov 2006 From: UTC -5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms Yes, very. In the meantime, would you check that my program is doing what you want? Otherwise the Inetnet plumbers could come and go without us being any further ahead than we are now.
August 31st, 2014, 12:44 PM   #33
Senior Member

Joined: Mar 2012

Posts: 572
Thanks: 26

Quote:
 Originally Posted by CRGreathouse Yes, very. In the meantime, would you check that my program is doing what you want? Otherwise the Inetnet plumbers could come and go without us being any further ahead than we are now.
I've had a go at a geometrical proof of this particular point here, which I think works?

Prime Numbers: Attempted proof

Bear in mind I'm only addressing the narrow point of whether the outputs from the function tend towards 1 in 2 (for level 1 numbers), 1 in 6 (for level 2 numbers) etc. And I'll acknowledge upfront that an error of even 1 is insufficient if we are attempting a 'counting' proof, but what I'm looking to discuss in the end is whether we could use this method in a different way that could lead to a reductio ad absurdum given the assumption that the conjecture is false.

Last edited by Hedge; August 31st, 2014 at 12:51 PM.

September 1st, 2014, 01:05 AM   #34
Senior Member

Joined: Mar 2012

Posts: 572
Thanks: 26

Quote:
 Originally Posted by Hedge However, I would argue that it is stronger than a Poisson/binomial process since there is so much dependence and modular structure within the levels, meaning that the estimate is at least based on highly predictable frequencies, rather than independent probabilities.
Quote:
 Originally Posted by CRGreathouse I assume that you can't prove this.
Just to explain, the previous quote was a response to this...

September 6th, 2014, 06:11 AM   #35
Senior Member

Joined: Mar 2012

Posts: 572
Thanks: 26

I said I'd look at the code

Quote:
 Originally Posted by CRGreathouse Code: f(p)={ my(n=log(p)\log(2)+1,q=2^n-p,t); t=sum(i=0,#binary(q),if(bittest(q,i),q-=2^i;3^hammingweight(q)*2^i,0)); (2^n-t)/3^hammingweight(2^n-p) };
So far as I can see this bit (above) is right but lacks the restriction to q < 2^n/4

Quote:
 Originally Posted by CRGreathouse Here's the code I'm using: [code]ok(p)={ my(n=log(p)\log(2)+1,N=2^n,q=N-p,t,r); if(N/4<=q&&q0 };
Then you added the restriction above, which looks like it ought to work but there was a glitch that you noticed:

Quote:
 Originally Posted by CRGreathouse looks like I forgot to check ok(k) in one place
Then, sorry but I can't work out what the last bit below does, which doesn't mean there is anything wrong with it, just that I can't follow the language well enough.

Quote:
 Originally Posted by CRGreathouse Code: cc(n)=my(v=List());while(n>1,listput(v,n);n=3*n+1;n>>=valuation(n,2));Set(v); showcc(n)={ while(n>1, print1(n" -> "); n=3*n+1; n>>=valuation(n,2) ); print(1) }; bad(n,v)={ forstep(k=1,n-2,2, my(t=cc(k),u=setintersect(t,v)); if(#u, showcc(k);v=setminus(v,u)) ); showcc(n) }; v=[];forstep(n=1,1e6,2,if(ok(n),t1=setintersect(t=cc(n),v);if(#t1&&t1!=[5],bad(n,t1);print);v=Set(concat(v,t))))
Having said that, I now think there's a limit to the point of running this. While I was doing this attempted proof Prime Numbers: Attempted proof I realised a couple of things.

Firstly it convinced me that the proportion of level n integer outputs from the function do indeed tend up or down to 1 in 2(3^n)/3. (If you don't read it, the main point is that the function involves dividing by 3^n at level n. Every prime power (except powers of 2) has a primitive root; thus the multiplicative group of integers modulo 3n is cyclic. Thus we can arrange the level n inputs as a square/cube/cuboid grid that is cyclic every 2(3^n)/3 places - it's a bit more complicated as the pattern doesn't start out as a cuboid, but it tends to a pattern that can be filled with an increasing proportion of cuboids...)

Secondly it became more clear that the region over which this happens is pretty vast. 100 million < 2^21 and at this point the level 3 numbers are only just starting to tend down from about 1 in 19 towards 1 in 18 outputs. And for level 2 numbers we've tended down from 1 in 7 to 1 in 6.001 at about 2^6000. So running tests over 100 million or so wouldn't tell us a huge amount.

Last edited by Hedge; September 6th, 2014 at 06:29 AM.

 Tags approach, collatz, pigeonhole

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post hiddenphi1 Applied Math 1 July 14th, 2014 11:56 AM merlin2222 Algebra 2 June 27th, 2011 02:27 PM deadlyned Number Theory 1 March 12th, 2011 01:34 PM mathdigger Applied Math 0 October 9th, 2010 12:55 AM wulfgarpro Algebra 17 March 22nd, 2010 04:13 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top