### A Collatz type Conjecture of Mridul K. Sen

For y ≥ 1, the iterates y, t(y), t(t(y)),... of the function

 t(x)=φ(x)/2 if x is even and x > 2, t(2)=1, t(x)=(3x+1)/2 if x is odd,

are printed and the number of steps taken to reach 1 is recorded. Here φ(x) is Euler's function.

It is conjectured by Mridul K. Sen in an email dated May 26, 2009, that every trajectory starting from a positive integer will reach 1.

Our calculation of Euler's function is based on a primitive factoring program which uses the Brent-Pollard algorithm and Pollard's p-1 algorithm. It should work on integers with no more than 20 digits.

Points to note:
(i) If n is odd, write n+1=2k3rR, where k ≥ 1, r ≥ 0 and gcd(R,6)=1. Then for 0 ≤ i ≤ k,

 ti(n) =3i(n+1)/2i - 1, =3i+r2k - iR - 1.

Hence the iterates ti(n) remain odd and increase if 0 ≤ i < k, until we reach tk(n)=3k+rR - 1, which is even.
(ii) If n is even, n > 4 and n is not of the form 2pa, a ≥ 1, where p is a prime of the form 4t+3, then 4 divides φ(n). However if n=2pa, a ≥ 1, where p is a prime of the form 4t+3, then φ(n)/2=pa-1(p - 1)/2, which is odd.

So if n is odd (red), the iterates increase till they reach an even (blue) integer. Then if they do not subsequently meet an integer of the form 2pa, a ≥ 1, p a prime of the form 4t+3, they decrease and remain even, eventually reaching 1. Otherwise they decrease until they meet an odd integer of the form pa-1(p - 1)/2, where p is a prime of the form 4t+3 and start to increase again. An example of this is n=3225811.

Iterates of Mersenne numbers 2n - 1 increase till they reach 3n - 1 and then often decrease monotonically to 1, exceptions in the range 2 ≤ n ≤ 30 being n=5, 9, 19, 27. On limited experimentation, iterates of the numbers 5n - 1 always seem to decrease monotonically to 1.

Enter y: