Problems & Puzzles: Puzzles

Puzzle 712 Primes or squares Bernardo Recaman sent the following nice puzzle: Find the largest integer n with the property that it is possible to split the integers 1 to 2n into n pairs of numbers whose n sums are either prime or square numbers, no two of them equal. Example: For n = 8, the pairs (1,8), (2,11), (3,4), (5,6), (7,16), (9,10), (12,13) & (14, 15) yield a set of 6 different primes and 2 different squares: {9, 13, 7, 11, 23, 19, 25, 29}. Q. Find all your solutions for n>8 up to the largest n possible.

---

Contributions came from Flavio Torazzo, Jan van Delden, Carlos Rivera, Emmanuel Vantieghem, Vicente Felipe Izquierdo, Dimitry Kamenetsky, Jud McCranie, Gérald deGrotte, Giovanni Resta and Hakan Summakoglu.

***

Two general comments:

1) this puzzle not only became very popular but also made bring back some old friends of this pages like Flavio and Dimitry and a new puzzler Gérald.

2) None of the puzzlers that got the solution for n=33 as the maximal of his own search (Jan, Rivera, Dimitry, Jud, Giovanni) is certain that there is not a solution for n>33.

***

Flavio wrote:

Here are 5 solutions for n = 9

• (1,2), (3,10), (5,6), (7,18), (9,14), (11,8), (13,4), (15,16) & (17,12) --> {3, 13, 11, 25, 23, 19, 17, 31, 29}
• (1,2), (3,10), (5,18), (7,4), (9,8), (11,14), (13,6), (15,16) & (17,12) --> {3, 13, 23, 11, 17, 25, 19, 31, 29}
• (1,4), (3,6), (5,8), (7,18), (9,10), (11,12), (13,16), (15,2) & (17,14) --> {5, 9, 13, 25, 19, 23, 29, 17, 31}
• (1,4), (3,10), (5,12), (7,2), (9,14), (11,18), (13,6), (15,16) & (17,8) --> {5, 13, 17, 9, 23, 29, 19, 31, 25}
• (1,18), (3,2), (5,4), (7,6), (9,8), (11,14), (13,10), (15,16) & (17,12) --> {19, 5, 9, 13, 17, 25, 23, 31, 29}

and 3 solutions for n = 10

• (1,4), (3,14), (5,8), (7,16), (9,2), (11,18), (13,6), (15,10), (17,20) & (19,12) --> {5, 17, 13, 23, 11, 29, 19, 25, 37, 31}
• (1,10), (3,2), (5,12), (7,6), (9,14), (11,20), (13,16), (15,4), (17,8) & (19,18) --> {11, 5, 17, 13, 23, 31, 29, 19, 25, 37}
• (1,12), (3,2), (5,6), (7,18), (9,14), (11,8), (13,4), (15,16), (17,20) & (19,10) --> {13, 5, 11, 25, 23, 19, 17, 31, 37, 29}

The solutions for n = 11 come from the previous adding the pair (21,22) --> {43}

The solutions for n = 12 come from the previous adding the pair (23,24) --> {47}

 

***

Jan wrote:

...An upperbound to the true maximum value for n is thus (probably) equal to 80...

My largest solution n=23:

 

23 [[1,2],[3,4],[5,6],[7,9],[8,11],[10,15],[12,19],[13,24],[14,22],[16,25],[17,26],[18,29],[20,33],[21,28],[23,36],[27,34],[30,37],[31,40],[32,41],[35,44],[38,45],[39,42],[43,46]]
23 [3, 7, 11, 16, 19, 25, 31, 37, 36, 41, 43, 47, 53, 49, 59, 61, 67, 73, 79, 83, 81, 89]

...I also found immediate answers except when n=25,26,27 and n=34 is still running.

***

Rivera found solutions for n=1 up to 33.

? 33

