Problems & Puzzles: Puzzles

Puzzle 764. N integers in a row such that... Claudio Meller posted the following puzzle in his always interesting site, as the entry 1359. Find an arrangement of  N=10 distinct integers in a row such that the gcd of every two contiguous integers produce the first nine integers from 1 to 9, not necesarily in order but such that the sum of the N integers is a minimal sum. He gave the following example:   N=10 1 18 9 6 12 8 112 35 30 2 Sum=233 gcd   1 9 3 6 4 8 7 5 2   Carlos Rivera sent the following contribution to this puzzle without claiming that this is the real minimal asked solution   N=10 1 2 4 8 24 6 9 45 35 7 Sum=141 gcd   1 2 4 8 6 3 9 5 7     Q1. Can you find a smaller sum solution for N=10? Q2. Redo the exercise for N=20, 50 & 100, minimal sum as before, in order to get the first 19, 49 & 99 integers as gcd's, respectively.

---

Contributions came from Ramón David Aznar, Giovanni Resta, Emmanuel Vantieghem and Hakan Summakoglu and Fred Schneider...

I have written in bold type the minimal sums gotten by all the puzzlers, for each N value.

***

Ramón wrote:

For N=10
9 18 6 15 5 7 14 4 8 16, Sum=102
9 6 3 5 1 7 2 4 8

***

Giovanni wrote:

I was able to find only solutions for N=10 (optimal) and N=20 (probably optimal).

The optimal solution for N=10 should be Sum=102
3 (3) 9 (9) 18 (6) 12 (4) 8 (8) 16 (1) 5 (5) 10 (2) 14 (7) 7
(Please notice that this solution is different from the already discovered by Ramòn)

The solution for N=20 has sum 592 and values:
1 (1) 19 (19) 38 (2) 26 (13) 65 (5) 10 (10) 30 (15) 45 (9) 36 (18) 18 (6) 12 (12) 24 (8) 16 (16) 32 (4) 28 (14) 14 (7) 77 (11) 33 (3) 51 (17) 17

where between ( ) I indicate the GCD of surrounding integers.

***

Emmanuel wrote:

Let  F  be the row of the  N  numbers and  G  the row of the GCD's.

 

N = 10

F = {1,5,15,9,18,24,8,4,14,7}, sum 105 all most sure minimal.

G = {1,5,3,9,6,8,4,2,7}.

 

N = 20

F = {1,7,14,42,48,16,24,36,18,45,30,10,55,44,52,39,51,34,38,19} with sum 623 (probably not minimal)

G = {1,7,14,6,16,8,12,18,9,15,10,5,11,4,13,3,17,2,19}

 

N = 50

F = {1,16,48,24,132,22,143,26,78,114,38,133,35,210,90,135,54,36,144,240,440,308,
84,42,238,34,527,310,230,46,667,232,32,160,100,75,195,117,99,231,147, 196,148,185,205,123,129,86,94,47} with sum 7246 (all most sure not minimal)

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

My method is not suitable to find a solution for  N = 100 in a reasonable time.

***

Hakan wrote:

Q1:
N=10  Sum=102
array:3 9 18 12 8 16 5 10 14 7
gcd  :3 9 6 4 8 1 5 2 7

 

Q2:   
 

N=20  Sum=787
array:38 19 2 4 8 16 48 9 18 36 12 30 15 10 70 14 91 143 187 17
gcd  :19 1 2 4 8 16 3 9 18 12 6 15 5 10 14 7 13 11 17

N=50  Sum=10716
array:94 47 2 4 8 16 32 96 6 9 18 36 24 48 144 108 135 45 10 20 40 120 30 75 175 35 14 28 84 42 147 539 22 44 132 429 39 26 442 34 323 38 874 46 667 899 1147 1517 1763 43
gcd  :47 1 2 4 8 16 32 6 3 9 18 12 24 48 36 27 45 5 10 20 40 30 15 25 35 7 14 28 42 21 49 11 22 44 33 39 13 26 34 17 19 38 46 23 29 31 37 41 43

