Prime Array

Find the $m\times n$ Array of single digits which contains the maximum possible number of Primes, where allowable Primes may lie along any horizontal, vertical, or diagonal line. For $m=n=2$, 11 Primes are maximal and are contained in the two distinct arrays

$$A(2,2)=\left[{\matrix{1 & 3\cr 4 & 7\cr}}\right], \left[{\matrix{1 & 3\cr 7 & 9\cr}}\right],$$

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. For the $3\times 2$ array, 18 Primes are maximal and are contained in the arrays

$$A(3,2) = \left[\begin{array}{ccc}1 & 1 & 3\\ 9 & 7 & 4\end{array}\right],... ...rray}\right], \left[\begin{array}{ccc}1 & 7 & 2\\ 4 & 3 & 9\end{array}\right],$$

$$\phantom{=} \left[\begin{array}{ccc}1 & 7 & 5\\ 4 & 3 & 9\end{array}\right],... ...rray}\right], \left[\begin{array}{ccc}1 & 7 & 9\\ 4 & 3 & 2\end{array}\right],$$

$$\phantom{=} \left[\begin{array}{ccc}1 & 7 & 9\\ 4 & 3 & 4\end{array}\right],... ...rray}\right], \left[\begin{array}{ccc}3 & 7 & 6\\ 4 & 1 & 9\end{array}\right].$$

The best $3\times 3$, $4\times 4$, and $5\times 5$ prime arrays known were found by C. Rivera and J. Ayala in 1998. They are

$$A(3,3)=\left[{\matrix{ 1 & 1 & 3\cr 7 & 5 & 4\cr 9 & 3 & 7\cr}}\right],$$

which contains 30 Primes,

$$A(4,4)=\left[{\matrix{ 1 & 1 & 3 & 9\cr 6 & 4 & 5 & 1\cr 7 & 3 & 9 & 7\cr 3 & 9 & 2 & 9\cr}}\right],$$

which contains 63 Primes, and

$$A(5,5)=\left[{\matrix{ 1 & 1 & 9 & 3 & 3\cr 9 & 9 & 5 & 6 & ... ...& 1 & 7\cr 3 & 3 & 7 & 3 & 1\cr 3 & 2 & 9 & 3 & 9\cr}}\right],$$

which contains 116 Primes. S. C. Root found the a $6\times 6$ array containing 187 primes:

$$A(6,6)=\left[{\matrix{ 3 & 1 & 7 & 3 & 3 & 3\cr 9 & 9 & 5 & ... ...cr 3 & 4 & 9 & 1 & 9 & 9\cr 3 & 7 & 9 & 3 & 7 & 9\cr}}\right].$$

In 1998, M. Oswald found five new $6\times 6$ arrays with 187 primes:

$\quad\left[{\matrix{1 & 3 & 9 & 1 & 9 & 9\cr 3 & 1 & 7 & 2 & 3 & 4\cr 9 & 9 & 4... ...& 5 & 7 & 1 & 3\cr 9 & 8 & 3 & 6 & 1 & 7\cr 9 & 1 & 7 & 3 & 3 & 3\cr}}\right],$
$\quad\left[{\matrix{3 & 1 & 7 & 3 & 3 & 3\cr 9 & 9 & 5 & 6 & 3 & 9\cr 1 & 1 & 8... ...& 6 & 3 & 7 & 3\cr 3 & 4 & 9 & 1 & 9 & 9\cr 9 & 7 & 9 & 3 & 7 & 9\cr}}\right],$
$\quad\left[{\matrix{3 & 1 & 7 & 3 & 3 & 3\cr 9 & 9 & 5 & 6 & 3 & 9\cr 1 & 1 & 8... ... & 6 & 3 & 7 & 3\cr 3 & 4 & 9 & 1 & 9 & 9\cr 9 & 9 & 9 & 2 & 3 & 3\cr}}\right].$

Rivera and Ayala conjectured and Weisstein demonstrated by direct computation in May 1999 that the 30-prime solution for $A(3,3)$ is maximal and unique. Heuristic arguments by Rivera and Ayala suggest that the maximum possible number of primes in $4\times 4$, $5\times 5$, and $6\times 6$ arrays are 58-63, 112-121, and 205-218, respectively.

See also Array, Prime Arithmetic Progression, Prime Constellation, Prime String

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.'' http://www.geocities.com/MotorCity/7983/primesearch.html.

Rivera, C. ``Problems & Puzzles (Puzzles): The Gordon Lee Puzzle.'' http://www.sci.net.mx/~crivera/puzzles/puzz_001.htm.

Weisstein, E. W. ``Prime Arrays.'' Mathematica notebook PrimeArray.m.