AS/SA No 14, Article 7: Peter Marteinson, "Observations on the Regularity of Prime Distribution"

Stanislaw Ulam’s (1964: 516) most general observation on his famous spiral, that a “property of the visual brain” allows patterns relating to the characteristics of primes to be discovered, may indeed stimulate the mathematical imagination, and inspire further creative attempts at visual pattern recognition in this area, but his spiral (fig.1), like its derivatives, has yet to be successfully interpreted in terms of possible arithmetic principles that can explain the genesis of the known distribution of prime numbers. Of his spiral he says only that it “appears to exhibit a strongly nonrandom appearance” (Stein et al. 1964). A corollary of this somewhat disappointing observation is that Euler’s pessimistic prognosis has yet to be disproved: “Mathematicians have tried in vain to this day to discover some order in the sequence of prime numbers, and we have reason to believe that it is a mystery into which the mind will never penetrate” (cited by Ivars Peterson in Science News, 5/4/2002). The Encyclopædia Britannica (2004) continues to suggest this consensus is alive and well, referring in an article entitled “Elementary Number Theory” to “the irregularity in the distribution of primes” which “suggests that there is no simple formula for producing all the primes.”

Figure 1. Ulam's Spiral

AS/SA nº 14, p.80

Ulam’s spiral does, however, corroborate the intuition that the entire question of primeness, articulated on the basis of an arithmetic product of two factors, is inherently a problematic in two dimensions, in that a pair of factors, along with their product, may be understood as a length, a width and an area in discretely quantified whole units of two-dimensional space. Consequently, by representing numbers as two-dimensional matrices of elements, one quickly observes that primes may be thought of as particularly ‘rough’ or uneven in terms of the simple property of rectangularity.

Figure 2. Two primes and their common neighbor in two dimensions

The primes 11 and 13 both display this property (see Figure 2): no matter how many permutations one attempts, rearranging their component elements into differing rows and columns, one never arrives at a rectangular configuration, as there is always a single exclusion, a ‘missing’ element, or a single additional element, in one of the rows. Their common neighbor, in contrast, can be arranged in numerous fashions, each of which displays perfect rectangularity: two rows of six, three rows of four, four rows of three, or six rows of two. (One might consider, in any case, that an arrangement of the primes in a single row of either eleven or thirteen elements is no longer necessarily two-dimensional, and that such an arrangement merely constitutes a spatial representation of the “one allowed” factorization of each prime, p x 1.) Similar representations of other primes, whether or not paired as twin primes, show the same result: not only are all primes, when so represented, irregular in any quasi-rectangular configuration, but in addition, each may be seen as a variant of a highly regular adjacent integer, 1 having been added or subtracted, and in so doing, its high degree of regularity having been completely disrupted.

AS/SA nº 14, p.81

One potentially fruitful avenue to investigate, in attempting to identify some arithmetical significance in the visual display of primes in this two-dimensional manner, appears therefore to be to examine the properties of those ‘highly rectangular’ numbers to which primes are adjacent. Such a line of investigation in fact reveals several significant observations.

Of Prime Numbers and ‘Prim’ Numbers

First among these observations is that prime numbers cannot occur adjacent to just any integer, nor even adjacent to any number having rectangular proportions in two dimensions: take 9 and 15, for example, which can be represented, respectively, as three rows of three and three rows of five. Neither of these two integers, however rectangular in two dimensions, has any prime numbers as neighbors (8 and 10 are composite, as are 14 and 16). An exhaustive investigation of such possibilities between 1 and 500 suggests that only certain regular, rectangular numbers, which I call ‘prim’ numbers because they are ‘prim and proper,’ or highly divisible, give prime numbers simply by the addition or subtraction of one. These may be loosely understood as those composite integers having the highest number of distinct factorizations in their immediate neighborhood. Further investigation reveals that the prim or most highly divisible numbers are the multiples of the factorials, 1.2.3, 1.2.3.4, 1.2.3.4.5, and so on. Thus we may regard the multiples of six as highly divisible and prim, the multiples of 24 as even more highly divisible and more prim, and so on with the multiples of 120, 720, 5040, etc. My observation is that the primes are deprived of factors by prims. In other words, a graph of n vs the number of its factor pairs (other than n x 1) reveals an undulating relation, on which there are regular maxima: these maxima are at the ‘prim’ numbers: those divisible by a high proportion of inferior integers, including 1, 2 and 3 (for small n, adding further factors according to the factorial series as n increases). (see Figure 3).

