Collatz Conjecture: No Cycle: A One-Page Proof

Update Aug 2, 2010:  Step #7 is wrong.  I have found an error in my argument which invalidates the proof. 

 This is meant to be a one-page proof based on my longer argument that I posted before. This one-pager attempts to show that there cannot be a cycle in a Collatz Sequence that does not include 1.

Claim: A Collatz Sequence does not have cycles that do not include 1.

1. Assume that a Collatz sequence has a cycle of length n.

2. If we only consider the odd integers in this sequence, we can characterize this sequence by two sets of positive integers:

x₀, x₁, ..., x_n

p₁, p₂, ..., p_n

where for each x_i:

x_i = (1/2^p_i)*(3x_i-1 + 1)

so, from the above, we can see the following:

(a) Each x_i is odd

(b) x₀ = x_n [since it is a cycle of length n]

Further, we can also see that x₁ = x_n+1, ..., x_n-1 = x_2n-1

(c) Each p_i ≥ 1 [since x_i-1 is odd, it follows that 3x_i-1 + 1 is even.]

3. Since the purpose is to show that all cycles must include 1, I will assume that each x_i ≥ 3 and show that this leads to a contradiction.

4. I can show that p₁ + ... + p_n is less than 2n. [see Corollary 9.2, here for the argument]

5. This gives us an interesting relationship, it means that:

This follows directly from step #4. Assume that this wasn't true.

Let a = # of 1's
Let b = # of 2's
Let c = # of p_i that are greater than 2.
Let d = sum of (p_i - 2) for all p_i ≥ 3

So, we have: 2n = 2a + 2b + 2c

If we assume the relationship above is not true, then d ≥ a.

Now, using our definitions above:

p₁ + p₂ + ... + p_n = a + 2b + 2c + d

But if d ≥ a, then it follows that p₁ + p₂ + ... + p_n = 2n which goes against step #4.

6. I can also show that for each p_i = 1, a value in the cycle that corresponds to p_i+n-1 which for purposes of this proof, I will call "p_i+n-1" [each p_i must repeat since each x_i after x₀ will itself form a cycle of length n].

7. For every p_i = 1, p_j = 1 where i ≠ j, it follows that abs(p_i+n-1 - p_j+n-1) ≥ 3. [See Corollary 12.3, Theorem 13, and Corollary 13.1, here]

8. The result in step #7 gives us the following relationship:

Let a = the number of p_i that are equal to 1

sum(p_i ≥ 3 - 2) = (1 - 1) + (1 + 3 - 2) + (1 + 3 + 3 - 2) + ... + (1 + [a-1]*3 - [a-1]*2)

where each term in the parentheses is one of the p_i+n-1 values that must be 3 greater than all others p_j+n-1 values. The first term is (1-1) because 1 of these values can be 1 and we are not counting it since it is not greater than 2.

Using the summation formula, where: 1 + 2 + 3 + ... + (a-1) = (1/2)(a-1)(a), we get the following value for the sum:

sum(p_i ≥3 - 2) = (a-1)*1 + (1/2)(a-1)(a)*3 - (a-1)*2

9. Combining step #5 and step #8, gives us:

Let a = the number of p_i that are equal to 1

Then:

(a-1) ≥ (a-1)*1 + (1/2)(a-1)(a)*3 - (a-1)*2

But this is only true if a ≤ 1. [See Theorem 16, here, for my reasoning about the above equation]

10. Here lies the contradiction because I can further show that there are at least two p_i that are equal to 1. [see Corollary 11.1, here]

QED

Collatz Conjecture: No Cycles

Update (Aug 2, 2010):  Lemma 12 is wrong.  I do not believe that it can be corrected.  This invalidates the argument.


Definition 1:  Collatz Sequence of Odd Integers

By collatz sequence of odd integers, I mean the integers  x₀, x₁, x₂... and the integers p₁, p₂, ... such that:

x₀ = any odd integer greater than 1.

and:

where p_i is the largest positive integer such that x_i is a positive odd integer.


Lemma 1:  In a Collatz Sequence of Odd Integers, any x_i  where i ≥ 1 has the following relationship to x₀:

Proof:

(1)  The case for i=1 comes directly from Definition 1 above:

(2)  Assume that it is true up to some i ≥ 1 so that:

(3)  From Definition 1 above, we have: 

 



(4)  Combining step #2 with step #3 gives us:

QED
 

Definition 2:  A Collatz Cycle

By collatz cycle, I mean any collatz sequence of odd integers x₀, ..., x_n where:

x_i ≥ 3

x_n = x₀

n ≥ 1

and n is the length of the cycle.


Lemma 2:  If x₀, ..., x_n is a collatz cycle, then n ≥ 2

Proof:

(1)  From Definition 1 above, we have:

(2)  Assume that the length of the cycle is n=1.

