The Collatz type Conjecture of Mridul K. Sen

A Collatz type Conjecture of Mridul K. Sen

For y ≥ 1, the iterates y, t(y), t(t(y)),... of the function \[ t(x)=\left\{\begin{array}{cl} \phi(x)/2 & \mbox{ if $x$ is even, $x>2$,}\\ 1 & \mbox{ if $x=2$,}\\ (3x+1)/2 & \mbox{ if $x$ is odd,} \end{array} \right. \] are printed and the number of steps taken to reach 1 is recorded. Here $\phi(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=2^k3^rR, where k ≥ 1, r ≥ 0 and gcd(R,6)=1. Then for 0 ≤ i ≤ k,

tⁱ(n) =3ⁱ(n+1)/2ⁱ - 1,

=3^i+r2^{k - i}R - 1.

Hence the iterates tⁱ(n) remain odd and increase if 0 ≤ i < k, until we reach t^k(n)=3^k+rR - 1, which is even.
(ii) If n is even, n > 4 and n is not of the form 2p^a, a ≥ 1, where p is a prime of the form 4t+3, then 4 divides φ(n). However if n=2p^a, a ≥ 1, where p is a prime of the form 4t+3, then φ(n)/2=p^a-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 2p^a, 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 p^a-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 2ⁿ - 1 increase till they reach 3ⁿ - 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 5ⁿ - 1 always seem to decrease monotonically to 1.

Last modified 12th August 2010
Return to main page