Solution found!!!

 

 66  65  131 - 64  63  127 - 62  59  121 - 61  52  113 - 60  49  109 - 58  45  103 - 57  50  107 - 56  44  100 - 55  46  101 - 54  43  97 - 53  36  89 - 51  32  83 - 48  33  81 - 47  26  73 - 42  37  79 - 41  30  71 - 40  27  67 - 39  25  64 - 38  23  61 - 35  24  59 - 34  19  53 - 31  18  49 - 29  14  43 - 28  13  41- 22  15  37 - 21  10  31 - 20  16  36 - 17  12  29 - 11  8  19 - 9  7  16 - 6 5  11 - 4  3  7 - 2  1  3.

It´s easy to show that n=80 is the maximal theoretically possible as upper bound of solutions.

***

Emmanuel wrote:

 my record is n =18 :

{{1,8},{2,9},{3,10},{4,13},{5,11},{6,17},{7,18},{12,19},{14,22},{15,26},{16,21},{20,27},{23,30},{24,25},{28,31},

{29,32},{33,34},{35,36}}  giving the sums   {9,11,13,17,16,23,25,31,36,41,37,47,53,49,59,61,67,71}.

***

Vicente found solutions for n=9 up to 22:
 

No he llegado muy lejos pero creo que las soluciones son correctas hasta k=22.
Te indico K, parejas, sumas:
 
9,{{1,2},{3,8},{4,9},{5,12},{6,13},{7,16},{10,15},{11,18},{14,17}},{3,11,13,17,19,23,25,29,31}
10,{{1,2},{3,4},{5,8},{6,13},{7,9},{10,15},{11,12},{14,17},{16,20},{18,19}},{3,7,13,19,16,25,23,31,36,37}
11,{{1,2},{3,4},{5,6},{7,9},{8,11},{10,13},{12,17},{14,22},{15,16},{18,19},{20,21}},{3,7,11,16,19,23,29,36,31,37,41}
12,{{1,2},{3,4},{5,6},{7,9},{8,11},{10,13},{12,17},{14,22},{15,16},{18,19},{20,21},{23,24}},{3,7,11,16,19,23,29,36,31,37,41,47}
13,{{1,2},{3,4},{5,6},{7,9},{8,11},{10,13},{12,17},{14,22},{15,16},{18,19},{20,23},{21,26},{24,25}},{3,7,11,16,19,23,29,36,31,37,43,47,49}
14,{{1,2},{3,4},{5,6},{7,9},{8,11},{10,15},{12,17},{13,18},{14,22},{16,21},{19,24},{20,27},{23,26},{25,28}},{3,7,11,16,19,25,29,31,36,37,43,47,49,53}
15,{{1,2},{3,4},{5,6},{7,9},{8,11},{10,15},{12,17},{13,18},{14,22},{16,21},{19,24},{20,27},{23,26},{25,28},{29,30}},{3,7,11,16,19,25,29,31,36,37,43,47,49,53,59}
16,{{1,2},{3,4},{5,6},{7,9},{8,11},{10,13},{12,17},{14,22},{15,16},{18,23},{19,24},{20,29},{21,26},{25,28},{27,32},{30,31}},{3,7,11,16,19,23,29,36,31,41,43,49,47,53,59,61}
17,{{1,2},{3,4},{5,6},{7,9},{8,11},{10,13},{12,17},{14,22},{15,16},{18,23},{19,24},{20,29},{21,26},{25,28},{27,32},{30,31},{33,34}},{3,7,11,16,19,23,29,36,31,41,43,49,47,53,59,61,67}
18,{{1,2},{3,4},{5,6},{7,9},{8,11},{10,13},{12,17},{14,22},{15,16},{18,23},{19,24},{20,29},{21,26},{25,28},{27,32},{30,31},{33,34},{35,36}},{3,7,11,16,19,23,29,36,31,41,43,49,47,53,59,61,67,71}
19,{{1,2},{3,4},{5,6},{7,9},{8,11},{10,15},{12,17},{13,18},{14,22},{16,25},{19,24},{20,27},{21,28},{23,30},{26,33},{29,32},{31,36},{34,37},{35,38}},{3,7,11,16,19,25,29,31,36,41,43,47,49,53,59,61,67,71,73}
20,{{1,2},{3,4},{5,6},{7,9},{8,11},{10,15},{12,17},{13,18},{14,22},{16,25},{19,24},{20,27},{21,28},{23,30},{26,33},{29,32},{31,36},{34,37},{35,38},{39,40}},{3,7,11,16,19,25,29,31,36,41,43,47,49,53,59,61,67,71,73,79}
21,{{1,2},{3,4},{5,6},{7,9},{8,11},{10,13},{12,17},{14,23},{15,16},{18,25},{19,22},{20,27},{21,28},{24,29},{26,33},{30,34},{31,36},{32,39},{35,38},{37,42},{40,41}},{3,7,11,16,19,23,29,37,31,43,41,47,49,53,59,64,67,71,73,79,81}
22,{{1,2},{3,4},{5,6},{7,9},{8,11},{10,13},{12,19},{14,22},{15,26},{16,21},{17,30},{18,31},{20,23},{24,29},{25,34},{27,40},{28,33},{32,39},{35,38},{36,43},{37,44},{41,42}},{3,7,11,16,19,23,31,36,41,37,47,49,43,53,59,67,61,71,73,79,81,83}

