Primes less than 100 in a 4 x 4 board

Question

Place one of the digits (0 to 9) in each of the cells of a 4 x 4 board so that as many as possible of the 25 primes less than 100 divide at least one of the 10 positive 4-digit numbers that can be read across, down or diagonally (from top to bottom).

Answer 1

Summary:

Following my previous answer, I tried a different approach:

The are 10 numbers in the puzzle grid — 4 rows, 4 columns, 2 diagonals. I decided to examine a list of 10 numbers in the range 2..9999 to see which contain all the 25 lowest prime factors (without considering the grid intersections), and see what I can ascertain.

At first I asked myself if it is even possible to make a list which contains all the 25 lowest primes. For example, one naive arrangement of the products (less than 10000) of successive primes is

2310: 2  3  5  7 11
3315: 13 15 17
0437: 19 23
0899: 29 31
1517: 37 41
2021: 43 47
3127: 53 59
4087: 61 67
5183: 71 73
6557: 79 83
8633: 89 97

As can be seen, this takes 11 rows, too many.

Permuting 10 numbers is far more daunting than permuting the 4 numbers for the main puzzle, where the other 6 numbers are formed from the intersections, and I could not cover all the combinations. But when I restricted the data to one occurrence of each of the 25 primes, it was easy to find very many 10-number solutions, such as

9870:  2  3  5  7  47
9911: 11 17 53
9269: 13 23 31
0551: 19 29
1517: 37 41
2537: 43 59
4087: 61 67
5183: 71 73
6557: 79 83
8683: 89 97

When I allowed primes to be duplicated, I also found solutions, but not so many. In the above example rows 4, 5, 6 and 7 can be multiplied by the already used $7$, $5$, $3$, and $2$ respectively and still have a product less than 10000.

I also noticed that none of the combinations found has any number which is a single prime (although there might be).

To solve the puzzle, I needed to restrict the number base permuted over the four rows. So I limited the number base to one occurrence of any prime anywhere in the four row numbers, with each number to contain at least two prime factors. Leaving six other numbers to duplicate the primes, and/or have a single prime factor.

That put 5470 numbers into each of the four rows. But it's impossible to permute $5470^4$ items even when the computer code for the bottom row is doing no work at all on each number.

The key is to have the inner loops/recursions do as little work as possible, which I achieved by building a new list for each row, from the previous row's list, excluding any numbers with prime factors already used.

Then, because of the decreasing list length for each row, it was possible to do an exhaustive search of all the permutations, within these constraints, which took about 30 hours.

Result: the maximum number of distinct prime factors found was 23.

But to summarise, this assumes that any single-prime number, and any duplicated prime, can be found in the other six numbers obtained from the grid.

---

Previously answered:

