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 

 

***