***

Dimitry wrote:

Here are my solutions for puzzle 712. For the case of unique primes and squares I could not get better than 33:
 

n 33
(64,63), (44,27), (42,41), (25,22), (5,14), (28,36), (38,35), (19,12), (49,52), (30,7), (32,21), (46,51), (65,66), (57,43), (6,10), (11,18), (23,13), (54,59), (26,33), (17,8), (53,56), (47,20), (4,9), (50,29), (34,15), (45,62), (39,2), (40,3), (60,61), (24,37), (16,1), (58,31), (55,48)

If we allow primes, squares and cubes:

n 46
(85,78), (81,76), (39,14), (13,10), (47,26), (9,18), (23,41), (86,87), (71,60), (52,75), (6,7), (15,32), (42,61), (69,82), (68,57), (17,24), (27,54), (3,22), (50,29), (40,19), (35,62), (91,88), (44,63), (67,70), (5,4), (1,16), (36,31), (53,8), (83,84), (25,12), (46,37), (34,2), (51,49), (74,65), (11,20), (90,79), (59,30), (28,21), (64,80), (89,92), (45,56), (55,58), (73,48), (72,77), (33,38), (43,66)
 

Finally if we allow primes and any power (a^b, with b>1) I get

 

n 50
(96,85), (40,49), (68,89), (9,38), (74,75), (100,99), (22,3), (53,47), (37,76), (91,82), (65,62), (95,98), (6,26), (14,5), (7,34), (90,73), (23,41), (60,77), (43,16), (69,32), (67,72), (57,64), (70,55), (8,28), (54,13), (11,18), (66,78), (21,10), (31,30), (81,88), (12,15), (25,56), (94,97), (20,59), (35,93), (44,63), (61,48), (58,39), (50,33), (24,19), (84,83), (79,52), (87,92), (51,2), (46,27), (86,17), (4,45), (71,80), (42,29), (1,36)

***

Jud wrote:

N=86 cannot have a solution because numbers can be up to 2n + 2(n-1).  For n=86, the largest possible is 342.  There are 68 primes and 17 squares below that number, a total of 85.  The actual limit may be less than 86.

The largest n I was able to find a solution for is n=33.

n=33  (1,3) (2,5) (4,13) (6,10) (7,16) (8,11) (9,22) (12,17) (14,23) (15,38) (18,25) (19,30) (20,27) (21,40) (24,47) (26,41) (28,31) (29,35) (32,51) (33,48) (34,39) (36,53) (37,42) (43,54) (44,56) (45,58) (46,55) (49,60) (50,57) (52,61) (59,62) (63,64) (65,66)

