Prime Array

Find the 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 the array, 11 primes are maximal and are contained in the two distinct arrays

(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 array is

(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, ... (Sloane's 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).

The best arrays known 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 array.

The best prime arrays known 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.

The best prime arrays known 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 contain 187 primes. One was found by S. C. Root, and the others by M. Oswald in 1998.

The best prime array known 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.

The best prime array known 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.

The best prime array known 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 contain 527 primes and was found by Gary Hertel.

Heuristic arguments by Rivera and Ayala suggest that the maximum possible number of primes in , , and arrays are 58-63, 112-121, and 205-218, respectively. It is believed that all arrays up to are now optimal (J.-C. Meyrignac, pers. comm., Sep. 19, 2005), giving the maximal numbers of primes for the array for , 2, ... as 1, 11, 30, 63, 116, 187, and 281 (Sloane's A109943).