Review: A067836

[David Wilson]

Concerning A067836:

In the description, "nxtprime" and "nxtprm" should be changed to
"nextprime".

Regarding the comment:

These are easy to prove:

n >= 1  ==>  a(n) >= 2.
1 <= k < n  ==>  a(k) | f(n)  ==>  a(k) <= f(n).

Let 1 <= k < n, suppose a(k) | a(n).  Then a(k) | nextprime(f(n)+1) - f(n)
==>  a(k) | nextprime(f(n)+1).  Since a(k) >= 2, a(k) = nextprime(f(n)+1).
This gives nextprime(f(n)+1) <= f(n), clearly absurd, so a(k) does not
divide a(n).

Let p be the least prime missing from the set {a(1), ..., a(n-1)}.  a(n)
cannot be divisible by a(1) through a(n), hence its smallest prime factor
is >= p.  If a(n) is composite, we must therefore have a(n) >= p^2,
that is, nextprime(f(n)+1)-f(n) >= p^2.  I suspect that this implies an
unusually large gap between f(n) and the next prime in relation to the size
of f(n), though the analysis is beyond me.  If I am right, this argues very
strongly that a(n) is prime, that is, the sequence probably contains no
composites.

For example, among the 58 published elements, all are prime, and 79
is the first missing prime.  In order for there to be a composite value
later in the sequence, it must be at least 79^2 = 6241.  The largest
published element in the sequence, 577, is nowhere near 6241.  I am
willing to conjecture that 79 will show up the sequence before an
element >= 6241.

Also, I would like to express some doubt as to the certainty of the
later elements in the sequence.  f(n) grows very quickly, and is quite
large by the time we reach n = 58.  I suspect that for larger f(n),
a(n) = nextprime(f(n)+1) - f(n)) is a probable, not certain, value.  If
this is so, it should be noted.