Sunday, 20 May 2018

elementary number theory - Expression for the highest power of 2 dividing 3aleft(2b1right)1


Question: I am wondering if an expression exists for the highest power of 2 that divides 3a(2b1)1, in terms of a and b, or perhaps a more general expression for the highest power of 2 dividing some even n?




EDIT: This is equivalent to finding an expression for the highest power of 2 dividing some even n, however finding it in terms of a and b may make it more useful for what I have described below.







Motivation For Asking:






The reason for this particular question is because, having had a look at the Collatz conjecture, I have found that positive odd integers n of the form 2a(2b1)1 will iterate to the even value of 3a(2b1)1 after a iterations of 3n12, then being divided by the highest power of 2 dividing it. Since I have also found that numbers of the form (23)c(23c1(2d1)+1)1 become powers of 2 after c iterations, I am hoping to find an expression for the number of iterations for n to become a power of 2, and hence reach the 4-2-1 loop.






Updates:







EDIT 1: I have found a post on mathoverflow at https://mathoverflow.net/questions/29828/greatest-power-of-two-dividing-an-integer giving a rather long expression for the highest power of 2 dividing any odd positive integer n which may be useful.






EDIT 2: Here is an image displaying patterns I find quite interesting. It is from a program I wrote which displays the exponent of the highest power of 2 dividing each value of 3a(2b1)1, represented by lighter pixels for higher values and darker pixels for lower values. It is plotted on a 2d grid such that each pixel on the x-axis represents the b value, starting from one, and the same for a on the y-axis:



enter image description here




This seems to suggest that if a and b are both either odd or even, the highest power of 2 dividing 3a(2b1)1 is 2 (I am currently having a look at this further).






EDIT 3: Defining 2bs as the highest power of 2 dividing 1.5as(ns+1)1, I know that any odd ns=2as(2xs1)1 will reach:



ns+1=2as+1(2xs+11)1=3as(2xs1)12bs=1.5as(ns+1)12bs



This has led me to find an expression for the zth iteration, Tz(n1), starting from some odd n1, of:




T(ns)=1.5as(ns+1)12bs=ns+1



The expression I found is as follows:



Tz(n1)=1.5zc=2ac(1.5a1(n1+1)1)2zd=1bd+1.5az12bz+z1e=21.5zf=e+1af(1.5ae1)2zg=ebg



Hence, for the Collatz conjecture to be true:



Tz(n1)=1.5zc=2ac(1.5a1(n1+1)1)2zd=1bd+1.5az12bz+z1e=21.5zf=e+1af(1.5ae1)2zg=ebg=1




must have a unique solution for any odd n1 such that {z,a1...z,b1...zN+}



This raises a separate question - namely what can be said of as+1 and bs+1 from the values of as and bs? If there turns out to be some connection, the values of zi=1ai and zi=1bi may be expressed simply in terms of a1 and b1, hence turning the problem into a (diophantine equation? I have not yet studied Mathematics beyond secondary school, so I am unsure of correct Mathematical terminology or notation - please feel free to correct me).






EDIT 4: As suggested by Gottfried Helms, when 3a(2b1)1 is written as 3ab(3a+1), factoring out the highest power of 2 shows that for ab(mod2), the highest power of 2 dividing 3a(2b1)1 is 2, and for a1(mod2) where b0(mod4), or a0(mod2) where b3(mod4) it must be 4. In other cases it seems to be no longer dependant on a or b and becomes pseudo-random. This helps to explain the patterns found above, but not all of them.




No comments:

Post a Comment

real analysis - How to find limhrightarrow0fracsin(ha)h

How to find lim without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...