Problimes

[Dean Hickerson]

Jon Perry asked:

> Can we have some definitions for: A003066 A003067 A003068

Antti Karttunen replied:

> I think the sequences are completely defined by their
> formulae, given as Maple code (which has erroneously been
> given in Mathematica-code field %t !):
> a[1]:=2: for i from 1 to 150 do a[i+1]:=floor(a[i]+1/product((1-1/a[j]), j=1..i)): od:
>
> For A003067 and A003068 replace floor with round or ceiling respectively.
>
> But what we could have (in addition to definitions) is some elaboration!

I haven't seen the reference, but based on its title ("How unexpected is
the prime number theorem?") and the name "problimes", here's a guess:

Suppose you have a list of the first n prime numbers p_1, ..., p_n, and
you want to estimate the next one.  The probability that a random integer
is not divisible by any of p_1, ..., p_n is  (1-1/p_1) * ... * (1-1/p_n).
In other words, 1 out of every  1/((1-1/p_1) * ... * (1-1/p_n))  integers
is relatively prime to p_1, ..., p_n.  So we might expect the next prime
to be roughly this much larger than p_n; i.e.

    p_(n+1)  may be about  p_n + 1/((1-1/p_1) * ... * (1-1/p_n)).

The 3 sequences in question are obtained by replacing this approximation
by an exact equation, using 3 different ways of making the results
integers.  I'm guessing that Hirschhorn derives asymptotic formulae for
the sequences, and that they're similar to the one for primes.

Dean Hickerson
dean at math.ucdavis.edu