Problems & Puzzles: Puzzles

Puzzle 388. Primes on a dice, again. Anton Vrba sent the following nice puzzle, cousin of the puzzle 367 Consider two cubes (dice) with a unique prime number on each face.  1. Can you construct such a pair such that by placing the two die next to each other in any order or combination, such that the concatenation of the two numbers is always prime? Note: The best solution sent by Anton produces 63/72 primes. 2. Question 1 requires 72 primes of 72 combinations, but if not possible can you better 63 of 72. 3. Relaxing the constraint that the die are constructed with prime numbers can you find a solution for 1.

---

Bernardo Boncompagni found a solution to Q2.

I found a solution which yields 68 primes:

die 1: 3 19 1237 104107 594193 23350801
die 2: 7 31 1657 79147 12492511 839204221

***

Carlos Rivera found one solution which yields 64 primes, for Q3:

1 3 19 33 57 87
7 17563 40453 36547 72079 85027

***

Bernardo Boncompagni found a 69 primes solution for Q3:

first die: 3, 9, 2859, 114817, 241657, 1604551
second die: 7, 37, 187, 13933, 86149, 161303413

***

On May 20-23, 2007, Wilfred Whiteside has gotten 92 almost-complete solutions (71/72) to Q2, on May 13, 2007. Here is one of them:

Soln with 71 primes found
3 19 1237 5746591 825704611 4161169807
7 31 79147 182467 798674809 852878413
Total of 12 faces = 6,644,437,142

Wilfred Whiteside has gotten 17 complete (72/72) solution to Q3 on May 20, 2007:

Soln with 72 primes found
3 9 159 442627 2788473 40111689
7 37 79009 86989 2120449 66293689
Sum of faces = 111,923,140
 

Finally he got one complete solution to Q1:

3 587 61487 5674049 906716033 17529092573
11 467 54401 868121 478942913 10890311651
Sum of faces = 29,811,722,296 (is this the smallest solution?, CR)
 

Used 2 cpu box to generate base pairs of perfect 5 sided die pairs (generating 50 primes).
One cpu worked on faces = 3 or 3 mod 1.  Other cpu worked on faces = 3 or 3 mod 2 faces.
These 5 face die pairs were then searched to find perfect 6,5 side die pairs
(60 primes).  These were distruted as work units, where each work unit searched a
particular 5x5 over a range of face values.

 

The perfect 6,5 side die pairs were then similarly searched as work units for the final
face value that would make a perfect 6x6 die pair. About 338 billion prime faces were
tested in this last phase before a 72 prime solution showed up.

 

The search for a 6x6 with non prime faces was done similarly, but used much less cpu.

 

Note: Code was not very efficient, each cpu generated its own primes to test against
   one particular pair of die.  5 Miller-Rabin tests were done on the fly with 50
   Millers used to verify final solutions 
 

 

Prime Faces case:

 

200 perfect 5x5s (50 primes) generated after 2 weeks on 2 cpus
 
171 perfect 6x5s (60 primes) generated after 1400 work units of 2 hours each - testing
each 5x5 up to 70 billion

 

65 6x6s with 71 faces generated with 1550 work units of 2 hours each - testing 31 6x5s
(which had faces up to 10 billion) by testing final face values to 500 billion

 

27 more 6x6s with 71 faces + 1 perfect 6x6 with 72 faces generated using 234 work units
of 2 hours each - testing 140 6x5s (which had minum faces from 10 to 70 billion) by
testing final face values to 20 billion (stopped when 72 soln reached)

 

Total of about 6500 cpu hours (3.2 Ghz)

*****************************************************

Non Prime Faces Case:

 

1550 perfect 5x5s (50 primes) generated after 6 days on 2 cpus

 

1370 perfect 6x5s (60 primes) generated after 1550 work units of 14 minutes - testing
face values up to 500 million

 

17 perfect 6x6s (72 primes) generated after 1540 work units of 14 minutes - testing
final face values up to 500 million (a few tested up to 1 billion)

 

Total of about 1000 cpu hours (3.2 GHz)

***

On March 2011, Giovanni Resta wrote:

It is not clear to me if the solution by Wilfred Whiteside
which is shown on your page for Q3 is the one (among
the 17 he found) with minimal total (111,923,140).

In any case, I found a solution for Q3 with a smaller
total sum (70,968,498):
First die : 7 13 63  3381 5182021 50907303
second die: 1 61 127 6421 3690241 11178859

It is curious to compare these (large)
results with those obtained requiring
that only the concatenation of the first die with
the second provides primes (so 36 instead of 72).
In that case, it is easy to find the minimum for
the sum (441):
{1,10,19,22,61,148} {3,7,9,13,51,97}
and for the maximum element (109):
{1,3,22,36,85,94} {7,13,37,73,97,109}

Using only primes the two minima are:
for the total sum (5738):
{3,19,199,367,631,2269} {7,13,181,457,739,853}
for the maximal element (1549):
{139,271,313,691,757,1063} {97,109,241,409,1087,1549}

***

---