\\ 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.