[seqfan] Comments on A135543
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