20170914, 04:52  #1 
Aug 2004
New Zealand
13·17 Posts 
Iteration of (sigma(n)+phi(n))/2
In recent weeks there has been some interest on the seqfan mailing list about iterating the map (sigma(n)+phi(n))/2 (see for example A291790).
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. The smallest unresolved case is starting with n=270, which has now survived 515 iterations of the map. The unresolved cases for n<1000 are 270, 440, 496, 702, 737, 813, 828, 897, and 905. There are other values less than 1000 unresolved, but their trajectories converge with one of the nine listed. All of them have survived at least 400 iterations. All the factorizations for the existing steps have been added to factordb.com. I'm not planning on taking these further myself, but there is plenty of scope for fairly easy factorization here. Some the composites are still down in 100 digit range and even the hardest (for the 270 trajectory) is only a C138. 
20170914, 10:55  #2  
"Forget I exist"
Jul 2009
Dumbassville
10000011000000_{2} Posts 
Quote:
Last fiddled with by science_man_88 on 20170914 at 11:01 

20170918, 15:39  #3  
"Andrew Booker"
Mar 2013
5·17 Posts 
Quote:
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. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Given sigma(n)n, find the smallest possible n  mart_r  Aliquot Sequences  6  20130723 20:50 
What are your periteration times?  LiquidNitrogen  Hardware  22  20110712 23:15 
Spooky sigma values  lavalamp  Software  2  20100824 15:22 
Time per iteration  em99010pepe  Riesel Prime Search  7  20070830 08:54 
Per iteration time  sofII  Software  8  20020907 01:51 