My best so far is (edit #2)

23 primes

  4  1  8  9
  3  5  5  3
  4  4  5  3
  5  1  4  1

 4189: 59 71
 3553: 11 17 19
 4453: 61 73
 5141: 53 97
 4345: 5  11 79
 1541: 23 67
 8554: 2  7  13 47
 9331: 7  31 43
 4551: 3  37 41
 9545: 5  23 83

 23 primes:
 2 3 5 7 11 13 17 19 23 31 37 41 43 47 53 59 61 67 71 73 79 83 97

---

Update:

Currently I ended up with at least three $62$ solutions using 23 primes.

Obviously the exhaustive method is not reasonable.

I did this by permuting the primes as factors for each row (in various ways), without repeating any prime on another row, although in some variants I used a prime more than once in a row. I then checked the columns and diagonals that were formed.

I did not permute (various choices of) the low-valued primes, especially 2, in the expectation they would be found in the columns and diagonals.

I later tried a second method which was in two stages. I permuted the three corners of a triangle with one row, one column, and one diagonal, like this

 X  .  .  X
 .  .  .  .
 .  .  .  .
 X  .  .  .

and permuted the three pairs in between, like this

 X  r  r  X
 c  .  d  .
 c  d  .  .
 X  .  .  .

and exhaustively checked out the most primes used, which was 11, having 1328 such solutions. That only left 7 cells to permute exhaustively, which took just a few minutes. But sadly, the best solution was only 22 primes used (13 solutions).

For 10 primes in the triangle there were 661323 permutations, so it was unfeasible to try.

I could have tried three more variants, based on the three other corners, but unlike other methods this didn't even find any 23-prime solutions.

Answer 2

Using a Monte-Carlo simulation I have been able to find many solutions involving 23 out of the 25 factors (same as @Weather Vane). This has run for over a day so I'm not hopefully of this method improving as 23 is findable fairly quickly.

Below is an answer using the first 23 primes: 2 up to 83.

  Using first 23 primes:
  7548
  8569
  6665
  2117
  Alternate using first 23 primes:
  3212
  5795
  5117
  1443

I have some 70+ other solutions using 23 out of the first 25 primes. I have found none using 24 out of the first 25 primes and none using all the first 25 primes.

Answer 3

I decided to try a slightly different approach. The key is obviously to reduce the search space in an efficient way. My method found a solution with 23 primes within about a minute (which probably means people using C or something could find it even quicker):

23 primes

  8366
  9455
  8541
  7199
 Missing Factors: {67, 97}

I still have it running so will update if I find something better than 23, but so far I have not... I've found a few more with 23 but I'll just show the one for now unless there's demand.

The basic method (which has not yet proven better than other methods already used, but is at least equal) is as follows:

1. I go through all the numbers from 1 to 9999 and precompute the factorization.
2. Anything with a "wasted factor" of more than 50 is discarded (defined below).
3. Anything kept is saved in a bunch of lists. For example, (9456) would be saved in (9***, 9**6, *4*6, ...).

This approach allows me to build up promising matrices.

For example:

1. I first find a first row by looking at the **** list (anything is allowed).
2. Then I find a first column by looking at R***, where R is the first value in the first row. I also check how many primes I've got covered and give up if it's too few (less than 5 is the current scenario).
3. Then I find a diagonal by looking at the R**C where R is the last value of the first row and C is the last value of the first column. I also give up if I've got less than 7 primes covered.

Etc. I build up to a point where I can quickly check the last 100 values or so and see how we've done.

What's a wasted factor? Well, if the power is more than 1 then all those extras are wasted. And if a prime is more than 100 then it's wasted too. The total wasted factor you can afford is about 1000. So my approach would allow $2*7^3$ (wasted factor of 49) and $2^6$. Obviously, there are a number of parameters one can tweak to adjust the search space.

---

Update: I ran the script through with the following parameters:

1. Discard anything with a wasted factor of more than 50. So there are 3386 numbers that we consider.
2. Try each of those in the first row providing it gives us a coverage of at least 2 of the 25 primes.
3. Try each of the valid first columns (ie same first digit as the first row) providing it gives us a cumulative coverage of at least 4 of the 25 primes.
4. Try each of the valid TR-BL diagonals providing it gives us a cumulative coverage of at least 6 of the 25 primes.
5. Try each of the valid second rows provided it gives us a cumulative coverage of at least 9 of the 25 primes.
6. Try each of the valid second columns provided it gives us a cumulative coverage of at least 12 of the 25 primes.
7. Try each of the valid third rows provided it gives us a cumulative coverage of at least 15 of the 25 primes.
8. Try all 100 possible remaining values (there are two digits missing which account for the TL-BR diagonal, the fourth row and the third and fourth column).

With even this relatively generous search space the best solution involved 23 primes. If there is a solution it's in a weird niche, for example, with one of the numbers having a large wasted factor and all the other ones neatly and perfectly covering the remaining primes. I would say this is extremely doubtful.

Answer 4

I've run an exhaustive search over the whole space for grids with 24 or 25 primes, and unless there's an error in my logic, the maximum is

23

My approach was to first take the top row, then the leftmost column, and use those values along with the excess from the numbers held to try to close the gap between the maximal product of the numbers in the grid and the product of the primes as quickly as possible.

For instance, if we have the following after 2 choices:

3589
1---
5---
4---

we know that we can close the gap according to the values we have. The second row will never have a value that exceeds 1999, the third will never exceed 5999, etc. Along with dividing by the redundant factors, this turns out to be very useful for pruning the search space quite quickly.

I also tried to preprocess as much as possible to avoid repeated computations.

Here's the Java file:

https://pastebin.com/2rmCV9sW

This takes about 29 minutes to run on my machine for the 24 case (and around 1:30 for the 25 case).

I also ran it for the 23 case, the following is the full list (147 grids all up):

https://pastebin.com/GNvfUxKn

That list should be exhaustive. Please let me know if you find anything with 23 primes that's not on the list, because that would imply an error/oversight on my part.

Answer 5

Kicking it off with a score of 38. Actually 9 unique primes.

9 2 8 2
2 1 9 0
8 9 7 0
2 0 0 2

Calculating the score

9282 (2, 3, 7, 13, 17) = 5 x2
2190 (2, 3, 5, 73) = 4 x2
8970 (2, 3, 5, 13, 23) = 5 x2
2002 (2, 7, 11, 13) = 4 x2
9172 (2) = 1
2992 (2) = 1

Total 38
Primes used (2, 3, 5, 7, 11, 13, 17, 23, 73) = 9