[seqfan] Re: Do 20 and 105 eventually reach a prime in these sequences?

Robert Gerbicz robert.gerbicz at gmail.com
Wed Sep 14 21:31:10 CEST 2011

```2011/9/14 Sean A. Irvine <sairvin at xtra.co.nz>

>
> This seems to be a simple variation on the home prime problem, for which 49
> has proved notoriously difficult.
>
> See: https://oeis.org/A037271
>
> Sean.

Yes, and for home primes it is known with heuristic that for all starting
number the sequence terminates in prime. I have not found this heauristic,
here it is mine for this sequence (but with a little modification this is
also good for home primes):

A random n integer has got loglog(n) prime factors, for almost all of them
it has got exponent of one. This gives that a(n+1) is longer than a(n) in
average by C1*log(log(a(n)), so
a(n+1)~a(n)*10^(C1*log(log(a(n))))=a(n)*exp(C2*log(a(n))) for some C1,C2>0
(here ~ does not mean asymptotic). Assume that C2=1 to simplify the
calculations.

For a given k (large) integer let n the smallest number for that
exp(exp(k))<a(n)<exp(exp(k+1))
How many terms of the sequence are between exp(exp(k)) and exp(exp(k+1)) ?
See for the next number: a(n+1)<=a(n)*log(a(n))<a(n)*exp(k+1) From this we
can easily get using induction that there are at least
(exp(k+1)-exp(k))/(k+1) terms of the sequence in the above interval.

A random x integer is prime with 1/log(x) probability. Let E(n)={event that
a(n) is prime} and P(E(n)) is the probability of E(n). The sum of the
probabilites for all n, where exp(exp(k))<a(n)<exp(exp(k+1)) is:
sum(1/log(a(n)))>=1/exp(k+1)*(exp(k+1)-exp(k))/(k+1)=(1-1/e)/(k+1)
But sum of 1/(k+1) is infinity so by Borel-Cantelli lemma we can get that
we reach prime with probability of 1. (we can't apply exactly the lemma,
because the E(n) events are not independent)

```