Problems & Puzzles: Puzzles

Puzzle 766. A Follow up to Puzzle 764.

Dmitry Kamenetsky propose the following nice follow-up to the Puzzle 764

"There is an interesting 2D variant of this problem. Place numbers in a NxN grid such that all gcds from 1 to 2*N*(N-1) are generated. A gcd is generated for every pair of neighboring numbers"

In this problem even small N are hard to solve for the minimal sum.

To give you an example, here is the best result I found for N=3, Sum=251, gcds in red.

 10 44 11 2 11 40 24 36 8 12 35 42 9 7 3 10 4 1 251 5 6 9

Q. Send your minimal sum solutions for N=3, 4 & 5.

Contributions came from Dmitry Kamenetsky

***

Dmitry wrote:

Here are my best results for the 2D case.

3x3, score: 251
Same as problem statement
10 44 11
40 24 36
35 42 9

4x4, score: 1647
187 88 110 46
102 48 80 115
117 72 60 76
182 126 105 133

score: 6526
253 322 175 75 95
231 252 140 570 494
198 288 160 120 78
374 204 592 216 351
527 62 111 261 377

6x6, score: 34561
26 572 352 336 1776 1073
1833 780 160 1400 696 406
1316 420 1225 950 540 378
315 570 2793 2356 612 1161
495 462 714 1581 782 1978
55 902 2173 954 1062 1357

***

On Dec 5, 2014, Dmitry sent this better result for 6x6

6x6
score 25056
583 165 550 200 902 1271
1113 210 1225 880 572 806
602 252 392 224 156 429
1161 216 912 480 180 495
846 918 969 380 690 354
799 1258 1073 1102 1334 1357

***

Michael Hürter wrote on Nov. 1, 2016:

5x5: Sum = 6480

185 175 150 460 437
518 105 120 160 38
28 252 216 352 304
68 306 297 286 377
527 186 429 156 348

***

Dmitry wrote on Nov 15, 2016

More results.

7x7, score 106136
2623 3268 1026 756 1071 2686 3239
3477 1596 2016 280 2040 2788 574
1862 1050 800 2730 1980 616 2387
1225 2775 2145 312 576 2232 2914
3045 2146 6380 1518 1472 1863 3243
2478 1924 1040 2640 3984 1620 1971
4189 1846 4355 2211 913 2385 3869

8x8, score 310683
5893 6225 1850 3100 8277 7626 8774 1177
5751 4050 3996 6300 3560 2170 15785 7469
9045 1260 3885 672 2080 1680 11220 4947
3283 4508 10005 2208 2184 4816 8514 3655
1610 2484 6264 2736 4290 4410 9009 7735
3555 5922 2726 8265 2090 4312 8052 3965
8374 2226 8319 4484 1216 1496 2652 4017
5353 7474 4033 1744 3264 1326 3796 7519

9x9, score 771368
8201 8024 15694 1900 7296 10512 28105 12430 10961
9452 6120 5985 8400 896 7200 7392 4880 17751
11645 9864 7752 3534 8680 6625 10500 7686 4473
7990 7332 6630 11067 5950 19822 7420 17892 3266
6063 9374 1290 12075 3300 4444 24745 6566 11270
5076 14715 4257 1518 8184 2852 18879 3886 7705
11556 21330 3960 5520 3520 11960 5220 4292 22126
12947 11297 27170 2340 5184 5265 9594 10101 16198
10043 20501 12065 13208 10712 13493 10742 4551 10947

***

 Records   |  Conjectures  |  Problems  |  Puzzles