mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2022-02-27, 06:16   #12
slandrum
 
Jan 2021
California

1E316 Posts
Default

Quote:
Originally Posted by uau View Post
I found a 117 element solution to the bonus problem. I don't remember the best for the basic question, but running a quick search gets 83 (could likely be easily improved somewhat, somewhat equivalent search gives 122 for the bonus).

My view about the bonus not being much harder than the standard problem seems supported by the published list of solvers - out of 13 listed people there's only a single one who didn't solve the bonus too.
Are you sure that your solutions are valid? One of the tests that I ran that was not correct generated an invalid solution of length 83 for the 200 digit problem, which seemed a striking coincidence. There was an error in the logic that permitted summands that were factors of other summands.

I have solutions that are under 100 for the 200 digit problem and under 150 for the 300 digit problem, but not as good as the solutions that you claim to have achieved.
slandrum is offline   Reply With Quote
Old 2022-02-27, 14:18   #13
SmartMersenne
 
Sep 2017

139 Posts
Default

Quote:
Originally Posted by slandrum View Post
Are you sure that your solutions are valid? One of the tests that I ran that was not correct generated an invalid solution of length 83 for the 200 digit problem, which seemed a striking coincidence. There was an error in the logic that permitted summands that were factors of other summands.

I have solutions that are under 100 for the 200 digit problem and under 150 for the 300 digit problem, but not as good as the solutions that you claim to have achieved.
I am impressed by people who found any solution at all.
SmartMersenne is offline   Reply With Quote
Old 2022-02-27, 20:33   #14
uau
 
Jan 2017

23×19 Posts
Default

Quote:
Originally Posted by slandrum View Post
Are you sure that your solutions are valid?
I've checked them enough that I'm pretty sure.
uau is offline   Reply With Quote
Old 2022-02-28, 02:40   #15
uau
 
Jan 2017

23·19 Posts
Default

Improved to 68 and 100 (well below half the targets now).
uau is offline   Reply With Quote
Old 2022-03-01, 23:29   #16
uau
 
Jan 2017

23·19 Posts
Default

Here's a not-quite-a-solution to the bonus problem. This could be considered somewhat of a spoiler to some aspects of the problem, but the month is over even if an official solution hasn't been published yet...


Quote:
[(1956, 0), (1929, 4), (1923, 6), (1913, 11), (1904, 18), (1893, 21), (1888, 27), (1886, 29), (1880, 38), (1879, 40), (1870, 42), (1866, 45), (1859, 51), (1837, 55), (1835, 62), (1833, 67), (1832, 68), (1828, 72), (1826, 79), (1808, 80), (1803, 87), (1799, 89), (1796, 92), (1790, 97), (1783, 107), (1780, 109), (1776, 113), (1770, 122), (1767, 124), (1749, 125), (1746, 130), (1733, 134), (1731, 142), (1729, 144), (1723, 150), (1722, 154), (1716, 155), (1714, 160), (1713, 161), (1704, 166), (1698, 174), (1679, 178), (1668, 180), (1657, 184), (1653, 188), (1649, 190), (1645, 199), (1629, 206), (1623, 208), (1603, 214), (1598, 220), (1590, 230), (1585, 235), (1584, 238), (1581, 240), (1580, 244), (1567, 249), (1558, 252), (1552, 253), (1548, 256), (1542, 265), (1533, 269), (1521, 270), (1517, 271), (1509, 276), (1505, 285), (1479, 294), (1475, 297), (1471, 302), (1467, 303), (1460, 311), (1449, 316), (1448, 319), (1443, 326), (1422, 327), (1414, 332), (1401, 336), (1394, 346), (1374, 350), (1358, 351), (1356, 357), (1354, 366), (1353, 369), (1344, 372), (1341, 375), (1336, 379), (1331, 380), (1323, 382), (1312, 385), (1311, 399), (1303, 401), (1286, 406), (1279, 411), (1276, 418), (1271, 421), (1267, 422), (1266, 428), (1263, 432), (1261, 437), (1256, 441), (1255, 443), (1246, 448), (1245, 452), (1244, 454), (1242, 455), (1238, 460), (1233, 463), (1225, 471), (1221, 477), (1217, 478), (1211, 487), (1179, 491), (1158, 492), (1154, 496), (1136, 501), (1133, 506), (1128, 509), (1123, 517), (1121, 521), (1114, 524), (1107, 528), (1101, 530), (1100, 534), (1097, 541), (1090, 545), (1087, 547), (1081, 550), (1079, 559), (1066, 561), (1064, 569), (1062, 571), (1055, 578), (1050, 582), (1048, 584), (1047, 585), (1037, 590), (1033, 600), (1025, 605), (988, 610), (985, 612), (984, 614), (962, 622), (952, 625), (951, 628), (938, 635), (937, 643), (925, 647), (921, 654), (909, 656), (902, 661), (896, 663), (883, 667), (876, 680), (848, 684), (838, 691), (835, 695), (831, 702), (829, 705), (826, 710), (825, 717), (824, 720), (823, 721), (812, 725), (811, 726), (804, 730), (803, 734), (796, 739), (789, 743), (785, 747), (783, 752), (776, 755), (773, 757), (772, 762), (752, 770), (745, 772), (731, 776), (717, 778), (716, 783), (710, 789), (700, 796), (693, 800), (692, 806), (689, 809), (685, 819), (677, 823), (671, 825), (664, 827), (652, 828), (651, 832), (644, 833), (633, 838), (631, 847), (619, 854), (614, 861), (608, 864), (604, 868), (602, 869), (600, 876), (599, 877)]
uau is offline   Reply With Quote
Old 2022-03-09, 08:30   #17
SmartMersenne
 
