## MathDemos:Solve 3n+1 Problem(解决3n+1问题)

3n+1 Problem, Collatz conjecture

Collatz conjecture: successive operations on a number as dividing it by 2 if it is even and else multiply it by 3 and add 1. The conjecture says that the sequence ends with 1.
It is also known as the 3n+1 problem or the Hailstone problem. The function is
f:(n)=> n%2==1? 3*n+1: n/2
For example,f(3)=10. And f(10)=5. This leads to the sequence 3, 10, 5, 16, 4, 2, 1, 4, 2, 1, ... which indeed reaches 1. Syracuse function g(n) only considers odd numbers. A sequence obtained by iterating the function from a given starting value is sometimes called "the trajectory" of that starting value.

## Collatz-Odd-Tree Generation Rule

1. x is a leaf node in the full Collatz-Odd-Tree iff (x%3==0)
2. v(x)= x%3==0?null:(x%3==1?(4*x-1)/3:(2*x-1)/3) to generate the first child of x if x%3!=0
3. h(x)=4*x+1 to generate the next sibling of x. Because 3(4*x+1)+1 = 12*x+4 = 4*(3*x+1) .

To prove 3n+1 Conjecture only needs to prove Collatz-Odd-Tree generating all positive odd integers.
Obviously, start from `x0=1`, `h(x)=4*x+1` and `v(x)=(2*x-1)/3 or (4*x-1)/3` repeatedly iterate all positive integers formed of 4k+1 or 4k-1, just all positive odd integers. Collatz Conjecture is proved!□

## Collatz-Syracuse Decent Theorem

sage.misc.misc.nest(f, n, x)
Return f(f(...f(x)...)), where the composition occurs n times.