A table for n from 9 to 33 is attached.

***

Gérald wrote:

for n= 9
pairs  (1,3),(2,9),(5,8),(4,12),(6,13),(7,16),(10,15),(11,18),(14,17)
set     {4,11,13,16,19,23,25,29,31}

for n=10
pairs  (3,4),(2,7),(5,8),(1,16),(9,10),(11,12),(6,19),(14,15),(13,18),(17,20)
set     {7,9,13,17,19,23,25,29,31,37}

for n=11
pairs  (1,2),(3,8),(4,9),(6,10),(5,12),(7,16),(11,14),(13,18),(17,19),(15,22),(20,21)
set     {3,11,13,16,17,23,25,31,36,37,41}

for n=12
pairs  (3,8),(2,11),(6,10),(5,12),(4,15),(1,22),(7,18),(9,20),(14,17),(13,23),(16,21),(19,24)
set     {11,13,16,17,19,23,25,29,31,36,37,43}

for n=13
pairs  (1,2),(5,6),(4,9),(3,13),(7,12),(11,14),(8,21),(15,16),(10,26),(18,19),(17,24),(20,23),(22,25)
set     {3,11,13,16,19,25,29,31,36,37,41,43,47}

for n=14
pairs  (1,4),(3,10),(5,11),(8,9),(6,13),(7,16),(2,27),(12,19),(14,22),(17,20),(18,23),(15,28),(21,26),(24,25)
set     {5,13,16,17,19,23,29,31,36,37,41,43,47,49}

for n=15
pairs  (2,5),(1,10),(4,12),(3,14),(7,16),(6,19),(8,21),(13,18),(9,27),(15,22),(11,30),(17,26),(23,24),(20,29),(25,28)
set     {7,11,16,17,23,25,29,31,36,37,41,43,47,49,53}

for n=16
pairs  (1,8),(4,9),(3,13),(6,11),(2,17),(7,16),(5,20),(10,19),(14,22),(12,25),(18,23),(15,28),(21,26),(24,29),(27,32),(30,31)
set     {9,13,16,17,19,23,25,29,36,37,41,43,47,53,59,61}

for n=17
pairs  (1,4),(5,6),(2,11),(3,14),(7,16),(10,15),(9,20),(8,23),(12,24),(18,19),(13,28),(17,26),(22,25),(21,32),(29,30),(27,34),(31,33)
set     {5,11,13,17,23,25,29,31,36,37,41,43,47,53,59,61,64}

for n=18
pairs  (2,5),(1,8),(3,13),(6,11),(9,10),(4,19),(7,18),(12,17),(15,22),(20,21),(14,29),(23,24),(16,33),(26,27),(25,34),(30,31),(28,36),(32,35)
set     {7,9,16,17,19,23,25,29,37,41,43,47,49,53,59,61,64,67}

for n=19
pairs  (2,3),(1,6),(4,7),(5,8),(9,14),(10,15),(11,18),(16,20),(12,25),(17,24),(13,30),(19,28),(22,27),(21,32),(23,36),(26,35),(31,33),(29,38),(34,37)
set     {5,7,11,13,23,25,29,36,37,41,43,47,49,53,59,61,64,67,71}

***

Giovanni wrote:

