Dijkstra's Notes on Structured Programming - concerning the program to compute first 1000 prime numbers

Question

In his "Notes on Structured Programming" essay, E. W. Dijkstra gives an example of a program that computes the first 1000 primes (Section 9. "A First Example of Step-Wise Program Composition").

The idea is to iterate all the numbers from 1 to 1000 in increasing order, to test each one and if found to be prime save it into an array p. The test consists of giving an answer to the question of whether the number j is divided by one of the primes found earlier: if it is divided - the number is not prime; otherwise - it is prime.

• j is the number under test and here it is assumed to be incremented by 1 at each iteration (in the original paper an optimization has been introduced where j is odd and incremented by 2).
• The smallest array index is 1.

Next is an excerpt from the paper followed by the question proper:

We use the facts that
(1) [...] the smallest potential factor to be tried is p[1]
(2) the largest prime number to be tried is p[ord - 1] where p[ord] is the smallest prime number whose square exceeds j.

(Here I have also used the fact that the smallest prime number whose square exceeds j can already be found in the table p. In all humility I quote Don Knuth's comment on an earlier version of this program, where I took this fact for granted:

"Here you are guilty of a serious omission! Your program makes use of a deep result of number theory, namely that if $p_n$ denotes the $n$-th prime number, we always have $$ p_{n+1} < (p_{n})^2 $$ " Peccavi.)

In my analysis I have arrived at the conclusion that the program does not depend on this result; that is - the program will work correctly even if the inequality above were not true.
Help is needed in finding the error in my line of reasoning, or to identify the misunderstanding of the source material, if that were the case.

---

The program makes use of a lemma

If a natural number $n > 1$ is composite, then $n$ is divisible by some prime number $p \leq \sqrt{n}$.

(A proof can be found in "Discrete Mathematics" 2nd ed., by Edgar G. Goodaire, page 116)

Thus when we test number j for primality we only need to consider those primes whose squares are less than or equal to j.

Suppose that we have computed the first $n > 1$ primes and all of them are in the array p. We next initiate the process of computing the next prime $p_{n+1}$ by incrementing j and testing it for primality.
In the case where $p_{n} < j < (p_{n})^2$, there exists a prime $p_{k}$ such that $$(p_{k-1})^2 \leq j < (p_{k})^2$$ The potential factors of j are $p_{1},p_{2},..,p_{k-1}$ and all of them are in the array p, thus if the next prime lies in the interval $p_{n} < j < (p_{n})^2$ we are guaranteed to find it.
This is the case which corresponds to the theorem pointed by Don Knuth, and since we know it to be true, we could stop here as far as program correctness is concerned.

But for the sake of argument, let's continue and consider the case $j > (p_{n})^2$. All of the numbers $p_{n} < i < j$ are composite, so the largest prime less than j is $p_{n}$ and, by our assumption $(p_{n})^2 < j$. Thus the potential factors of j are $p_{1},p_{2},..,p_{n}$ and all of them are in the array p.

Given that in both cases the entire list of primes whose square is less than or equal to j is in the table p, and that's the necessary and sufficient condition for the primality test, we conclude that the relation $p_{n+1} < (p_{n})^2$ plays no role in the operation of the program.

Answer 1

Statement (2) requires that the smallest prime number whose square exceeds $j$ is in the list. If $j=p_{n+1} > (p_n)^2$, then the smallest prime number whose square exceeds $p_{n+1}$ is $p_{n+1}$ itself. As $p_{n+1}$ is not in the list while tested, (2) no longer holds.

You indeed show that all primes that are divisors of $j$ are in the list. So, an algorithm that tests all divisors in the list would be correct. However, this isn't what the algorithm in the text does, it first looks for a prime of which the square exceeds $j$, but doesn't have to be a proper divisor of $j$.

So, the algorithm as stated in the text does require property (2), which relies on the fact that $j=p_{n+1} > (p_n)^2$. In your analysis, you made the change that only the primes that divide $j$ properly need be in the list. This is a valid algorithm, but it is a different algorithm than the one in the text.

In other words, while having all primes that are proper divisors of $j$ in the list is nessecary, it isn't sufficient to run the algorithm as stated in the text.

Answer 2

From memory: His algorithm looked for the next prime in the sieve, and exited if that prime squared was too large. The way the code was written, it assumed the next prime is in the sieve, and would go wrong if it wasn’t.

There may not be a p[ord] in the sieve with a square large enough.