[seqfan] Comments on A135543

David Wilson dwilson at gambitcomm.com
Fri Nov 21 16:57:44 CET 2008

A135543(n) gives the smallest number requiring n iterations of f(n) = 
n-(largest prime <= n) to reach a number <= 1.

I guess the current description is adequate, could be a little clearer.

Since 0 is in the range of the iteration function, I think a(0) = 0 is 
superior to a(0) = 1.

The comment asks

    a(5) must be very large (>100000000). Can anyone extend the sequence?

Probably not. We can prove that

    a(n) = a(n-1) + A104138(a(n-1)) (n >= 2)

where A104138(n) is the smallest prime followed by a gap of n or more 

[Note 1: If we make a(0) = 0 as suggested above, this recurrence applies 
to the entire sequence].

[Note 2: There is something interesting going on here. a(n), the record 
values of an iteration-counting function, turns out to be an iterated 
function. How do we get from the first iteration function (f(n) = n - 
(largest prime <= n)) to the second (a(n) = a(n-1) + (smallest prime 
followed by a(n-1) nonprimes))? A generalization might help us compute 
record values of other iteration-counting functions].

The largest known value of A104138(n) is A(1441) = 804212830686677669. 
a(5) = 1357323+A104138(1357323) is well beyond our projectable 
computational abilities. Our best (poor) estimate of A104138(n) is 
sqrt(n)exp(sqrt(n)), putting a(5) in the 500-digit ballpark.

More information about the SeqFan mailing list