AS/SA nº 14, p.82

This exercise has been carried out for the first several hundred integers (see appendix). Yet even in so brief an investigation, it becomes clear, furthermore, that ‘prim’ numbers do indeed occur at every multiple of six (as well as every multiple of 24, 120 etc., obviously) (represented here as yellow), and more interestingly, (pink) primes only occur at n ±1, or one integer from prim numbers. The data imply that this rule must apply for all primes. ¹ However, without yet attempting a proof, let us look for confirmation through the following thought experiment as evidence in its support.

A ‘Displacement Principle’

Why is it that integers having a maximum number of factors are immediately adjacent to integers with a minimum of whole factors? Clearly, if a prim number n_prim is divisible by an integer factor greater than one, f, then the next occurrence of an integer that is also evenly divisible by f occurs at n_prim +f. Similarly, the nearest integer inferior to n that is evenly divisible by f must prim occur at n_prim -f. This means that adding or subtracting an integer less than f is never sufficient to prim reach a new integer that is also divisible by f. Therefore, a hypothetical prim number n having as its factors all or nearly all imaginable inferior integers as factors, must be adjacent to a pair of numbers, n_prim +1 and n_prim -1, that have no factors, or a greatly reduced number of factors for that order of magnitude. Thus it is not surprising that the most highly divisible integers, the multiples of 6 (which incidentally make up the Assyrian and Babylonian systems for measuring time and angles that we inherited in the West) are adjacent to each and every occurrence of prime numbers greater than three. Stated otherwise, all integers adjacent to prims like multiples of 6 have zero factors and are therefore prime, unless by mechanical ‘providence’ they themselves have a prime by which they are divisible. All numbers in this particular n±1 position either have zero or very few non-trivial factors. Furthermore, this explains the role of the natural logarithm in the distribution of primes: Looking at the appendix, an extended version of figure three, illustrates how factors are distributed in the progression of natural numbers — first every second natural number is given a factor of two, and every third number from nine on is also given a factor, every fourth from sixteen on, etc., so we see that the probability of having factors and being composite increases precisely according to the terms of the factorials that make up e and the very basis of the 1/log(n) frequency of prime distribution at n. These are 1 + 1/1 + 1/1x2 + 1/1x2x3 + 1/1x2x3x4 and so on.

AS/SA nº 14, p.83

A Modulus-6 Clock Spiral

The prim number conjecture appears to be further strengthened by what I propose as a possibly clearer alternative to Ulam’s checkerboard-type square spiral: a clock-like spiral in which the integers are positioned according to a modulus-6 pattern (see Figure 4).

AS/SA nº 14, p.84

In which cases are the candidates for primeness suggested by this model, those integers either 1 less or 1 greater than multiples of six, not prime? Again, the answer, which leads to a slightly better simplified algorithm for the computation of primes, is elementary: if such a candidate, n_prim ±1, is not prime, then it is composite, and can therefore be written as the product of two primes. Furthermore, one of these two factors must be less than its square root, the other greater, unless they are equal to each other and are the square root of that candidate. Therefore, one need only eliminate as factors, in a variant kind of sieve, those prime numbers and near-primes less than or equal to a candidates’ square root. If none of these divides evenly, there are no factors (other than 1) and the candidate is indeed prime.

A Simpler Algorithm

To find all primes up to n, we therefore need only:

a) stop at each multiple of 6, m
b) consider m+1 and m-1 as candidates
c) test each candidate by dividing it by each prime ≤√m
d) conclude a candidate is prime if all such tests show a non-zero remainder.

Conclusion

The modulus-6 clock cycle reveals six simple series, the expression of which appears not only to prove that the conjecture that primes occur next to prims by reason of the displacement principle is valid, but seems also to offer new avenues for demonstrating the truth of the Riemann hypothesis and the Goldbach Conjecture (according to which any positive integer greater than 4 can be expressed as the sum of two primes). This was simplified and written by Euler as p + q = 2n, where p and q are primes. It also illustrates graphically the manner in which primes are created by the addition or subtraction of one from certain integers, which is the actual cause of the phenomenon that primes often occur in pairs. (This also implies that 3 and 5 are not paired primes in the same sense, though 5 and 7 are.)

An attempt at a proof of the Golbach conjecture might go as follows, based on properties of the modulus-6 spiral above, and upon the distribution of the non-primes among the two series on which all primes occur:

