Let
the minimum such
. I came up with the following upper bound:
with the following solution to the puzzle
If we inspect this table, we see that it satisfies the conditions for divisibility and the upper bound is correct. Now, if a prime
appears explicitly in the table, its neighbors must be divisible by that prime. If the prime appears in the interior, its neighbors must be at least the sizes
. If it appears on an edge, the neighbors are at least
. If it appears in a corner the neighbors are at least
. Using the lowest of these upper bounds
, in an optimal solution we must have that
, or
. That is, the only explicit primes in this table are at most
and
. No other primes can appear explicitly in the table. As we can see, up to 26, the only numbers that do not appear in this table are
and
. Since these numbers are not allowed in an optimal solution, the solution I provided must be optimal. Therefore
.