An iteration produces all the prime numbers

[Valentin Albillo]

(02-14-2021 12:38 PM)EdS2 Wrote:  Indeed, so, all true. I still liked what I saw!

Thanks for Mills' constant (1.3063778838630806904686144926...) - that's perhaps a little more accessible, as we only need an expression, not an iteration. (Then again, it produces only primes, less impressive to me than producing all primes, although that is of course a matter of taste.)

Mills' constant (1.306377883863...) produces primes which grow extremely fast as the article you linked states (2, 11, 1361, 2521008887, 16022236204009818131831320183, ~O(1e84)), each term has about 3x the digits of the previous term, so using it you can only produce and certify the primality of a very few before you are forced to check their primality using a probabilistic method for a little while and afterwards even that won't be feasible.

However, there's an infinity of prime-generating Mills-like procedures but with much reduced growing rates so they can be used to generate proven primes by the hundreds. On the other hand, there are some iterative procedures (many trivial, but not all) that do not depend on the accuracy of an irrational (transcendental ?) constant to generate an indefinite number of fully-certified primes.

Primes are always a source of awe. One of the many many things that awed me is that you can generate the sequence of primes using the sequence of zeros of the Riemann's Zeta function, and you can in turn generate the zeros of the function using the primes. Perfectly symmetrical, one sequence encodes the other.

By the way, the constant mentioned in your linked article can be generated to the full 13 digits given there by running this trivial 2-line HP-71B program, which produces the value in no time:

      1   DESTROY ALL @ P=2 @ M=P @ S=-1
      2   FOR I=1 TO 12 @ P=FPRIM(P+1) @ S=S+(P-1)/M @ M=M*P @ NEXT I @ DISP " 2";STR$(S)

      >RUN
            2.920050977316

Regards.
V.