gistfile1.txt

Powers of Two


Assume: http://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic

Assume: No power of two is divisible by three.
Assume: In any three sequential integers, exactly one is divisible by three.

Even powers of two are congruent to 3 mod 1. Proof:

Let n be even in x = 2**n. Then m*2 = n and x = 4**m = 2**2**m = (2**m)**2, so x is a square (the square of 2**m).

Since x is a square, x - 1 can be rewritten as (2**m)**2 - 1**2 and the difference-of-squares factoring applies:
(2**m)**2 - 1**2 = (2**m - 1)(2**m + 1)

Because 2**m - 1, 2**m, and 2**m + 1 are a sequence of integers, exactly one of them is divisible by three. Since 2**m cannot be divisible by three (because it is a power of two), one of the others is, and thus x - 1 is divisible by three.

Therefore, x is congruent to 3 mod 1.

Odd powers of two are congruent to 3 mod 2. Consider: Multiply an even power of two by two. x % 3 = 1 -> 2*x % 3 = 2.


3x + 1


Assume: Adjacent integers are coprime. Example proof: http://foolproof.pbworks.com/w/page/8978149/Two Adjacent Integers Are Coprime

Consider: forall x, if x is even, then x' = x / 2 exists. x' is divisible by three iff x is divisible by three.

forall x, x' = 3*x + 1 cannot be divisible by three.
Proof: 3*x must be divisible by three. x' is adjacent to 3*x. Therefore, x' cannot be divisible by three.