18
$\begingroup$

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 10 positive 4-digit numbers that can be read across, down or diagonally (from top to bottom).

$\endgroup$
  • 3
    $\begingroup$ Can any of these 4 digit numbers have leading zeros? $\endgroup$ – Brandon_J Apr 26 at 2:05
  • 4
    $\begingroup$ Leading 0´s are allowed but all 10 4-digit numbers involved must be positive other wise solution is trivial: a row of 0´s. $\endgroup$ – Bernardo Recamán Santos Apr 26 at 2:08
  • 2
    $\begingroup$ @BernardoRecamánSantos Do you know if there is an actual solution or not? $\endgroup$ – Ian Miller Apr 28 at 15:49
  • 1
    $\begingroup$ @BernardoRecamánSantos what makes you conject that there is a solution with 25 primes? Why not 24, or 26? What is the largest you have found? $\endgroup$ – Weather Vane Apr 28 at 17:47
  • 2
    $\begingroup$ I was meaning why should the number 100 (and hence 25 primes) related to the 4x4 grid? Why not ask that all primes less than 1000 fit into the grid... $\endgroup$ – Ian Miller Apr 29 at 6:17
13
+50
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Do you think this is likely to be optimal? How did you find it? $\endgroup$ – Dr Xorile Apr 26 at 16:49
  • $\begingroup$ @DrXorile by using a C program to permute. It is not reasonable to check every possible permutation so I have made some efficiencies, and I keep finding one more solution. For example, I never use an even number in the right-hand column, because there is better than 50% chance there is one along the bottom. The OP doesn't say if there is a solution which contains all 25 primes as factors. $\endgroup$ – Weather Vane Apr 26 at 17:00
  • $\begingroup$ Sounds like a good approach. Definitely intractable to do an exhaustive search ($10^{16}$). I was trying with bigger numbers first along the top and left (under the vague intuition that bigger numbers have more factors). So far, though, I've only got to 21 ([[9, 8, 8, 9], [8, 9, 1, 8], [7, 7, 6, 0], [9, 9, 5, 4]]). $\endgroup$ – Dr Xorile Apr 26 at 21:11
  • $\begingroup$ If no optimal solution exists, I think it will be really hard to prove it. So far I have found an alternate board with 21 primes [3, 5, 7, 0], [5, 6, 0, 9], [9, 8, 8, 9], [9, 1, 1, 6]. $\endgroup$ – Jay Apr 27 at 8:54
  • 1
    $\begingroup$ @DrXorile I have added some details of how I worked, but can't find a better solution. $\endgroup$ – Weather Vane Apr 27 at 15:22
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I have found 26 solutions with 23 primes, and not all of yours. Strangely I have two solutions with the first line 3337 and two with the first line 9447. $\endgroup$ – Weather Vane Apr 28 at 6:39
  • $\begingroup$ 23 does appear to be a wall. I had started looking at which primes were often missing but there wasn't any particular strong candidates. $\endgroup$ – Ian Miller Apr 28 at 6:42
  • $\begingroup$ @IanMiller Of all solutions with 23 primes found so far, which has the least product for the two missing primes? This information would give us some idea of how much space there is for improvement. $\endgroup$ – Bernardo Recamán Santos Apr 29 at 14:20
  • $\begingroup$ None are particularly more common than others. Based on the 23 prime answers I've found so far the most common primes not to be include are: 73 (missing in 10.5%), 79 (missing in 9.6%), 83 (missing in 9.6%), 67 (missing in 7.9%, 47 (missing in 6.1%), 29 (missing in 5.3%), 43 (missing in 5.3%), 71 (missing in 5.3%), 89 (missing in 5.3%). I found examples with nearly every prime missing out of the 25 (no examples missing 2 or 3 or 7). $\endgroup$ – Ian Miller Apr 29 at 14:58
5
$\begingroup$

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.

$\endgroup$
  • 5
    $\begingroup$ I too don't think it is worth posting more than one solution for 23 when the target is 25 primes. I did some preliminary computation too, for example an integer, for each number, with a bit for each prime factor present. So I can OR those bit patterns for all the numbers used. Finally there is a lookup table for each bit pattern converting it back to "numer of primes", although in C there is probably an instrinsic function to do that. $\endgroup$ – Weather Vane Apr 28 at 19:58
  • 1
    $\begingroup$ I did basically the same preliminary calculations too - for each value from 1000 to 9999 create a bit mask for which primes actually divide it. E.g. one thousand divides by 2 & 5 (the first and third primes) so in binary it's mask is 101 while one thousand one divides by 7, 11 & 13 (the 4th, 5th & 6th primes) so in binary it's mask is 111000. This allowed me to do bitwise OR between all ten 4-digit numbers. Then count the number of 1 bits in the number which can be done by repeatedly calculating x = x & (x-1) while x>0 and count the number of loops. $\endgroup$ – Ian Miller Apr 29 at 12:30
  • $\begingroup$ I guess we're covering similar ground. The realization that the tenth root of the product of the first 25 primes is around 5000 meant that the maximum number of wasted factors across all 10 numbers is about 1000. So I tried to narrow my search space using that. My confidence that there are no solutions with 25 primes is growing. $\endgroup$ – Dr Xorile Apr 29 at 16:00
  • 1
    $\begingroup$ Great update. You've systematically covered the vast majority of possible solutions and I agree if an answer with 24+ primes exists it is an extreme edge case. $\endgroup$ – Ian Miller May 1 at 4:48
  • $\begingroup$ I would have liked to award bounty to both Dr Xorile and Ian Miller for their prodigious efforts in trying to reach 24+ primes. Now, I too am almost convinced that 23 is best possible. $\endgroup$ – Bernardo Recamán Santos May 4 at 1:11
5
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Just 9 out of 25 possible primes divide your 10 numbers. $\endgroup$ – Bernardo Recamán Santos Apr 26 at 2:34
  • 2
    $\begingroup$ Ah I see I may have misinterpreted the question. I will leave this answer and edit the number. $\endgroup$ – Jay Apr 26 at 2:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.