N=100 Sum=73874
array:97 194 3 6 12 4 10 20 40 80 160 16 24 36 72 144 48 120 15 25 50 150 225 18 54 81 162 270 90 315 35 14 28 56 168 84 63 126 210 490 98 539 77 22 44 88 264 66 99 495 715 26 52 156 195 455 546 390 60 480 96 64 1088 68 34 51 255 1615 95 38 76 228 1311 46 92 276 2001 87 58 1798 62 93 3441 74 3034 82 1763 86 4042 94 2491 3127 3599 4087 4757 5183 5767 6557 7387 89
gcd  :97 1 3 6 4 2 10 20 40 80 16 8 12 36 72 48 24 15 5 25 50 75 9 18 27 81 54 90 45 35 7 14 28 56 84 21 63 42 70 98 49 77 11 22 44 88 66 33 99 55 13 26 52 39 65 91 78 30 60 96 32 64 68 34 17 51 85 95 19 38 76 57 23 46 92 69 87 29 58 62 31 93 37 74 82 41 43 86 94 47 53 59 61 67 71 73 79 83 89

***

Fred wrote:

Q1: I think 102 is the minimal solution.  I found this by hand.
 

9	=>	102	=	4		8		24		18		9		3		5		10		14		7
					4		8		6		9		3		1		5		2		7

 

Too bad, I didn't have time to code something to solve this generally.

***

The Sunday Nov 16, 2014, Dmitry Kamenetsky wrote:

I've got some improvements for Puzzle 764. I am almost sure that 102 is optimal for N=10. Here are my results for other N:

N=20, score=508

11 77 14 28 32 16 40 10 15 30 12 36 18 9 39 13 19 38 34 17

 

***

On Nov 19, 2014, Dmitry send new better results:

N=50, score=4464

47 94 74 185 115 46 184 80 40 20 130 78 39 143 33 66 44 88 164 41 31 186 114 38 323 34 204 84 42 147 98 70 175 75 30 90 45 27 54 36 72 48 96 32 112 28 203 87 129 43 

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

 

N=100, score=36352

57 228 380 285 165 55 66 198 495 225 75 50 150 60 460 92 1679 511 84 252 108 162 81 27 153 102 474 79 89 267 69 138 368 160 80 590 2537 86 344 88 440 120 180 90 166 415 265 2173 82 164 284 2059 87 174 406 854 1891 62 186 651 42 336 96 288 72 564 94 1739 74 814 44 132 231 308 196 98 245 70 280 224 64 192 312 260 1105 170 68 136 1139 1273 38 494 182 819 126 234 78 39 1261 97 

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

***

On Dec. 5, Dmitry send better results:

N=50, score=4162

37 148 92 46 253 33 66 44 132 48 96 32 80 40 60 30 75 50 70 105 42 84 28 98 49 91 26 78 117 45 135 54 36 72 24 136 34 323 38 114 174 145 155 93 123 41 47 94 86 43 
 

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

 

N=100, score=23589

97 194 178 89 79 474 354 649 77 154 110 165 75 150 60 240 80 280 168 84 357 255 170 68 408 48 96 192 64 288 72 36 492 82 697 493 87 174 406 42 294 98 441 126 198 99 66 132 88 176 496 62 93 279 603 268 292 365 305 488 344 86 817 95 190 76 228 513 81 162 270 90 315 70 140 364 273 78 156 52 130 325 50 100 460 92 138 69 851 74 370 470 94 611 689 371 497 213 249 83
 

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

***

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

 N = 50: Sum = 4036

43 86 94 47 41 123 93 124 116 203 49 98 28 84 42 105 70 50 75 45 90 60 40 80 32 96 48 24 36 72 54 27 117 78 26 143 33 66 44 88 136 34 323 38 114 138 46 115 185 37

N = 100: Sum = 22062

79 316 268 469 427 671 583 424 184 92 138 69 989 86 516 348 87 58 406 196 98 245 70 210 60 180 90 135 81 162 108 72 144 96 192 64 160 80 120 168 56 252 84 126 63 231 154 110 165 99 198 132 88 176 304 76 114 57 95 380 100 150 75 325 130 52 156 78 273 91 481 74 666 558 62 93 465 255 204 68 170 85 799 94 282 426 355 415 166 178 89 97 291 177 590 410 82 369 657 73

***