(3)  Then from step #1, we have the following:

which gives us:

and factors into:

(4)  But then x₀ = 1 which goes against our Definition 2 above since all x_i ≥ 3.

(5)  So, we reject our assumption in step #2.

QED


Lemma 3:  If x₀, ..., x_n is a collatz cycle, then:

Proof:

(1)  Using Lemma 1 above, we have:

where n is the length of the cycle.

which is the same as:

(2)  Multiplying both sides by:

gives us:

QED


Lemma 4:  If r is odd:

(a^r + 1)/(a + 1) = a^r-1 - a^r-2 + a^r-3 + ... -a¹ +  (-1)^r

Proof:

(1)  Let u =  a^r-1 - a^r-2 + a^r-3 + ... - a¹ + 1

Then we have:

a*u = a^r - a^r-1 + a^r-2 + ... + a

au + u =  u(a+1) = a^r + 1

(2)  This gives us finally that:

u = (a^r + 1)/(a+1)

QED

Lemma 5:   if a ≥ 2, b ≥ 2, and 2^a - 3^b is positive, then 2^a - 3^b ≥ 5

Proof:

(1)  Assume that 2^a - 3^b = 1

so that we have:

3^b + 1 = 2^a

(2) We can show that b is even since:

(a)  Assume that b is odd

(b)  Then using Lemma 4 above:

(3^b + 1)/(3 + 1) = 3^b-1 - 3^b-2 + ... - 3 + 1

(c)  Since b ≥ 2 and odd, b ≥ 3 and it follows that 3^b-1 + ...  - 3 + 1 is odd and greater than 1.

(d)  But this is impossible since it 2^a is not divisible by any odd integer greater than 1.

(e)  So we reject our assumption in step #2a.

(3)  Since b is even, there exists an integer t such that b=2t

(4)  Since 3^t is odd, it follows that there exists an integer m such that:

3^t = 2m + 1

(5)  So we have:

2^a = (3^t)² + 1 = (2m+1)² + 1 =  4m² + 4m + 2 =

(6)  But this is impossible since 4 divides 2^a (since a ≥ 2) but does not divide 4m² + 4m + 2.

(7)  So we reject our assumption in step #1.

(8)  So, we know that it cannot equal 1 from step #7 and we we know that it cannot equal 2 or 4 since even - odd = odd.

Finally, we know it cannot be divisible by 3 since 2^a is not divisible by 3 so that we have:

2^a - 3^b ≥ 5

QED

Lemma 6:  If x₀, ..., x_n is a collatz cycle, then n ≥ 3

Proof:

(1)  Assume that x₀, x₁, x₂ is a cycle of length 2.

(2)  Using Lemma 3 above, we have:

(2^{p₁ + p₂})x₀ = 3²x₀ + 3 + 2^p₁

which becomes:

(2^{p₁ + p₂} - 3²)x₀ = 3 + 2^p₁

(3)  Since 3 + 2^p₁ is positive and x₀ is positive, it follows that 2^{p₁ + p₂} - 3² must be positive.

(4)  The first power of 2 greater than 9 is 16 so that p₁ + p₂ ≥ 4.

(5)  We know that x₀ is not divisible by 3 since 2^p₁ is not divisible by 3.

(6)  Since x₀ is an odd integer greater than 1, it follows that x₀ ≥ 5

(7) Now, I will use induction to show that (2^{p₁ + p₂} - 3²)x₀ is greater than 3 + 2^p₁ since:

(a)  Assume that p₁ + p₂ = 4

(b) Since p₂ ≥ 1, it follows that p₁ ≤ 3.

(c)  So 3+2^p₁ ≤ 11

(d)  But from step #6 and step #4, (2^{p₁ + p₂} - 3²)x₀ ≥ 7*5 = 35

(e) Assume (2^{p₁ + p₂} - 3²)x₀ is greater than 3 + 2^p₁  up to some p₁ ≥ 3.

(f)  Since p₂ ≥ 1, it follows that 2^{p₁ + p₂}  is greater than 2^p₁

so that:

x₀*2^{p₁ + p₂} is greater than 2^p₁

and finally:

(2^{p₁ + p₂} - 3²)x₀ + x₀2^{p₁ + p₂} is greater than 3 + 2^p₁ + 2^p₁

(g)  Adding this all together, gives us:

x₀(2^{p₁ + p₂ + 1} - 3²) is greater than 3 + 2^{p₁ + 1} 

(8)  Since it is always greater, it cannot be equal.

QED


Lemma 7:  If x₀, ..., x_n is a collatz cycle and n ≥ 3, then the following n equations must hold:

Proof:

This follows directly from Lemma 3 above.  If x₀ is a cycle of length n, then so is x₁, x₂, and so on up until x_n-1.

