View Single Post
Old 2017-09-18, 15:39   #3
arbooker
 
arbooker's Avatar
 
"Andrew Booker"
Mar 2013

1258 Posts
Default

Quote:
Originally Posted by sean View Post
In many cases the map results in a fraction (i.e. odd/2) and the iteration finishes. However, there appears to be cases (perhaps a lot of cases for large n) where the iteration appears unbounded and continues indefinitely (not unlike certain aliquot sequences or home primes, etc.). It is not clear why this should be.
I would guess that asymptotically 100% of positive integers have unbounded trajectory, and it might be possible to prove something along those lines.

Note that \((\sigma(n)+\varphi(n))/2\) is an integer unless \(n\) is a square or twice a square, and those are very rare among large numbers. Further, if \(n>1\) and \((\sigma(n)+\varphi(n))/2\) is odd then \(n\) must be of the form \(pm^2\) or \(2pm^2\) for an odd prime \(p\). Combining this with some sieve theory, one can show that the number of composite \(n\le x\) with \((\sigma(n)+\varphi(n))/2\) prime is \(O(x/\log^2{x})\). Since the map tends to increase geometrically and \(\sum1/k^2\) converges, this suggests that a typical large composite has little chance of ever reaching a prime.
arbooker is offline   Reply With Quote