\\ Collatz-Sequence
\\ Created by Michael Hortmann, Aug 4 2019
\\ see https://en.wikipedia.org/wiki/Collatz_conjecture
\\ define recursively:
\\ x_{0} any positive integer as initial value
\\ x_{n+1}:=x_{n/2}, if x_n even,
\\ x_{n+1}:=(3*x_{n+1})/2, if x_n odd.
\\ Obviously we have a loop 2->1->2 .
\\ Therefore we halt the sequence when we reach the value 1.
\\ Collatz' conjecture: we arrive at the value 1 from any initial
value
\\ It's interesting that such a seemingly simple problem should be
so
\\ difficult.
collatz(n)={
local(q=divrem(n,2));
if(q[2],return(3*q[1]+2),return(q[1]))
}
collatz_reverse(n)={
local(r=random(2),q=divrem(2*n-1,3));
if(r,return(2*n),if(q[2],return(2*n),return(q[1])))
}
\\ the following line produces a collatz sequence of length 100:
n=1; for(i=1,100,print(n);n=collatz_reverse(n))
\\ the following line proves it:
j=0;while(n-1,print(j++," ",n);n=collatz(n))
\\ The Collatz function can be viewed as a self-mapping of the
\\ natural numbers. We can interpret it as a dynamical system.
\\ Collatz' conjecture states that all orbits end in the cycle
2->1 .
\\ The Collatz function is not injective: e.g. 3->5 and 10->5.
\\ Any number n, has either 1 or 2 preimages namely 2*n and
\\ (2*n-1)/3 if this is an integer, i.e. if n%3 = 2.
\\ That is, one in three integers has two preimages.
\\ Our reverse function above chooses one of the preimages at
random.