Sep 2017

13910 Posts
Default

The new puzzlemaster has outdone himself and is now updating the website less frequently than a month!
SmartMersenne is offline   Reply With Quote
Old 2022-03-11, 09:05   #18
Zoozie
 
Jan 2021

68 Posts
Default Solutions for february still not uploaded

Pages even gives a 404.


Good puzzles, but way to lazy puzzlemaster.
Zoozie is offline   Reply With Quote
Old 2022-03-22, 00:56   #19
uau
 
Jan 2017

23·19 Posts
Default

Official solution has finally been published 3 weeks into the next month. No analysis though, just a far from optimal answer. Here are the best solutions I found:

68 for the base problem:
Quote:
[(660, 0), (647, 2), (640, 8), (632, 10), (631, 18), (605, 20), (588, 23), (586, 30), (583, 32), (576, 36), (575, 38), (563, 46), (553, 48), (545, 50), (535, 53), (534, 54), (529, 59), (528, 70), (517, 73), (512, 80), (510, 86), (506, 89), (505, 91), (487, 96), (476, 98), (472, 102), (467, 104), (457, 109), (447, 112), (440, 122), (420, 125), (418, 127), (414, 139), (404, 148), (393, 150), (391, 152), (389, 158), (385, 162), (382, 165), (366, 171), (360, 174), (356, 177), (355, 180), (354, 182), (341, 183), (338, 189), (331, 199), (325, 206), (299, 210), (293, 214), (292, 217), (287, 221), (283, 223), (257, 230), (242, 235), (237, 239), (227, 243), (218, 249), (213, 261), (211, 267), (208, 271), (206, 275), (205, 278), (204, 279), (203, 285), (202, 287), (200, 288), (199, 289)]
98 for bonus:
Quote:
[(984, 0), (971, 3), (961, 5), (952, 9), (945, 16), (942, 19), (938, 21), (935, 24), (930, 32), (923, 37), (918, 40), (916, 44), (906, 45), (888, 46), (884, 50), (883, 58), (873, 60), (871, 66), (864, 72), (859, 80), (852, 86), (844, 88), (833, 91), (822, 92), (803, 97), (800, 104), (794, 108), (785, 115), (783, 121), (782, 124), (771, 126), (761, 131), (760, 137), (756, 139), (750, 143), (743, 149), (729, 150), (724, 163), (722, 170), (704, 172), (699, 174), (686, 181), (657, 182), (655, 183), (646, 194), (640, 195), (633, 201), (623, 202), (622, 210), (617, 215), (608, 220), (593, 221), (588, 225), (581, 231), (580, 235), (579, 245), (578, 246), (575, 248), (568, 254), (560, 260), (554, 264), (545, 271), (532, 274), (531, 278), (524, 282), (518, 293), (517, 295), (515, 300), (500, 304), (494, 310), (493, 315), (484, 317), (473, 321), (455, 323), (450, 325), (435, 326), (431, 329), (417, 336), (408, 343), (407, 357), (401, 361), (392, 362), (383, 363), (370, 364), (369, 380), (367, 384), (364, 390), (353, 393), (349, 394), (347, 397), (343, 398), (334, 399), (316, 402), (315, 406), (312, 410), (303, 415), (301, 427), (299, 432)]
Some notes about solving it:

