Ulam's Spirals : Towards an Explanation

Last Update March 25, 2004

Copyright Didier van der Straten 2002-2004


An abundant literature as well as an ever increasing number of web pages are devoted to this very curious observation originally made by S.M. Ulam : Why is that so that prime numbers tend to accumulate on some "parallel to diagonals" while they are much poorer in density in some others ?

An interesting and interactive site can help visualize this. It has been developped and is maintained by Dario Alpern here .

This phenomenon is to date ranked as one of the many mysteries of the prime number theory.

Here is an attempt to present an original explanation.

It is straightforward to observe that the terms belonging to a "half-line parallel to the North-West to South-East diagonal" are of the form (2n+1)^2 + (2n+1) + k or of the form (2n)^2 + 2n + k where k influences the "distance" of this parallel wrt that NW-SE diagonal.

For the half-lines parallel to the South-West to North-East diagonal, the terms are of the form (2n)^2 + k or of the form (2n+1)^2 + k where k has a similar role w.r.t. the SW-NE diagonal.

To select half-lines containing prime numbers, we have of course to select the parity of k respectively in those four forms with a view to generate odd integers.

First I suggest to study the two first forms (half-lines parallel to the NW-SE diagonal), and together at that, so as to enlighten a close relationship between the Ulam's Spiral phenomenon and the fact that the polynomial n^2 + n + k, for well chosen (odd) values of k, can produce series very abundant in prime numbers.

The most striking example is n^2 + n + 41 which produces already 41 primes for the values of n from 0 to 40.

Many researches are indeed made about those polynomials, attempting to find out other "good" values of k, but to date without an explanation of the the "internals" of this phenomenon.

To illustrate the developments that follow, one can consult table1

Let us, for a start, examine the p remainders of the division of n^2 + n by p for n evolving from 0 to p-1 (with p being a prime). In short, the expression ;

modulo ((n^2 + n);p) for n running from 0 to p-1

It is enough indeed to examine the p first terms because they are the "pattern of remainders" which will repeat in sequence beyond p.

At first glance, the two "extreme" remainders are zero. (i.e. for n=0 and for n=p-1).
Moreover the remainders for n=a (a<(p-1)/2) and for n=p-1-a are the same, as can be seen by developing the two expressions, which are said to be congruent modulo p.

Finally, one finds a particular remainder for a=(p-1)/2, the value exactly in the middle of the series.

A further important observation is that all the remainders from n = 0 to n = (p-1)/2 have a different value. (A proof of this will be shown.)

Hence, for the successive p remainders from n=0 to n=p-1, one finds that it takes only (p+1)/2 different values. One of the values occurs exactly once, the other values occur twice.

For example, for p = 7, one finds the following series of remainders : 0, 2, 6, 5, 6, 2, 0 for n from 0 to 6. That builds up 4 different values, where 5 occurs once and 0, 2 and 6 occur twice, in a symmetrical pattern.

The striking conclusion is that there are therefore (p-1)/2 values that the remainder cannot take over the whole series.

In the above example, 1, 3 and 4 are "absent" in the series.

This observation that some remainders are missing has a close relationship with the study of quadratic residues and quadatic non-residues as will be approached when studying the SW-NE diagonal.

Hence, back to our expression n^2 + n + k, there must be (p-1)/2 odd values of k from 1 to 2p-1 for which this expression is NEVER DIVISIBLE BY p.

In our above example again, n^2 + n + k is never divisible by 7 for k = 3, 11 and 13.

Now taking the step to tabulate various values of p, one finds that :
n^2 + n + 1 is never divisible by 5, 11, 17, 23, 29... ;
n^2 + n + 3 is never divisible by 7, 13, 17, 19, 29... ;
n^2 + n + 5 is never divisible by 3, 13, 29, 31, 37... ;

and that n^2 + n + 41 is not divisible by any of the primes from 3 to 37... !