after a certain n (around 80 I think, but I forgot the precise value I've computed) it is impossible to find  solution because the number of
primes+squares is smaller than the number of the pairs involved.

Anyway, I found solutions for all the n from 8 to 33, but I'm
not sure larger solutions cannot exist, but I think they are improbable.

One of the solutions for n=33 is:

(1,2)=3 (3,4)=7 (5,6)=11 (7,9)=16 (8,11)=19 (12,17)=29 (16,20)=36 (10,21)=31 (15,22)=37 (13,28)=41 (14,29)=43 (18,31)=49 (19,34)=53 (24,35)=59 (23,38)=61 (25,39)=64 (27,40)=67 (30,41)=71 (37,42)=79 (26,47)=73 (33,48)=81 (32,51)=83 (36,53)=89 (43,54)=97 (46,55)=101 (44,56)=100 (50,57)=107 (45,58)=103 (49,60)=109 (52,61)=113 (59,62)=121 (63,64)=127 (65,66)=131.
 

***

Hajan wrote:

n=9:  (1,2),(4,7),(3,10),(6,11),(5,14),(8,15),(9,16),(12,17),(13,18)
n=10: (1,3),(2,7),(6,10),(4,13),(5,14),(8,15),(9,16),(11,18),(12,19),(17,20)
n=11: (1,3),(2,7),(6,10),(4,13),(5,14),(8,15),(9,16),(11,18),(12,19),(17,20),(21,22)
n=12: (1,3),(2,7),(6,10),(4,13),(5,14),(8,15),(9,16),(11,18),(12,19),(17,20),(21,22),(23,24)
n=13: (1,2),(4,7),(3,10),(6,11),(5,14),(8,15),(9,16),(12,17),(13,18),(20,21),(19,24),(22,25),(23,26)
n=14: (1,2),(3,4),(5,6),(8,9),(7,12),(10,13),(11,14),(15,16),(17,20),(18,23),(19,24),(21,26),(22,27),(25,28)
n=15: (1,2),(3,4),(5,6),(8,9),(7,12),(10,13),(11,14),(15,16),(17,20),(18,23),(19,24),(21,26),(22,27),(25,28),(29,30)
n=16: (1,2),(3,4),(5,6),(7,9),(8,11),(10,13),(14,15),(12,19),(16,20),(17,24),(18,25),(21,26),(22,27),(23,30),(28,31),(29,32)
n=17: (1,2),(3,4),(5,6),(7,9),(8,11),(10,13),(14,15),(12,19),(16,20),(17,24),(18,25),(21,26),(22,27),(23,30),(28,31),(29,32),(33,34)
n=18: (1,2),(3,4),(5,6),(7,9),(8,11),(10,13),(14,15),(12,19),(16,20),(17,24),(18,25),(21,26),(22,27),(23,30),(28,31),(29,32),(33,34),(35,36)
n=19: (1,2),(3,6),(4,7),(5,8),(9,10),(11,14),(13,16),(12,19),(15,22),(17,24),(18,25),(21,26),(20,29),(23,30),(27,32),(28,33),(31,36),(34,37),(35,38)
n=20: (1,2),(3,6),(4,7),(5,8),(9,10),(11,14),(13,16),(12,19),(15,22),(17,24),(18,25),(21,26),(20,29),(23,30),(27,32),(28,33),(31,36),(34,37),(35,38),(39,40)
n=21: (1,2),(3,6),(4,7),(5,8),(9,10),(11,14),(13,16),(12,19),(15,22),(17,24),(18,25),(21,26),(20,29),(23,30),(27,32),(28,33),(31,36),(34,37),(35,38),(39,40),(41,42)
n=22: (1,2),(3,4),(5,6),(8,9),(7,12),(10,13),(11,14),(15,16),(17,19),(20,21),(23,24),(18,25),(22,27),(29,30),(33,34),(26,35),(28,36),(31,40),(32,41),(37,42),(38,43),(39,44)
n=23: (1,2),(3,6),(4,7),(5,8),(9,10),(11,12),(14,15),(13,18),(17,19),(16,21),(20,23),(22,25),(24,29),(26,33),(27,34),(32,35),(28,36),(39,40),(30,41),(31,42),(37,44),(38,45),(43,46)
n=24: (2,3),(4,7),(8,15),(1,18),(6,19),(9,20),(13,23),(5,26),(10,27),(11,30),(12,31),(17,32),(14,33),(16,37),(21,38),(22,39),(24,40),(25,42),(28,43),(29,44),(34,45),(35,46),(36,47),(41,48)

***