Since each successor in a collatz sequence of odd integers is always the same given the same predecessor, it follows that if x₀ repeats at x_n, then x₁ repeats at x_n+1, etc. up to x_n-1 repeating at x_2n-1.

QED


Corollary 7.1:  For any collatz cycle of length n, it cannot be the case that all p_i have the same value.

Proof:

(1)  Assume that p₁ = p₂ = ... = p_n

(2)  Then from Lemma 7 above, it follows that x₀ = x₁ = ... = x_n-1

(3)  But this cannot be the case since we assumed that the cycle is of length n and has no repeats within n numbers.

(4)  So we reject our assumption in step #1.

QED


Lemma 8:  2²ⁿ - 3ⁿ = 3^n-1 + 3^n-2*2² + 3^n-3*2⁴ + ... + 3*2^2n-4 + 2^2n-2

Proof:

(1)  This is true for n=2 since:

2⁴ - 3² = 16 - 9 = 7

3¹ + 2² = 7

(2)  Assume that it is true up to some n ≥ 2 so that:

2²ⁿ - 3ⁿ = 3^n-1 + 3^n-2*2² + 3^n-3*2⁴ + ... + 3*2^2n-4 + 2^2n-2

(3)  Adding 3*2²ⁿ - 2*3ⁿ to both sides gives:

2²ⁿ - 3ⁿ + 3*2²ⁿ - 2*3ⁿ = 4*2²ⁿ - 3*3ⁿ = 2²ⁿ⁺² - 3ⁿ⁺¹

3^n-1 + 3^n-2*2² + 3^n-3*2⁴ + ... + 3*2^2n-4 + 2^2n-2 + 3*2²ⁿ - 2*3ⁿ =

= 3^n-1 + 3^n-2*2² + 3^n-3*2⁴ + ... + 3*2^2n-4 + 2^2n-2 + 2²ⁿ + 2*(2²ⁿ - 3ⁿ)

(4)  Again, using the assumption in step #2, we get:

3^n-1 + 3^n-2*2² + 3^n-3*2⁴ + ... + 3*2^2n-4 + 2^2n-2 + 2²ⁿ + 2*(2²ⁿ - 3ⁿ) =


=  3^n-1 + 3^n-2*2² + 3^n-3*2⁴ + ... + 3*2^2n-4 + 2^2n-2 + 2²ⁿ + (2*3^n-1 + 2*3^n-2*2² + 2*3^n-3*2⁴ + ... + 2*3*2^2n-4 + 2*2^2n-2) =

= 3*3^n-1 + 3*3^n-2*2² + 3*3^n-3*2⁴ + ... + 3*3*2^2n-4 + 3*2^2n-2 + 2²ⁿ =


= 3ⁿ + 3^n-1*2² + 3^n-2*2⁴ + ... + 3²*2^2n-4 + 3*2^2n-2 + 2²ⁿ

QED


Lemma 9: 

Let p₁, ..., p_n be any sequence of positive integers such that p₁ + ... + p_n = 2n

Then, there exists 1 ≤ i ≤ n such that:

if we shift the sequence left as needed such that we have:

p_i, p_i+1, ..., p_n, p₁, ..., p_i-1

then it follows that:

p_i ≤ 2

p_i + p_i+1 ≤ 4

...

and so on up until:

p_i + ... + p_i-2 ≤ 2n - 2

Proof:

(1)  This is clearly true if all p_i = 2, so assume that there is at least one non-two value in p₁, ..., p_n 

(2)  In the sequence p₁, ..., p_n, let us shift it until p₁ is a 1 or 2 and p_n is not.

This is the point right after we  have [p_i ≥ 3],  [p_i ≤ 2].

(3)  We can now group the integers in the following way:

Let S₁ be the initial sequence of positive integers equal to 1 or 2.

Let M₁ the integer ≥ 3 that follows S₁

Let S₂ be the sequence of integers that are equal to 1 or 2 that follow M₁   (Note: it is possible that S₂ is empty if M₁ is followed by an integer ≥ 3.)

Let M₂ be the integer ≥ 3 that follows S₂

and so on until we hit:

M_t which is the the integer that was shifted to p_n in step #2.

(4)  So, to be clear, we have grouped the integers into subsequences:

S₁, M₁, ..., S_t, M_t

where each S_i consists of 0 or more integers and each M_i consists of exactly 1 integer.

(5) Now, I define two functions:  n(), p() such that:

