Rectangular arrays

1 William Poundstone: "Labyrinths of Reason -- Paradox, Puzzles and the Frailty of Knowledge", Anchor Press, New York, 1988, in chapter on "NP-Completeness" on page 177.

2 Sir Thomas Heath: "A History of Greek Mathematics", Clarendon Press, Oxford, 1921, edition consulted Dover, New York, 1981, Volume 2, page 104.

3 Apollonius’ life dates are not known, but he was famous as an astronomer under Ptolemy Philopator (222 to 205 BCE). See Heath: "A History of Greek Mathematics", op. cit., Volume 2, page 126.

Picture credit: Seven- circuit Labyrinth of Cretan type redrawn from Jeff Saward's Caerdroia Journal -- see our "useful Links" page.

Volume 1: Patterns of prime distribution

in "polygonal - number pyramids"

You are on page	Rectangular arrays
0 1 2 3 4 5 6 7 8 + 10 11 12 13 14 15 16 17 18
	A maze’s solution is much, much simpler than the maze itself, (...) and it is easily verified.¹

1.1. The misleading prime number sieve of Eratosthenes

Many mathematicians, and other people curious about numbers, have long searched for patterns in the distribution of primes, that is, those whole numbers which can be evenly divided only by themselves and by one, and which seem to pop up randomly among the more frequent non- prime or composite numbers.

The problem dates back at least to Eratosthenes of Cyrene (280 to 194 BCE), the acclaimed scholar and head of the Library at Alexandria in Egypt who wrote the first surviving description of the sieve for prime numbers now named after him.

In proposing this sieve, or method for locating the primes, Eratosthenes may have lived up to his reputation of being the "beta" expert in each of his many erudite pursuits, that is, the next best to the first or "alpha" specialists in those subjects².

His sieve hides the order inherent among the primes, whereas some other simple methods for arranging the sequence of numbers display a series of organized visual patterns formed by primes which you will see described here. Moreover, the circumstantial evidence I will present in the second Volume of this book suggests that the leading mathematicians of his host country may have known some of these number- inherent and orderly patterns long before he was born.

The method Eratosthenes used to weed out non- prime numbers is still the only practical one known, and it forms the basis of all modern sieve theory : list the numbers up to an arbitrarily chosen target square, then cross out the successive multiples of all the primes up to the root of that square.

The entries that remain are not multiples of those only factors that would be small enough to produce them if they were multiplied with any of the other not- crossed- out numbers which are all larger than that square root. These left-over entries are therefore primes.

However, that method and its simple logic are so obvious to anyone experimenting with multiplication and its reversal that it can hardly be this latecomer’s invention.

By then, people had been multiplying and dividing and studying numbers for thousands of years, and whoever marks the multiples of the successive primes among, say, the first hundred numbers, notices quickly that all the multiples of eleven and up in that set are already tagged as multiples of smaller numbers.

	Figure 1: Some square "Sieves of Eratosthenes" with primes and other special numbers marked
Gif = 31 Kb	View vector version 65 Kb
Each square array re-arranges the primes differently. The prime-free diagonal stripes in the squares of odd side-length 3n ± 1 are caused by the odd multiples of three and each one's two even neighbors.

The contribution more credibly associated with Eratosthenes is the arrangement of the so weeded number patch in the form of a square sieve.

To construct this sieve, one chops up the line of natural numbers into stretches as long as the root of the limiting square, then stacks these line segments in consecutive layers one number-space high so that they form a square array, as illustrated in Figure 1 above.

This array has often been used as a visual demonstration that primes occur in no discernible order, and it may not be the best way of writing the numbers for studying patterns formed by primes.

However, it illustrates one of the reasons why Eratosthenes’ contemporaries may have honored him with that high ranking, right next to the luminaries of his time. These included his friend Archimedes of Syracuse (287 to 212 BCE) who was one of the few outstanding giants among the many great mathematicians whose name and work survive. There was also his longtime co- Alexandrinian Apollonius of Perga (262 to 190 BCE³) whose systematic study of the conic sections and their tangents is still the mathematical foundation of modern astronomy and space travel. Coming in second to these was no mean feat.

Square arrays led to rectangular ones, and these are very useful tools for the arithmetic of residue classes which deals with the remainders left over from dividing a number by the width of a rectangular array. Those remainders are a convenient way to organize all the infinitely many numbers into as few categories as the array has columns.

All numbers with the same remainder share the same column in such an array. Often they have other traits in common, too, beginning with the two- column separation into odd and even, and with the ten- wide array of our decimal system where the members of each column have always the same last digit. Similarly, our seven- day week is a rectangular array that counts the days left over since the last completed multiple of seven.

	Figure 2: Rectangular arrays four and six units wide, and the distribution of primes into only two of their columns
Gif = 34 Kb	View vector version 170 Kb
Each row of numbers continues here before and behind the framed array of limited width. This shows the continuity of the parabolae which the polygonal numbers, such as triangular numbers, squares, etc., describe in this arrangement. The six-wide array lines up all twin-prime centers into a single column. It also highlights that triangular numbers and real squares do not occur in the columns 6n - 1 or 6n + 2, just as the columns 4n - 1 and 4n + 2 contain no squares.

Rectangular arrays have also contributed much to the study of primes. For instance, as Figure 2 illustrates, arrays four and six units wide each sort the primes above 2 and 3 into only two of their columns, those of the forms 4n ± 1 and 6n ± 1 which each have distinctive properties.

The six-wide array supplies also a simple visual proof that all twin prime centers above 4 are multiples of six because all entries in the only other odd column 6n ± 3 are divisible by 3 and can thus not contain the prime needed next to a twin prime center on either side.

1.2. Proving the twin prime conjecture

The six- wide array further helps to demonstrate the otherwise still unproven conjecture that there must be infinitely many twin primes, that is ...

Continue

Return to navigation bar ¦ Back to top ¦ About us
Our Privacy Policy ¦ Useful Links ¦ Rebranding