I don't know of any way to search for a solution that would use the "decimal representation has ones and zeros" requirement in a way other than just picking a particular such number in advance and then targeting that. I picked numbers of the form 10N because that effectively gives a smaller target number of 5N - if you have a representation of 5N, you can just add N to all the powers of 2 to get a valid representation of 10N.

To generally find representations of the required form, you can consider divisibility by either 2 or 3. My best-performing search used 3, so I'll use it here.

Suppose you want to find a representation for 625. This is 1 mod 3. There is at most one term in the sum that is not divisible by 3. Thus the sum must have a power of 2 that is 1 mod 3, and is thus even (power of 4). We'll choose the largest possible such power, 256. 625-256 = 369. This is divisible by 9, so there can be no term in the remaining sum that is not divisible by 9 (at most one term could be 3 or 6 mod 9, and would make the whole sum not divisible). Dividing out the 9, we get 41. This is 2 mod 3, so there must be an odd power of 2. We'll pick the largest, which is 32. 41-32 = 9. This gives the representation 625 = 256 + 9*(32 + 9*(1)) = 256 + 9*32 + 81.

This algorithm - at each step, subtract the largest possible power of 2 that makes the remainder 0 mod 3 and non-negative, then divide out all factors of 3 - generally finds a valid representation for any number. To find sums with less terms, you must sometimes pick a smaller-than-maximal power of 2. Note that the non-divisibility requirement implies that the powers of 2 must be decreasing - if you picked 625 - 4 = 621, 621/27 = 23, you'd get 23-2 = 21, 21/3 = 7 and then you'd be stuck since there are no smaller powers of 2 you could continue with.

The algorithm I used kept a heap of the most promising partial sums found so far. Each is characterized by two values: the remaining sum to be represented by later terms, and the last power of two used (which implies a requirement for the remaining powers to be smaller). For a good candidate, you want the remainder to be small, and the power to be high (a low power leaves less potential choices later, and too low makes it outright impossible to expand it into any valid representation at all). I used the heuristic of "exponent - 5*log(remainder)", where higher is better. At each step the code would take all the candidates, subtract all possible powers of 2 and divide out factors of 3. The best results according to the above heuristic would then form the candidates taken to the next step.

Last fiddled with by uau on 2022-03-22 at 00:56
uau is offline   Reply With Quote
Old 2022-03-23, 07:30   #20
Dieter
 
Oct 2017

7·19 Posts
Thumbs up

Quote:
Originally Posted by uau View Post
Official solution has finally been published 3 weeks into the next month. No analysis though, just a far from optimal answer. Here are the best solutions I found:

68 for the base problem:
98 for bonus:
Some notes about solving it:

I don't know of any way to search for a solution that would use the "decimal representation has ones and zeros" requirement in a way other than just picking a particular such number in advance and then targeting that. I picked numbers of the form 10N because that effectively gives a smaller target number of 5N - if you have a representation of 5N, you can just add N to all the powers of 2 to get a valid representation of 10N.

To generally find representations of the required form, you can consider divisibility by either 2 or 3. My best-performing search used 3, so I'll use it here.

