Prime lights out

Question

You start with a 4x4 grid filled with zeroes. If you press a cell then the cell and all its neighboring (horizontally and vertically) cells will have their numbers increased by 1. What is the most number of distinct primes you can obtain?

Answer 1

Here is my solution:

All 16 cells are primes:

 Moves          Result
 117 51 50 30   173 223 179 101
 5   5  48 21   127 139 131 103
 0   30 7  4    59  79  107 83
 24  37 18 51   61  109 113 73

How I found this:

First I used light chasing to fill the top 3 rows with primes. That is to say, I did some nice large number of moves on the top row cells, and then on each subsequent row I did some mostly arbitrary moves to make the row above show distinct primes. The last row then contains numbers that are not necessarily prime or distinct.

 Moves          Result
 90 70 50 30    173 223 179 101
 13 13 29 21    127 139 131 103
 11 14 18 23    59  79  107 83
 21 23 23 21    55  81  85  67

To turn the bottom row into primes I added on the following patterns (the first pattern was added 3 times, the second pattern was added 14 times):

 Moves             Result
 -5  3  0  0    0  0  0  0
  2  2 -3  0    0  0  0  0
  1 -4  1  3    0  0  0  0
  1  0  3 -4    2  0  0  2

  3 -2  0  0    0  0  0  0
 -1 -1  2  0    0  0  0  0
 -1  2 -1 -2    0  0  0  0
  0  1 -1  3    0  2  2  0

These two patterns were found by pressing one button on the top row, and then using light chasing (allowing negative moves) to make the top three rows zero and see what the effect is on the bottom row. Linear combinations of these were then constructed to make them change only two of the bottom row numbers.

No doubt smaller solutions are possible. I started out using too few moves on the top row, and kept running into problems of duplicate primes, or negative numbers of moves. I then used a fairly large number of top row moves and hit upon this solution.

Answer 2

Via integer linear programming, the minimum number of moves turns out to be:

98

    Moves        Result
    2  8  9  4   11 23 43 13
    1  4 22  0    7 37 59 31
    0  2 24  5    3 47 53 29
    0 17  0  0   17 19 41  5

This same solution minimizes the largest prime.

---

By request, here's the SAS code I used:

proc optmodel;
   /* declare parameters */
   num n = 4;
   set ROWS = 1..n;
   set COLS = ROWS;
   set CELLS = ROWS cross COLS;
   set NEIGHBORHOOD {<i,j> in CELLS} = {<i2,j2> in CELLS: abs(i-i2) + abs(j-j2) <= 1};

   /* construct primes */
   num maxprime = 200;
   set COMPOSITES = union {i in 3..sqrt(maxprime) by 2} i*i..maxprime by 2*i;
   set PRIMES = {2} union (3..maxprime by 2 diff COMPOSITES);
   put PRIMES=;

   /* declare decision variables */
   var NumMoves {CELLS} >= 0 integer;
   var IsCellPrime {CELLS, PRIMES} binary;

   /* declare objective */
   min TotalNumMoves = sum {<i,j> in CELLS} NumMoves[i,j];

   /* declare constraints */
   con OnePrimePerCell {<i,j> in CELLS}:
      sum {p in PRIMES} IsCellPrime[i,j,p] = 1;
   con AtMostOneCellPerPrime {p in PRIMES}:
      sum {<i,j> in CELLS} IsCellPrime[i,j,p] <= 1;
   con Link {<i,j> in CELLS}:
      sum {<i2,j2> in NEIGHBORHOOD[i,j]} NumMoves[i2,j2] 
    = sum {p in PRIMES} p * IsCellPrime[i,j,p];

   /* call MILP solver */
   solve;

   /* print solution */
   print NumMoves;
   num sol {CELLS};
   for {<i,j> in CELLS} do;
      for {p in PRIMES: IsCellPrime[i,j,p].sol > 0.5} do;
         sol[i,j] = p;
         leave;
      end;
   end;
   print sol;
quit;

Answer 3

Here is my solution without doing any computation.

The following moves produce an "all-one" result:

 Moves          Result
 0 1 0 0        1 1 1 1
 0 0 0 1        1 1 1 1
 1 0 0 0        1 1 1 1
 0 0 1 0        1 1 1 1

The following moves produce an "all-different" result:

 Moves                  Result
 2^0  2^1  2^2  2^3     d_0  d_1  d_2  d_3
 2^4  2^5  2^6  2^7     d_4  d_5  d_6  d_7
 2^8  2^9  2^10 2^11    d_8  d_9  d_10 d_11
 2^12 2^13 2^14 2^15    d_12 d_13 d_14 d_15

The numbers $d_0, \dots, d_{15}$ are clearly all different, because of the binary number system.

Taking a positive linear combination of the previous two sets of moves, we can make the results of the form $a + md_0, a + md_1, \dots, a + md_{15}$ for any positive integers $a, m$.
Now we choose $a, m$ such that $a, a + m, \dots, a + md$ are all prime numbers, where $d = \max\{d_0, \dots, d_{15}\}$. The existence of such $a, m$ is guaranteed by the Green-Tao theorem.
Consequently, all the $a + md_i$ are distinct prime numbers.

Answer 4

Here is a solution with 12 primes. Cells with brackets have to be pressed as often as their number indicates. Other cells will not be pressed. Note that cells have to be pressed in a checkerboard pattern. Dotted cells contain even, non-prime numbers. I used a small program to find primes that are sums of three other primes.

 [ 3]  31  [23] ....
  37  [ 5] .... [19]
 [29] .... [13]  43
 .... [17]  41  [11]
 

With the idea of JLee, we can upgrade this to 13 primes:

  [ 3]  31  [23] ....
  .... [ 5] .... [29]
  [ 2]  37  [13]  53
   19  [17]  41  [11]