|t(x)=φ(x)/2||if x is even and x > 2,|
|t(x)=(3x+1)/2||if x is odd,|
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.|
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.
Last modified 12th August 2010
Return to main page