Suppose you want to find a representation for 625. This is 1 mod 3. There is at most one term in the sum that is not divisible by 3. Thus the sum must have a power of 2 that is 1 mod 3, and is thus even (power of 4). We'll choose the largest possible such power, 256. 625-256 = 369. This is divisible by 9, so there can be no term in the remaining sum that is not divisible by 9 (at most one term could be 3 or 6 mod 9, and would make the whole sum not divisible). Dividing out the 9, we get 41. This is 2 mod 3, so there must be an odd power of 2. We'll pick the largest, which is 32. 41-32 = 9. This gives the representation 625 = 256 + 9*(32 + 9*(1)) = 256 + 9*32 + 81.

This algorithm - at each step, subtract the largest possible power of 2 that makes the remainder 0 mod 3 and non-negative, then divide out all factors of 3 - generally finds a valid representation for any number. To find sums with less terms, you must sometimes pick a smaller-than-maximal power of 2. Note that the non-divisibility requirement implies that the powers of 2 must be decreasing - if you picked 625 - 4 = 621, 621/27 = 23, you'd get 23-2 = 21, 21/3 = 7 and then you'd be stuck since there are no smaller powers of 2 you could continue with.

The algorithm I used kept a heap of the most promising partial sums found so far. Each is characterized by two values: the remaining sum to be represented by later terms, and the last power of two used (which implies a requirement for the remaining powers to be smaller). For a good candidate, you want the remainder to be small, and the power to be high (a low power leaves less potential choices later, and too low makes it outright impossible to expand it into any valid representation at all). I used the heuristic of "exponent - 5*log(remainder)", where higher is better. At each step the code would take all the candidates, subtract all possible powers of 2 and divide out factors of 3. The best results according to the above heuristic would then form the candidates taken to the next step.
Thank you for this clarification. I wasn’t able to solve the puzzle, and the published solutions were not helpful.
Your algorithm in the simplest form - without trying to find sums with less terms – yields a solution with 122 terms for 10**199.
Now I were able to solve the puzzle.
Dieter is offline   Reply With Quote
Old 2022-03-23, 17:30   #21
slandrum
 
Jan 2021
California

3·7·23 Posts
Default

My approach was similar, except I started taking out the large power of 3.

In my base code - you pass in known factors, and the number you want to expand. So for 10^199 the call is:
pfac([0,0], 10^199)

From there, it reduces the number by removing multiples of 2 and 3. If that results in 1, then it returns the factors (added to the passed in ones) as the result. If there's a remainder, then it computes the largest power of 3 less than the number to expand. It returns that concatenated (added to the know factors) and passes the remainder back in.

For example - for 100, you immediately reduce to [2,0] for factors and 25 for the number to expand. The largest power of 3 is 9, so you have [2,2] for your first summand, and [2,0] and 16 are passed back into the function. Removing factors of 2 and 3, you get [4,0] and 1, so you are finished. [[2,2], [6,0]] is the final result returned.

This quick and dirty process comes up with a solution of length 125 for 10^199 and 200 for 10^299, both acceptable answers for the problem as given. From there I worked on some variations of the process to improve outcomes, my best results had a length of 87 for the 200 digit problem (and was not using 10^199, but instead 1011111111111111 followed by 186 zeros). I also found a solution for (10^200-1)/9 (200 digits of 1) that's 147 in length, which is an amusing solution to the problem.
slandrum is offline   Reply With Quote
Old 2022-03-23, 21:59   #22
slandrum
 
Jan 2021
California

3×7×23 Posts
Default

Quote:
Originally Posted by slandrum View Post
(and was not using 10^199, but instead 1011111111111111 followed by 186 zeros)
That should have read "followed by 184 zeros"
slandrum is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
February 2019 Xyzzy Puzzles 17 2019-03-07 21:05
February 2018 Xyzzy Puzzles 27 2018-03-08 06:31
February 2017 R. Gerbicz Puzzles 1 2017-03-02 23:13
February 2016 Xyzzy Puzzles 1 2016-03-07 02:48
February 2015 Xyzzy Puzzles 1 2015-03-02 19:01

All times are UTC. The time now is 00:09.


Thu Dec 1 00:09:22 UTC 2022 up 104 days, 21:37, 0 users, load averages: 1.27, 1.05, 1.00

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