n(S_i) = (the number of 1's found in the sequence)

So n(S_i) = 0 if S_i is empty or all-twos.  If it contains two 1's, then n(S_i) = 2.

p(M_i) = M_i - 2.  So, if M_i = 5, p(M_i) = 3.

(6) So, from these definitions, since the sum = 2n, it clear that:

n(S₁) + n(S₂) + ... + n(S_t) = p(M₁) + ... + p(M_t)

NOTE:  If there were more 1's, then the sum would be less than 2n and if the sum of M₁ + ... + M_t were greater, then the sum would be more than 2n.

(7)  Now, I will show that there exists an S_i such that:

n(S_i) ≥ p(M_i)

and

n(S_i) + n(S_i+1) ≥ p(M_i) + p(M_i+1)

etc. all the way to up:

n(S_i) + n(S_i+1) + ... + n(S_t) + n(S₁) + ... + n(S_i-2) ≥ p(M_i) + p(M_i+1) + ... + p(M_t) + p(M₁) + ... + p(M_i-2)

(8)  We can assume that that not all the n(S_i) = p(M_i).  [If they did, then there is nothing that needs to be proved]

(9)  We can assume that there is at least one S_i such that n(S_i) is greater than p(M_i) since if this were not the case, then we would violate our observation in step #6 above.

(10)  Assume that S_i does not meet our assumption so that we eventually to get a c such that:

n(S_i) + n(S_i+1) + ... + n(S_i+c) is less than p(M_i) + p(M_i+1) + ... + p(M_i+c)

(11)  But in this case, there must be a S_j that is outside the sequence from S_i, M_i, ..., S_i+c, M_i+c that also has the property that n(S_j) is greater than p(M_j); otherwise we would have the situation where we violate our observation in step #6 above.

(12)  Now if S_j stops before it gets to S_i, then by the same argument it follows that there must be another S_k outside the already mentioned sequences where n(S_k)  is greater than p(M_k).  If S_k stops before S_i we can continue in this way ad infinitum so eventually, we must find a sequence S_u that is outside all the other sequences mentioned and:

n(S_u) is greater than p(M_u) and

n(S_u) + n(S_u+1) is greater than p(M_u) + p(M_u+1)

etc.

so based on our reasoning about S_i, we get:

n(S_u) + n(S_u+1) + ... + n(S_i) + ... + n(S_i+c-1) ≥ p(M_u) + p(M_u+1) + ... + p(M_i) + ... + p(M_i+c-1)

(13) Now, if this still stops at S_c, then there must exist another sequence S_v, etc.  So we can assume that eventually, it doesn't stop at all.

(14)  For purposes of this proof, let us label this first value S_i so that we have the following:

S_i, M_i, S_i+1, M_i+1, ..., S_t, M_t, S₁, M₁, ..., S_i-1, M_i-1

where:

n(S_i) ≥ p(M_i)

and:

n(S_i) + n(S_i+1) ≥ p(M_i) + p(M_i+1)

and so for the entire sequence.

(15)  We now shift p₁, ..., p_n such that we have:

p*₁ = the first integer in S_i
p*₂ = the second integer in S_i if it exists
...
p*_c = M_i
p*_c+1 = the first integer in S_i+1

etc.

(16)  It is clear that p*₁, p*₂, ... is a sequence is a left-shift from p₁, p₂, ... which satisfies the conditions of this proof.

QED


Corollary 9.1:   If x₀, ..., x_n is a collatz cycle and n ≥ 3, where:

then:


p₁ + ... + p_n  ≠ 2n.


Proof:

(1)  Assume that p₁ + ... + p_n = 2n

(2)  From Lemma 8 above, we know that:

2²ⁿ - 3ⁿ = 3^n-1 + 3^n-2*2² + 3^n-3*2⁴ + ... + 3*2^2n-4 + 2^2n-2

(3)  So that for all x_i, we have:

x_i(3^{n − 1} + 3^{n − 2}2² + ... + 3 * 2^{2n − 4} + 2^{2n − 2}) =

(4)  Since x_i ≥ 5, this only holds true if:

3^{n − 1} + 3^{n − 2}2² + ... + 3 * 2^{2n − 4} + 2^{2n − 2}  is less than

(5)  But from Lemma 9 above, it follows that for at least one x_i, this will not be the case.

(6)  Therefore, we reject our assumption in step #1.

QED


Corollary 9.2:  We can extend Corollary 9.1 so that we show that:


p₁ + ... + p_n is less than 2n.

Proof:

(1) Assume that there exists a cycle x₀, ..., x_n with n ≥ 3 and p₁ + ... + p_n greater than 2n.

(2) Then there exists c such that p₁ + ... + p_n - c = 2n

(3)  Let p*₁, p*₂, ... be values modified from p₁, ..., p_n such that p*₁ + ... + p*_n = 2n.

(4)  From Lemma 9 (and the reasoning in Corollary 9.1), we get a situation for some x_i where:

x_i(2^{p₁ + ... + p_n - c} - 3ⁿ) is greater than 3^n-1 + 3^n-22^p*_i + ... + 2^{p*_i + ... + p*_i+n-2}

(5)  Now it is clear from this equation that:

x_i*2^{p₁ + ... + p_n - c} is greater than  3^n-22^p*_i + ... + 2^{p*_i + ... + p*_i+n-2}

(6)  So it follows that:

x_i(2²ⁿ - 3ⁿ) + x_i*2²ⁿ is greater than 3^n-1 + 3^n-22^p*_i + ... + 2^{p*_i + ... + p*_i+n-2}  + 3^n-22^p*_i + ... + 2^{p*_i + ... + p*_i+n-2}

which means that:

x_i(2²ⁿ⁺¹ - 3ⁿ) is likewise necessarily greater than:

3^n-1 + 3^n-22^1+p*_i + ... + 2^{1+p*_i + ... + p*_i+n-2} 

(7)  We can repeat the same argument up to x_i(2^2n+c - 3ⁿ) so the proof is complete.

QED

Lemma 10.:  If p₁, ..., p_n represent the powers of 2 that make up a cycle, then p₁ + ... + p_n is greater than 1.5n.

Proof:

(1)  From  Lemma 7 above, we know that:

2^{p₁ + ... + p_n} - 3ⁿ ≥ 1

(2)  Let u = p₁ + ... + p_n

(3)  In order for step #1 to be true, it follows that p₁ + ... + p_n must be greater than 1.5*n  since:

2^u ≥ 3ⁿ if and only if  2^u ≥  log₂(3ⁿ) = n*log₂(3) which is greater than 1.5n.

QED


Lemma 11:

There exists a prime p such that:

p divides 2^{p₁ + ... + p_n} - 3ⁿ

and if x₀, ..., x_n-1 is a cycle of length n where:

x_i(2^{p₁ + ... + p_n} - 3ⁿ) = 3^n-1 + 3^n-2*2^p_i + ... + 3*2^{p_i + ... + p_i+n-3} + 2^{p_i + ... + p_i+n-2}

then, for any x_j, x_k:

p divides:

3^n-2(2^p_j - 2^p_k) + ... + 3(2^{p_j + ... + p_j+n-3} - 2^{p_k + ... + p_k+n-3}) + (2^{p_j + ... + p_j+n-2} - 2^{p_k + ... + p_k+n-2})

Proof:

(1) From Lemma 5 above, we know that:

2^{p₁ + ... + p_n} - 3ⁿ ≥ 5

(2)  Therefore, from the Fundamental Theorem of Arithmetic, it follows that there exists a prime p that divides it.

(3)  We also know that p ≠ 2 and p ≠ 3 since p divides 2^{p₁ + ... + p_n} - 3ⁿ

(4)  From Lemma 7 above, we know that for each of the n x_i in the cycle, it follows that:

x_i(2^{p₁ + ... + p_n} - 3ⁿ) = 3^n-1 + 3^n-2*2^p_i + ... + 3*2^{p_i + ... + p_i+n-3} + 2^{p_i + ... + p_i+n-2}

(5)  So, it follows that in each case p divides 3^n-1 + 3^n-2*2^p_i + ... + 3*2^{p_i + ... + p_i+n-3} + 2^{p_i + ... + p_i+n-2}.

(6) Which means that p also divides the subtraction of any two so that for any x_i, x_j  we have:

x_i(2^{p₁ + ... + p_n} - 3ⁿ) - x_j(2^{p₁ + ... + p_n} - 3ⁿ) = (x_i - x_j)(2^{p₁ + ... + p_n} - 3ⁿ) =

3^n-2(2^p_i - 2^p_j) + ... + 3(2^{p_i + ... + p_i+n-3} - 2^{p_j + ... + p_j+n-3}) + (2^{p_i + ... + p_i+n-2} - 2^{p_j + ... + p_j+n-2})

QED


Corollary 11.1:  If p₁, ..., p_n represent the powers of 2 that make up a cycle, then at least two of them are equal to 1.

Proof:

(1)  Since we are assuming a cycle, it follows that at least one of the p_i must be 1 for:

(a)  Assume that none of the p_i are 1.

(b)  Now by assumption each x_i ≥ 5  which gives us:

4x_i - 3x_i ≥ 5

and:

4x_i is greater than 3x_i + 1

x_i is greater than (1/4)*(3x_i + 1)

(c)  But then it follows by our assumption that each x_i+1 is less than x_i since:

x_i+1 is less than (1/4)*(3x_i + 1)

since we are assuming that there is no p_i = 1

(d)  But this is impossible since we are assuming a cycle so we reject our assumption in step #1a

(2)  Assume that there is only 1 one

(3)  Then it follows that all the other one's must be 2's since if there is one other value 3 or more then p₁ + ... + p_n ≥ 2n.

(4) But this is impossible since:

(a)  From Lemma 11, above, there is a case where we have p divides 2^{u - 1} - 2^{u - 2} = 2^u-2(2 - 1) = 2^u-2

(b)  But this is impossible since we know that p ≠ 2 so we reject our assumption in step #2 above.

QED

Lemma 12:


3^n-1 + 3^n-22^p_i + ... + 3*2^{p_i + ... + p_i+n-3} + 2^{p_i + ... + p_i+n-2} = (3 + 2^p_i)*...*(3 + 2^p_i+n-2) - (3)(3 + 2^p_i+1)*...*(3 + 2^p_i+n-2) - 3^n-1


Proof:

(1)   (3 + 2^p_i)*...*(3 + 2^p_i+n-2)  =  3^n-1 + 3^n-2[2^p_i + ... + 2^p_i+n-2] + ... + 3[2^{p_i + ... + p_i+n-3} + 2^{p_i+1 + ... + p_i+n-2}] + 2^{p_i + ... + p_i+n-2}

(2)  (3 + 2^p_i+1)*...*(3 + 2^p_i+n-2)  =  3^n-2 + 3^n-3[2^p_i+1 + ... + 2^p_i+n-2] + ... + 3[2^{p_i+1 + ... + p_i+n-3} + ... + 2^{p_i+2 + ... + p_i+n-2}] + 2^{p_i+1 + ... + p_i+n-2} 

(3)   (3)(3 + 2^p_i+1)*...*(3 + 2^p_i+n-2)  =  3^n-1 + 3^n-2[2^p_i+1 + ... + 2^p_i+n-2] + ... + 3²[2^{p_i+1 + ... + p_i+n-3} + ... + 2^{p_i+2 + ... + p_i+n-2}] + 3*2^{p_i+1 + ... + p_i+n-2} 

(4)  So it follows that:

(3 + 2^p_i+1)*...*(3 + 2^p_i+n-2) - (3)(3 + 2^p_i+1)*...*(3 + 2^p_i+n-2) - 3^n-1 = 3^n-1 + 3^n-22^p_i + ... + 3*2^{p_i + ... + p_i+n-3} + 2^{p_i + ... + p_i+n-2}

QED


Corollary 12.1:   If x₀, ..., x_n is a collatz cycle and n ≥ 3, then the following n equations must hold:

Proof:

(1)  From Lemma 7 above, we know that:

(2)   So, from Lemma 12 above, we get:

(3 + 2^p_i)*...*(3 + 2^p_i+n-2) - (3)(3 + 2^p_i+1)*...*(3 + 2^p_i+n-2) - 3^n-1 =

(3 + 2^p_i+1)*...*(3 + 2^p_i+n-2)[ (3 + 2^p_i) - 3] - 3^n-1 = 


(3 + 2^p_i+1)*...*(3 + 2^p_i+n-2)(2^p_i)  - 3^n-1

QED


Corollary 12.2:  If x₀, ..., x_n is a collatz cycle, then for all i

(3 + 2^p_i) does not divide:  2^{p₁ + ... + p_n} - 3ⁿ

Proof:

(1)  From Corollary 12.1, there exists some j such that:

j ≠ i and (j+n-1) ≠ i:

and:

x_j(2^{p₁ + ... + p_n} - 3ⁿ) = (3 + 2^p_j+1)*...*(3 + 2^p_j+n-2)(2^p_j)  - 3^n-1

(2)  Since j ≠ 1 and (j+n-1) ≠ i, it follows that there exists j+c such that p_j+c = p_i

(4)  It is clear that 3 does not divide 3+2^p_i since 3 cannot divide a power of 2 so that gcd(3 + 2^p_i,3^n-1) = 1

(5)  But then (3 + 2^p_i) cannot possibly divide 2^{p₁ + ... + p_n} - 3ⁿ since it cannot divide 3^n-1

QED


Corollary 12.3:   If x₀, ..., x_n is a collatz cycle, where p_i = 1 and p_j = 1 and i ≠ j, then there exists a,b:

(x_i - x_j)(2^{p₁ + ... + p_n} - 3ⁿ) = (2)(3 + 2^p_i+1)*...*(3 + 2^p_i+n-2)[2^a - 2^b]

Proof:

(1) From Corollary 12.1 above, we have:

x_i(2^{p₁ + ... + p_n} - 3ⁿ) = (3 + 2^p_i+1)*...*(3 + 2^p_i+n-2)(2)  - 3^n-1


x_j(2^{p₁ + ... + p_n} - 3ⁿ) = (3 + 2^p_j+1)*...*(3 + 2^p_j+n-2)(2)  - 3^n-1

(2)  Subtracting the bottom from the top gives us:

(x_i - x_j) (2^{p₁ + ... + p_n} - 3ⁿ) = (3 + 2^p_i+1)*...*(3 + 2^p_i+n-2)(2) - (3 + 2^p_j+1)*...*(3 + 2^p_j+n-2)(2)

(3)  Since both form cycles, there exists c such that p_i+c = p_j and p_i = p_j-c.

(4)  Since the equation in step #2 consists of a the difference of the products of n-2 terms, there are 4 possible ways cases to consider:

For purposes of this discussion, let:

Prod_i = (3 + 2^p_i+1)*...*(3 + 2^p_i+n-2)

Prod_j = (3 + 2^p_j+1)*...*(3 + 2^p_j+n-2)


Case I:  No overlap between the two terms excluded

(a)  In this case:

Prod_i = ***(3 + 2^p_j)(3 + 2^p_j+n-1)***

Prod_j = ***(3 + 2^p_i)(3 + 2^p_i+n-1)***

(b)  So the equation in step #2 above gives us:

(x_i - x_j) (2^{p₁ + ... + p_n} - 3ⁿ) = (***)(2)[(3 + 2^p_j)(3 + 2^p_j+n-1) -(3 + 2^p_i)(3 + 2^p_i+n-1) ]

(c)  Since by assumption, p_i = 1 and p_j=1, we have:

(x_i - x_j) (2^{p₁ + ... + p_n} - 3ⁿ) = (***)(2)(5)[(3 + 2^p_j+n-1) - (3 + 2^p_i+n-1) ]

(d)  Which gives us:

(x_i - x_j) (2^{p₁ + ... + p_n} - 3ⁿ) = (***)(2)(5)[2^p_j+n-1 -  2^p_i+n-1 ]


Case II:  Overlap of 1 term where p_j = p_i+n-1

In this case, both products exclude p_j = p_i+n-1 and we get:

(x_i - x_j) (2^{p₁ + ... + p_n} - 3ⁿ) = (***)(2)[(3 + 2^p_j+n-1) -(3 + 2^p_i) ] = (***)(2)[2^p_j+n-1 - 2 ]


Case III:  Overlap of 1 term where p_i = p_j+n-1

In this case, both products exclude p_i = p_j+n-1 and we get:

(x_i - x_j) (2^{p₁ + ... + p_n} - 3ⁿ) = (***)(2)[(3 + 2^p_j) -(3 + 2^p_i+n-1) ] = (***)(2)[2 - 2^p_i+n-1 ]

So, depending on the selection of p_i, p_j, this is the exact same as Case II.

Case IV:  Overlap of 2 terms where p_i = p_j+n-1 and p_j = p_i+n-1

This case is impossible since if both products exclude the same terms, then we have:

(x_i - x_j) (2^{p₁ + ... + p_n} - 3ⁿ) = (***)(2)[0 ] = 0

QED


Theorem 13:  If x₀, ..., x_n is a collatz cycle,

Then, there exists an integer a ≥ 1 such that:

 (2^{p₁ + ... + p_n} - 3ⁿ)  divides 2^a - 1

Proof:

(1)  From Corollary 11.1 above, we know that there exists p_i, p_j such that:

p_i = 1, p_j = 1, and i ≠ j.

(2)  From Corollary 12.3 above, we have:

(x_i - x_j)(2^{p₁ + ... + p_n} - 3ⁿ) = (2)(3 + 2^p_i+1)*...*(3 + 2^p_i+n-2)[2^a - 2^b]


(3)  From Corollary 12.2 above, we know that:

(2^{p₁ + ... + p_n} - 3ⁿ) must divide [2^a - 2^b]

(4)  Assume that a is greater than b.  [If necessary, we can switch i,j]

(5)  Then we have:

(2^{p₁ + ... + p_n} - 3ⁿ) must divide 2^b(2^a-b - 1)

QED

Corollary 13.1:  If  (2^{p₁ + ... + p_n} - 3ⁿ) divides 2^a - 1, then it follows that:


a ≥ 3

Proof:

This is pretty clear since  (2^{p₁ + ... + p_n} - 3ⁿ) cannot divide (2¹ - 1) or (2² - 1)

QED


Lemma 14:   

Let x₀, ..., x_n be a collatz cycle with p₁, ..., p_n the values defined in definition 1 above.

Let a be the number of p_i = 1

Let b be the sum of all  (p_j - 2) when p_j ≥ 3.

Then:


b ≤ a - 1

Proof:

(1)  From Corollary 9.2 above, we know that:

p₁ + ... + p_n is less than 2n.

(2)  This sum is equal to a sum in the following form:

2*****21*1

where the number of 1's at the end are equal to i where the sum p₁ + ... + p_n = 2n-i. 

(3)  Now, it is possible to transform the form in step #2 to the form in step #1 with two operations:

(a)  Swap the position of two values (the sum stays the same and the number of 1's stays the same)

(b)  Increase a value 2 or greater by 1 and change another value from 2 to 1.  (the sum stays the same but the number of 1's increases by 1)

(4)  In this way, it is clear that any combination of values is possible through these two operations and it is also clear that the number of 1's is equal or less than the number of times (b) is done + 1.

(5)  The conclusion for this proof follows.

QED

Corollary 14.1:  If there are two 1's that are consecutive (Case II or Case III in Corollary 12.3 above), then there are at least 1 other 1.

Proof:

(1)  By Corollary 12.3 above, we know that if this is the case, then:

x_i - x_j) (2^{p₁ + ... + p_n} - 3ⁿ) = (***)(2)[(3 + 2^p_j+n-1) -(3 + 2^p_i) ] = (***)(2)[2^p_j+n-1 - 2 ]

(2)  So, it follows that (2^{p₁ + ... + p_n} - 3ⁿ)  divides (2)(2^p_j+n-1-1 - 1)

(3)  From Corollary 13.1 above, this is only true if p_j+n-1 ≥ 4.

(4)  But if p_j+n-1 ≥ 4, then from Lemma 14, the total number of 1's is at least  4-2+1 = 3.

QED

Corollary 14.2: 

Let p₁, ..., p_n be the values described in Definition 1 above. 

There are at least two 1's that are not consecutive to each other

Proof:

This follows directly from Corollary 14.1 above.

QED

Lemma 15: 


Let x₀, ..., x_n be a collatz cycle with p₁, ..., p_n the values defined in definition 1 above.

Let a be the number of p_i = 1

Let b be the sum of all  (p_j - 2) when p_j ≥ 3.

Then:

Proof:

(1)  From Corollary 14.3 above, we can assume that all p_i = 1, p_j = 1 follows Case I from Corollary 12.3 above.

(2) It therefore follows that for each such p_i, p_j, we have:


(x_i - x_j) (2^{p₁ + ... + p_n} - 3ⁿ) = (***)(2)(5)[2^p_j+n-1 -  2^p_i+n-1 ]

(3)  Since it follows that (2^{p₁ + ... + p_n} - 3ⁿ) divides  2^p_i+n-1(2^{p_j+n-1 - p_i+n-1} - 1), for each possible pairings of 1's, we must be sure that the difference of the corresponding p_i+n-1, p_j+n-1 must differ by at least 3 (otherwise, we have a noncycle)

(4)  The only way this is possible is the corresponding values have the following set of values:

1, (1+3), (1+3+3), ...,  etc

(5)  Since there has to be one of these values for each existing 1, we know that there must be at least a such values so that we have:

1, (1+3), (1+3+3), ..., (1 + (a-1)*3)

(6)  Now, for b, we also need to subtract 2 and we can ignore the case where p_i = 1 so we have:

b ≥ (1+3-2), (1+3+3-2), ..., (1 + (a-1)*3 - 2)

(7)  Since we have (a-1) 1's and -(a-1) 2's, we can restate the sum as:

b ≥  (a-1)(1) - (a-1)(2) + (3) + (3 + 3) + (3 + 3 + 3) + ... + ([a-1]*3) =


= (a-1)(1) - (a-1)(2) + (1 + 2 + 3 + 4 + ... + [a-1])(3)

(8)  Using summation notation where (1 + ... + n) = (1/2)(n)(n+1), we get:

 
QED


Theorem 16:  There are no cycles in a Collatz Sequence of Odd Integers that do not have 1 as part of the cycle.

Proof:

(1)  Assume that there is a cycle that does not include 1 as part of the cycle.

(2)  Then, the cycle is characterized by the values p₁, ..., p_n  where each p_i ≥ 1 (see Definition 1 and Definition 2 above)

(3)  We can also be sure that p₁ + ... + p_n is greater than 1.5n (see Lemma 10 above if needed) and is less than 2n (see Corollary 9.2 above)

(4)  Let a be the number of p_i where p_i = 1

(5)  Let b be the sum of (p_i - 2) where p_i ≥ 3.

(6)  From Lemma 14 above, it follows that b ≤ a - 1.

(7)  So,from  Lemma 15 above, it follows that:

which is only true if:

which is the same as:

(a - 1)*4 ≥ (a)(a-1)(3)

so that:

0 ≥  (a-1)(3a - 4) 

so either a ≤ 1 or a ≤ (4/3)

(8)  But either way this is impossible since a ≥ 2 by Corollary 11.1 above.

(9)  So it follows that we must reject our assumption at step #1.

QED

Purpose

For the past year, I've been working on a blog that traces the history of number theory from the perspective of Fermat's Last Theorem.

As an amateur, it has been fun and very rewarding to review the most important proofs in the history of number theory and present them in a roughly historical order.

In the course of doing this, I have become interested in trying my hand at some basic results. Since I am not a mathematician by training or by profession, there is little doubt that I will make mistakes.

It is my hope that my efforts will be interesting to other amateurs. Since I am planning to take on some heavy problems, I am doubtful that my proposed proofs will hold up. Still, I cannot resist.

Please feel free to point out a flaw or to comment on how the proof can be improved.

Cheers,

-Larry