Primes, Spirals and Coffee Tables
Vector 11:4, page 104
Transcribed from the printed issue; not yet reviewed. Read it in the PDF of the issue, page 104
Algorithms in J for generating prime numbers are discussed and then used to construct square and rectangular spirals of primes which may be used in the design of a tiled top for a coffee table.
Primes¶
Prime numbers may be found by using a sieving method which is attributed to Eratosthenes, the Greek mathematician, astronomer and geographer of the third century B.C. who estimated the circumference of the earth and the distance from the earth to the moon and the sun. To find all primes less than or equal to 1000, say, write down in order the positive integers from 2 to 1000, and then cross out all multiples of 2, then all remaining multiples of 3, all remaining multiples of 5, etc. until no more integers may be crossed out. (It is not necessary to use divisors greater than 31 since the square root of 1000 is 31.6.) Those integers remaining are the required primes. Two simple methods which exploit features of APL and J for implementing this sieving process are due to Kenneth Iverson. The first method is based on the observation that the only two divisors of any prime number are itself and unity. The sieve may generated by first finding the residue table with a list of positive integers as each argument and then creating a list of 0s and 1s with the 1s corresponding to those columns of the table indicating exactly two divisors. This sieve may be expressed in J as
where
gives the positive integers, and, for example, ResidueSieve 10 is 0 1 1 0 1 0 1 0 0 0.
A list of prime numbers is given by
The second sieve is
since the primes do not occur in a multiplication table for the integers. A corresponding verb for prime numbers is
Approximate times using a 33-megahertz 486 to generate all primes less than or equal to 750 were 9.2 seconds using Pr1 and 429 seconds using Pr2.
The residue sieve may be made more efficient by using as arguments in the residue table a list from which all even integers greater than 2 have been eliminated. Such a list is given by
where
and, for example, PN 10 is 1 2 3 5 7 9. Therefore, the sieve is:
and the primes verb is
The expression Primes 750 was executed in approximately 1.4 seconds.
Spirals¶
Some interesting problems, originating with the American mathematician Stanislaw Ulam and described by Martin Gardner in Scientific American, are suggested when the positive integers are arranged in a spiral and the primes marked. It was found that the primes seemed to occur in series of straight lines. Ulam and his colleagues at Los Alamos studied these patterns extensively using spirals of up to approximately the first 65000 positive integers. In this section, however, we shall be concerned only with the description of a simple recursive algorithm for the construction of square and rectangular spirals of integers.
A spiral of positive integers may be considered to be a list of integers equally spaced along a length of string that is to be wound onto a stick of zero width and of a length determined by the difference between the length and width of the completed spiral. The left side of the figure given at the end of the paper shows the step-by-step construction of a spiral of the first fifteen positive integers with five rows and three columns. The verb
is used to repeatedly rotate the partially completed table of integers counter-clockwise through ninety degrees and append another row of integers on the top. This method of constructing a spiral may be simply expressed by the recursive verb
where
gives the number of rows in its table argument. Spirals of arbitrary dimension are given by
and for convenience square spirals by
The spiral of primes may be displayed by
which gives a logical table in which the primes are represented by 1s. The figure shows the use of the last three verbs.
Coffee Tables¶
A spiral of primes gives a pleasing design for a tiled top of a coffee table with tiles corresponding to prime integers in one colour, tiles corresponding to composite integers in another colour, and the tile corresponding to the integer 1 in a third colour. Since the tiles would be laid down row by row or column by column beginning at one corner, it is convenient to have some guide to the coordinates of the tiles and the corresponding integers. The verb
where
gives the coordinates, displays the coordinates together with the corresponding integers as a table of triples. The verb
gives a similar display with the primes and composite integers shown as 1s and 0s, respectively. The figure gives examples of the use of these two verbs.
Keith Smillie
Department of Computing Science,
University of Alberta, Edmonton,
Alberta T6G 2H1, Canada
References¶
Gardner, M., 1971. Martin Gardner’s 6th Book Of Mathematical Diversions from "Scientific American". The University of Chicago Press, Chicago.
Iverson, K. E., 1972. APL in Exposition. IBM Philadelphia Scientific Center Technical Report No. 320-3010. IBM Corporation, Philadelphia, Penn.
Iverson, K. E., 1993. J Introduction & Dictionary. Iverson Software Inc., Toronto, Ontario.
]s=. i. 2 0
]s=. 1 2 QtrTurn s
1 2
]s=. 3 QtrTurn s
3
2
1
]s=. 4 5 6 QtrTurn s
4 5 6
3 2 1
]s=. 7 8 QtrTurn s
7 8
6 1
5 2
4 3
]s=. 9 10 11 12 QtrTurn s
9 10 11 12
8 1 2 3
7 6 5 4
]s=. 13 14 15 QtrTurn s
13 14 15
12 3 4
11 2 5
10 1 6
9 8 7
s e. Primes 15
1 0 0
0 1 0
1 1 1
0 0 0
0 0 1
Spiral 5 3
13 14 15
12 3 4
11 2 5
10 1 6
9 8 7
SquareSpiral 5
21 22 23 24 25
20 7 8 9 10
19 6 1 2 11
18 5 4 3 12
17 16 15 14 13
(SpiralOfPrimes &.>) 5 3;5 5
┌─────┬─────────┐
│1 0 0│0 0 1 0 0│
│0 1 0│0 1 0 0 0│
│1 1 1│1 0 0 1 1│
│0 0 0│0 1 0 1 0│
│0 0 1│1 0 0 0 1│
└─────┴─────────┘
TopIntegers 5 3
┌──────┬──────┬──────┐
│4 0 13│4 1 14│4 2 15│
├──────┼──────┼──────┤
│3 0 12│3 1 3 │3 2 4 │
├──────┼──────┼──────┤
│2 0 11│2 1 2 │2 2 5 │
├──────┼──────┼──────┤
│1 0 10│1 1 1 │1 2 6 │
├──────┼──────┼──────┤
│0 0 9 │0 1 8 │0 2 7 │
└──────┴──────┴──────┘
TopPrimes 5 3
┌─────┬─────┬─────┐
│4 0 1│4 1 0│4 2 0│
├─────┼─────┼─────┤
│3 0 0│3 1 1│3 2 0│
├─────┼─────┼─────┤
│2 0 1│2 1 1│2 2 1│
├─────┼─────┼─────┤
│1 0 0│1 1 0│1 2 0│
├─────┼─────┼─────┤
│0 0 0│0 1 0│0 2 1│
└─────┴─────┴─────┘
Prime Spirals