[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)



More information about the SeqFan mailing list