2.10.16

Largest Power of 2

Recently, I showed a formula for finding an odd integer n = 5k + 2 based on another odd integer k such that  3k + 1 = 2i where i is the largest power of 2 such that  2i < n. I called k a Collatz exit point and n a Collatz trap.


It turns out that the largest power i of 2 such that 2i <  n for any odd integer n is involved in many other interesting theorems and I'm very much tempted to give it a special definition but I shall refrain from doing so until I prove more of the theorems associated with it.

Theorem: If n is an odd integer and i is the largest power of 2 such that 2i <  n  then
 2i+1 (mod n) = 2i - r for some integer r such that r = n - 2i 

Proof: If n is an odd integer then n can be represented as n = 2i + r for some integer r such that 2i-1 < r < 2i

Since n = 2i + r then 2i = (n - r) and also since 2i+1 (mod n) =  2*2i (mod n) then 2i+1 (mod n) =  2*(n - r) (mod n)

Clearly, since 2i-1 < r < 2i  then 2*(n - r) < 2*n so

 2i+1 (mod n) = 2*(n - r) (mod n)= 2*(n - r) - n = ( 2*2i ) - n = ( 2*2i )- (2i + r) = 2i+2i - 2i - r = 2i - r .'.

Example: Let n = 35, then the largest power i of 2 mod 35 such that 2i <  35  is i = 5 since 25 = 32 and 32 is congruent to 32 (mod 35) so no modular arithmetic is needed to compute this power.

However, for all i > 6 then 2> 35 and so modular arithmetic will be needed to compute such powers unless of course I use the method I described here and its improved version here, which generate all powers of 2 mod n without using modular arithmetic, multiplication, or exponentiation.

If I'm only interested in the value of 2mod 35 then by the theorem above 2i+1 mod n = 2mod 35 = 32 - (35 - 32) = 29

This is obviously insignificant but it is still interesting because computing 2i+1 will not exceed n using this formula.