In table2 the number of occurrences (over a sequence of p terms obtained by letting n vary by steps of 1 in the expression n^2 + n + k with k odd) where that expression is divisible by p is tabulated for p from 3 to 41 and for k (odd) from 1 to 41. Limiting ourselves to a sequence of p terms stems from the observation that this is the pattern that repeats itself when the sequence gets larger.

This explains why for a given p and a varying (odd) k, some terms can be 2, some (more seldomly) 1 and some others 0 (replaced by blanks to enlighten the phenomenon under study.

This table is an important summary of all our observations so far.

Now examining the table for a given value of k and letting p take the values of consecutive odd primes, one can see that some values of k are rather rich, and some are rather poor in the sense of producing terms of the form n^2 + n + k having small prime factors.

For instance, 15 and 33 are very "rich" while 17 and 41 are very "poor".

That observation has a straight relationship with the probability that some values of k produce series "poor" or "abundant" (respectively) in prime numbers.

The best example indeed is k = 41, where it appears that none of the terms n^2 + n + k is divisible by any of the primes from 3 to 37 inclusive.

The next step of our study is to calculate how that lack (or abundance) of small prime divisors in a given series of terms affects the "prime density" of that series.

A good starting point of understanding is to observe what the "prime density" becomes when, from the list of all natural integers, we shift to the list of all odd integers : it is merely multiplied by 2.

This is the suggested approach here : find the "density increase factor" applicable to a defined portion of the overall sequence of terms of the form n^2 + n + k, for each value of k under review, and letting n vary (by increment of 1).

Looking at table3 one can find the results (the formula used will be explained in a near future) i.e. the density increase factor that affects series of terms. Under each value of p, we see the value of the density increase factor expected to affect the terms of the form n^2 + n + k for values between p^2 and the square of the next p.

Hence the resulting prime density is the "original" prime density (i.e. assuming among all natural numbers) multiplied by that factor.

Let us see the example of k = 41, producing 41, 43, 47, etc. Around 43, the affecting p is 5 (its square is 25 and the next p^2 is 49). So the density increase factor is 3.75. Using the gross formula for the "original" or "natural" prime density around 45 from the Prime Number Theorem, we get :

(1 / ln(45)) * 3.75 = 0.997

This gross approximation "confirms" that "all" the numbers produced by n^2 + n + 41 between 41 and 49 (i.e. between n=0 and n=3) are prime.

In table4 the expected prime density is computed along some "half lines parallel to the NW-SE diagonal" i.e. for k = 1, 3, 5 and 7.

Here is a quick ranking of k values (lower than 100) producing n^2 + n + k diagonals with high prime density (by decreasing density increase factor) :

41, 17, 59, 67, 47, 11, 83, 77, 71, 37, 31... The "density increase factor" runs from 6.24 to 2.64 (will be developed in a separate table)

Here is also a ranking of k values leading to diagonals with low prime density (by increassing density increase factor):

75, 63, 33, 93, 15, 45, 99, 9,57, 21, 39, 3... The "density inncrease factor" runs from 0.61 to 0.98 (same remark).

All those are "predictive" figures as per the above explanations. It is good to observe that over a good range of k values say from 1 to 999 the mean value of all multiplication factors approaches 2 (which represents the multiplication factor for all the odd numbers together that contribute to build all those diagonals.

Very recently the author of this paper has found a beautiful web site helping to visualize properties of numbers as implied by their location in prime spirals : http://www.numberspiral.com/index.html written by Robert Sacks.

(This is a first reference among many that will appear here in a near future)

Note that in further studies we will discuss the other diagonals (SW-NE) and discover that, due to a simple phenomenon, some such diagonals can be without any prime number.

(study will be continued at a later date.) (above update date February 24, 2003)

(new upadte April 9, 2003))

To further illustrate the "predictive" Ulam's diagonal prime density computation, table5 has been developped : it shows for selected values of k the observed/real number of prime terms among the 100 first terms, i.e. for n from 0 to 99. The "predicted" number appearing besides the "observed" number is obtained by summing the "predictive prime density" applying to each term, as shown in the above example.

Copyright Didier van der Straten 2002-2003-2004

Last Update March 25, 2004


home page