mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2017-09-14, 04:52   #1
sean
 
sean's Avatar
 
Aug 2004
New Zealand

22·5·11 Posts
Default 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.
sean is offline   Reply With Quote
Old 2017-09-14, 10:55   #2
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts
Default

Quote:
Originally Posted by sean View Post
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.
if n is composite since both sigma(n) and phi(n) are multiplicative to some extent the sum is close ( but below at last check) to a multiplication of earlier terms ( not necessarily in the same iteration chain).

Last fiddled with by science_man_88 on 2017-09-14 at 11:01
science_man_88 is offline   Reply With Quote
Old 2017-09-18, 15:39   #3
arbooker
 
arbooker's Avatar
 
"Andrew Booker"
Mar 2013

5×17 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
Reply

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 2013-07-23 20:50
What are your per-iteration times? LiquidNitrogen Hardware 22 2011-07-12 23:15
Spooky sigma values lavalamp Software 2 2010-08-24 15:22
Time per iteration em99010pepe Riesel Prime Search 7 2007-08-30 08:54
Per iteration time sofII Software 8 2002-09-07 01:51

All times are UTC. The time now is 03:06.

Sat Nov 28 03:06:39 UTC 2020 up 79 days, 17 mins, 3 users, load averages: 1.05, 1.10, 1.09

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.