### 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=2^{k}3^{r}R, where k ≥ 1, r ≥ 0 and gcd(R,6)=1. Then for 0 ≤ i ≤ k,

t^{i}(n) | =3^{i}(n+1)/2^{i} - 1, |

| =3^{i+r}2^{k - i}R - 1. |

Hence the iterates t^{i}(n) remain odd and increase if 0 ≤ i < k, until we reach t^{k}(n)=3^{k+r}R - 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^{n} - 1 increase till they reach 3^{n} - 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^{n} - 1 always seem to decrease monotonically to 1.

*Last modified 12th August 2010*

Return to main page