[seqfan] Re: Iterating sigma - 1

[T. D. Noe]

At 4:51 PM -0400 5/6/10, franktaw at netscape.net wrote:
>Consider http://www.research.att.com/~njas/sequences/A039654 - Prime
>reached by iterating f(x) = sigma(x)-1 on n.
>
>It isn't obvious that this iteration always reaches a prime, although
>it seems nearly certain that it does. Should we add something like ",
>or 0 if no prime is ever reached", with a comment that apparently the
>sequence always does reach a prime? (Or can someone prove that a prime
>is always reached?)
>
>One might, in this case, also add a(1) = 0 (suitably modifying the
>comment).

For n>1, the iteration "x=n, repeat x=f(x) until a fixed point is reached"
will either increase indefinitely or converge to a prime.  There is no
possibility of looping because f(x) >= x for all x>1.  If the iteration
converges, it will converge to a prime because sigma(x)=x+1 iff x is prime.
The following Mma code is better because it doesn't stop after 6 iterations:

f[n_] := DivisorSigma[1,n]-1; Table[FixedPoint[f,n], {n,1000}]

The iteration converges for all 1 < n <= 10^6. In that range, the maximum
number of iterations is 45.

Tony