Adding any two primes in the five o'clock series gives an even integer in the four o'clock series, because adding two primes for which p,q mod6 = 5 must give a sum (10)mod6 = 4.

Adding any two primes in the seven o'clock series must give an even integer in the two o'clock series, for the same reason in modular arithmetic: 1 mod6 + 1 mod6 = 2.

Adding one prime from the five and one from the seven o'clock series, according to modular arithmetic, must give an even integer for which mod6 = 0, meaning a multiple of six, because (5 + 1) mod6 =0.

Conversely, it can be demonstrated that each of the three even series on the spiral can be generated by some combination of two primes, either both in the five o'clock series, both in the seven o'clock series, or one in each, without exception, using simple modular arithemtic. Thus the modular arithmetic readily demonstrates how flawlessly, like a mechanical computation device based on wheels, the even numbers are constructed as sums of primes. I leave the formally correct proof to real mathematicians, however.

As to the Riemann hypothesis, it can be shown from the mechanical progession of factors in the table of appendix one that the probability of primness (having factors) increases, as I have mentioned, according to regular, modular terms that are constituted by the factorials whose product gives e and the probability distribution 1/log(n).

Another minor point is that these series have a minor accelerating effect on Eratsothene-type sieves: if such an algorithm is correct, it may reduce the number of calculations required to factor large encryption keys by a factor of 104. This is because not only is it simpler to compute primes in this way, but their factorization may be significantly aided by the knowledge that an encryption key that is the product of two primes is located on the clock spiral in a position determined by the locations of its two factors: two five-o’clock factors, or two one-o’clock factors, must give a product on the one o’clock series, whereas a five o’clock prime multiplied by a one o’clock prime necessarily has a product which lies within the five o’clock series. Too, the final decimal digit of an encryption key is related to the final digits of the two primes multiplied to generate it.

Perhaps the most useful aspect of the displacement principle and the concept of prim numbers is that they provide a conceptualization of primes and their distribution: every second natural number is given a factor of two, every third is given a factor of three, every fifth a factor of five, and so on, such that these cyclic factor attributions may be regarded, like wave phenomena, as moving in and out of phase with one another as they accumulate with increasing n. To me it is compelling that when these cycle are rather "out of phase," factors are distributed more or less evenly in that neighbourhood of natural numbers, whereas when they are more "in phase," a prim number is observed, having many factors, and the immediate neighbours of that prim number, by virtue of the displacement principle, are deprived of factors, and are frequently primes.

Finally, it would seem clear from figure 4 that Ulam's spiral displays a strikingly "non-random" appearance only insofar as it is essentially a geometric distortion of the highly regular modulus-6 spiral I have drawn. But to me the most interesting aspect of this way of looking at primes and their distribution is that it provides a simple and elegant way to grasp why certain numbers lack factors and a thus clear understanding of the nature of primes. That primes are created by displacement from regular prims except where excluded by the modular factorial cycles may be seen as an "organizing principle in the distribution of the succession of primes."

AS/SA nº 14, p.85

Notes

1. Except 2 and 3, which clearly belong to a different category of primes on their own. The primes greater than 3, which are infinite in number, all occur adjacent to multiples of six. Also regarding prim numbers, any multiples of numbers themselves composed of many common small factors are also ‘very prim.’ For instance, multiples of both 3 and 4, meaning multiples of 12, are very prim, as are multiples of both 4 and 5, or of 20. Such numbers often occur on the ‘other side’ of a prime, with the multiple of six on the ‘first side.’ Further, although it has been observed in ancient Greek times that primes greater than 3 are all of the form 6n +/- 1, this appears not to have been explained by the highly divisible property of the multiples of six, and modular arithmetic, while frequently applied to the study of primes, does not appear to have been fully exploited to describe the orderliness of the primes, otherwise the Ulam sprial would likely not be a subject of such discussion in the literature (and nor would the Euler 41-400 square spiral). [Return 1]

Appendix:

Spreadsheet File: PrimeAnalysis.xls

Works Cited

Collective (2004). Encylopædia Britannica, “Elementary Number Theory” (from “Number Theory”), Britannica, London.

Peterson, Ivars (2002). “Prime Spirals,” Science News online, avail. http://www.sciencenews.org/20020504/mathtrek.asp

Stein, M.L., S.M. Ulam, and M.B. Wells (1964). “A visual display of some properties of the distribution of primes.” American Mathematical Monthly 71(May):516-520.

Observations on the Regularity of Prime Number Distribution

Peter Marteinson