TOPICS
Search

Prime Array

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

A prime array is an m×n array of single decimal digits arranged to contain as many distinct primes as possible. Numbers are formed by reading one or more consecutive digits horizontally, vertically, or diagonally, in either direction along a straight line. Each prime is counted only once, even if it occurs in multiple positions.

For the 2×2 array, 11 primes are maximal and are contained, for example, in the two arrays

A(2,2)=[1 3; 4 7],[1 3; 7 9],
(1)

giving the primes (3, 7, 13, 17, 31, 37, 41, 43, 47, 71, 73) and (3, 7, 13, 17, 19, 31, 37, 71, 73, 79, 97), respectively.

The best 3×3 array is

A(3,3)=[1 1 3; 7 5 4; 9 3 7],
(2)

which contains 30 primes: 3, 5, 7, 11, 13, 17, 31, 37, 41, 43, 47, 53, 59, 71, 73, 79, 97, 113, 157, 179, ... (OEIS A032529). This array was found by Rivera and Ayala and shown by Weisstein in May 1999 to be maximal and unique (modulo reflection and rotation).

Examples of 4×4 prime arrays are

[1 1 3 9; 6 4 5 1; 7 3 9 7; 3 9 2 9], [1 1 3 9; 7 6 9 2; 5 4 7 9; 1 7 3 3], [1 7 3 3; 9 4 2 1; 6 5 9 1; 7 7 3 9], [3 1 6 7; 7 5 1 4; 9 2 9 3; 3 3 7 3]
(3)

all of which contain 63 primes. The first was found by C. Rivera and J. Ayala in 1998, and the other three by James Bonfield on April 13, 1999. Mike Oakes proved by computation that the 63 primes is optimal for the 4×4 array.

Examples of 5×5 prime arrays are

[1 1 9 3 3; 9 9 5 6 3; 8 9 4 1 7; 3 3 7 3 1; 3 2 9 3 9], [3 3 1 9 9; 8 3 9 1 1; 2 7 4 5 7; 1 9 6 7 3; 9 7 9 1 9]
(4)

each of which contains 116 primes. The first was found by C. Rivera and J. Ayala in 1998, and the second by Wilfred Whiteside on April 17, 1999.

Examples of 6×6 prime arrays are

[1 3 9 1 9 9; 3 1 7 2 3 4; 9 9 4 7 9 3; 9 1 5 7 1 3; 9 8 3 6 1 7; 9 1 7 3 3 3], [1 3 9 1 9 9; 9 1 7 2 3 4; 6 9 4 7 9 3; 7 1 5 7 1 3; 9 8 3 6 1 7; 9 1 7 3 3 3], [3 1 7 3 3 3; 9 9 5 6 3 9; 1 1 8 1 4 2; 1 3 6 3 7 3; 3 4 9 1 9 9; 3 7 9 3 7 9], [3 1 7 3 3 3; 9 9 5 6 3 9; 1 1 8 1 4 2; 1 3 6 3 7 3; 3 4 9 1 9 9; 3 7 9 9 3 9], [3 1 7 3 3 3; 9 9 5 6 3 9; 1 1 8 1 4 2; 1 3 6 3 7 3; 3 4 9 1 9 9; 9 7 9 3 7 9], [3 1 7 3 3 3; 9 9 5 6 3 9; 1 1 8 1 4 5; 1 3 6 3 7 3; 3 4 9 1 9 9; 9 9 9 2 3 3],
(5)

each of which contains 187 primes. One was found by S. C. Root, and the others by M. Oswald in 1998.

An example of a 7×7 prime array is

[3 1 3 7 3 3 9; 9 9 2 3 3 3 3; 6 9 7 7 8 9 4; 7 6 1 5 9 1 9; 7 7 3 4 2 1 1; 9 9 4 7 9 3 9; 3 3 7 1 9 9 9],
(6)

which contains 281 primes and was found by Wilfred Whiteside on April 29, 1999.

An example of an 8×8 prime array is

[1 3 1 7 3 3 8 9; 9 3 3 2 6 9 9 9; 9 1 2 3 7 7 5 7; 6 9 1 7 2 4 3 3; 7 9 5 1 1 9 3 3; 9 9 1 6 4 3 3 3; 1 3 7 3 3 9 3 1; 9 1 9 3 9 3 7 3],
(7)

which contains 394 primes and was found by Wilfred Whiteside in 2005 as a part of Al Zimmerman's programming contest.

An example of a 9×9 prime array is

[3 1 9 3 7 6 9 3 3; 7 9 5 1 7 3 9 3 3; 9 9 3 9 2 2 9 7 3; 3 6 1 5 1 1 8 9 7; 4 7 7 4 3 1 3 3 1; 9 9 9 7 7 3 9 9 9; 3 3 3 9 5 1 4 3 9; 9 3 9 6 1 9 6 1 3; 9 6 3 3 7 9 1 3 3],
(8)

which contains 527 primes and was found by Gary Hertel.

Early heuristic estimates by Rivera and Ayala suggested 58-63, 112-121, and 205-218 distinct primes for 4×4, 5×5, and 6×6 arrays, respectively. These estimates are not rigorous bounds. The best scores reported in 2005 for n×n arrays with n=1, 2, ..., 7 are 1, 11, 30, 63, 116, 187, 281 (OEIS A109943). The first four values are proved maxima, while the values for n=5, 6, and 7 are conjectured maxima (J.-C. Meyrignac, pers. comm., Sep. 19, 2005).

For the 2×3 rectangular array, 18 primes are maximal and are contained in the arrays

A(2,3)=[1 1 3; 9 7 4],[1 7 2; 3 5 9],[1 7 2; 4 3 9][1 7 5; 4 3 9],[1 7 9; 3 2 5],[1 7 9; 4 3 2][1 7 9; 4 3 5],[3 1 6; 4 7 9],[3 7 6; 4 1 9].
(9)
(10)

For the 3×4 rectangular array, 43 primes are maximal, and (modulo reflection and rotation) there are exactly 3 distinct solutions

[1 9 9 7; 1 5 4 6; 3 3 7 1],[1 9 9 7; 1 5 7 4; 3 6 1 3],[3 9 2 9; 4 1 5 7; 7 6 1 3]
(11)

as proved by Mike Oakes on Dec. 29, 2004 with a 12 GHz-hour computation.

See also

Array, Prime Arithmetic Progression, Prime Constellation, Prime Magic Square, Truncatable Prime

Explore with Wolfram|Alpha

References

Dewdney, A. K. "Computer Recreations: How to Pan for Primes in Numerical Gravel." Sci. Amer. 259, 120-123, July 1988.Lee, G. "Winners and Losers." Dragon User. May 1984.Lee, G. "Gordon's Paradoxically Perplexing Primesearch Puzzle." https://web.archive.org/web/20011117165915/http://www.geocities.com/MotorCity/7983/primesearch.html.Rivera, C. "Problems & Puzzles: Puzzle 001-The Gordon Lee Puzzle." https://www.primepuzzles.net/puzzles/puzz_001.htm.Sloane, N. J. A. Sequences A032529 and A109943 in "The On-Line Encyclopedia of Integer Sequences."Zimmermann, A. "Best Grids for Part 1 Found during the Contest." http://www.recmath.org/contest/BestSolutions1.php.

Referenced on Wolfram|Alpha

Prime Array

Cite this as:

Weisstein, Eric W. "Prime Array." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/PrimeArray.html

Subject classifications