mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2022-02-02, 13:44   #1
tgan
 
Jul 2015

2416 Posts
Default February 2022

https://research.ibm.com/haifa/ponde...ruary2022.html
tgan is offline   Reply With Quote
Old 2022-02-03, 07:41   #2
uau
 
Jan 2017

23×19 Posts
Default

Better puzzle this time IMO - some of the recent puzzles have just asked to implement a straightforward brute-force search with little actual "puzzle" component that would require figuring out anything non-obvious, but this one was fine. The bonus question didn't seem much harder than the standard one though (the maximum number of summands could be set a lot lower - the 150 limit from the length-200 standard question would be more than enough for the length-300 bonus too).
uau is offline   Reply With Quote
Old 2022-02-13, 20:05   #3
Max0526
 
"Max"
Jun 2016
Toronto

929 Posts
Default

My glitchy Python code produced a no-star solution with 149 summands where I practically guessed the 200-digit number (mostly zeros).
At 242 summands for 300 digits now, long way to go to get to 214 and below, needs some rethinking and automation.
Definitely doable.
Max0526 is offline   Reply With Quote
Old 2022-02-13, 20:51   #4
slandrum
 
Jan 2021
California

3×7×23 Posts
Default

Quick and dirty pari/gp code gets an immediate 125 summand solution for the 200 digit problem and a 200 summand solution for the 300 digit problem.

Minor tweaks to the code and I get 116 for the 200 digit problem, and 175 for the 300 digit problem. And I know that there's a lot that can be done to get better answers.

First hint is that inspection of small numbers shows that there are multiple ways to encode many of them, and if the numbers are sufficiently large, then there are many ways to encode them.

For example: 11 is encoded as [(3,0), (0,1)] or [(1,0), (0,2)]
slandrum is offline   Reply With Quote
Old 2022-02-13, 23:05   #5
SmartMersenne
 
Sep 2017

8B16 Posts
Default

I find the "no summand divides the other" condition to be very strict. How can you easily find a solution? Are you sure you are considering this condition?
SmartMersenne is offline   Reply With Quote
Old 2022-02-14, 03:45   #6
slandrum
 
Jan 2021
California

1E316 Posts
Default

Quote:
Originally Posted by SmartMersenne View Post
I find the "no summand divides the other" condition to be very strict. How can you easily find a solution? Are you sure you are considering this condition?
Absolutely I'm adhering to this condition, otherwise the problem would be trivial to find much smaller solutions.

For example, I'll give here a solution to (10^200-1)/9 (200 digits of 1) - this has 193 summands, obviously one that has too many summands for the puzzle, but you can see from the output that no summand divides another (the 2 exponent is strictly increasing and the 3 exponent is strictly decreasing, so any pair of summands cannot have one divide the other). This is the quick and dirty output.

Quote:
[[0, 417], [2, 414], [5, 411], [9, 408], [11, 404], [12, 401], [13, 400], [14, 398], [15, 397], [16, 396], [18, 394], [19, 393], [21, 391], [27, 386], [28, 385], [29, 383], [34, 380], [35, 378], [39, 375], [41, 373], [42, 371], [43, 369], [46, 364], [47, 361], [48, 360], [49, 359], [50, 358], [51, 355], [52, 354], [54, 353], [55, 350], [56, 349], [62, 345], [64, 343], [65, 341], [66, 340], [68, 339], [72, 333], [74, 332], [77, 328], [78, 327], [79, 326], [80, 325], [81, 323], [82, 322], [84, 321], [91, 314], [93, 313], [94, 310], [97, 308], [98, 307], [100, 305], [101, 304], [102, 302], [107, 298], [109, 296], [112, 292], [114, 291], [117, 288], [118, 285], [119, 284], [120, 283], [121, 282], [122, 281], [125, 277], [126, 273], [130, 268], [131, 267], [132, 265], [133, 263], [135, 262], [136, 260], [137, 259], [140, 256], [142, 254], [143, 253], [145, 251], [147, 249], [149, 247], [151, 245], [152, 243], [154, 241], [156, 239], [159, 237], [161, 235], [162, 234], [163, 233], [166, 231], [169, 227], [171, 226], [173, 222], [174, 219], [175, 217], [185, 210], [186, 209], [187, 208], [191, 205], [192, 204], [193, 200], [195, 198], [197, 197], [199, 191], [201, 190], [203, 187], [204, 186], [205, 185], [206, 184], [207, 183], [213, 179], [215, 177], [216, 176], [217, 174], [218, 173], [223, 170], [224, 168], [225, 167], [226, 166], [227, 165], [230, 161], [231, 160], [235, 157], [236, 156], [238, 154], [240, 152], [241, 150], [242, 145], [245, 142], [246, 141], [247, 140], [248, 137], [252, 133], [253, 132], [254, 131], [255, 130], [257, 128], [261, 123], [262, 122], [263, 121], [266, 119], [267, 117], [269, 115], [270, 114], [274, 110], [275, 109], [277, 107], [279, 101], [280, 100], [281, 99], [284, 97], [287, 95], [290, 91], [292, 89], [297, 85], [298, 84], [301, 82], [303, 80], [304, 79], [306, 77], [308, 75], [311, 73], [312, 72], [314, 69], [316, 65], [317, 63], [320, 59], [321, 57], [322, 56], [323, 55], [324, 54], [328, 52], [330, 48], [331, 47], [332, 46], [342, 39], [343, 38], [344, 36], [347, 33], [349, 31], [351, 29], [353, 28], [357, 24], [358, 23], [360, 20], [365, 15], [366, 14], [367, 13], [371, 10], [372, 9], [373, 8], [374, 6], [375, 4], [377, 2], [379, 0]]
length: 193
Here's an output that takes a little longer to generate for the same number. This one has 166 summands:

Quote:
[[0, 417], [2, 414], [5, 411], [9, 408], [11, 404], [12, 401], [13, 400], [14, 398], [15, 397], [16, 396], [18, 394], [19, 393], [21, 391], [27, 386], [28, 385], [29, 383], [34, 380], [35, 378], [39, 375], [41, 373], [42, 371], [43, 369], [46, 364], [47, 361], [48, 360], [49, 359], [50, 358], [51, 355], [52, 354], [54, 353], [55, 350], [56, 349], [62, 345], [64, 343], [65, 341], [66, 340], [68, 339], [72, 333], [74, 332], [77, 328], [78, 327], [79, 326], [80, 325], [81, 323], [82, 322], [84, 321], [91, 314], [93, 313], [94, 310], [97, 308], [98, 307], [100, 305], [101, 304], [102, 302], [107, 298], [109, 296], [112, 292], [114, 291], [117, 288], [118, 283], [119, 282], [120, 277], [125, 274], [127, 272], [135, 266], [137, 264], [138, 261], [141, 258], [148, 254], [150, 250], [151, 248], [152, 247], [153, 246], [154, 245], [155, 244], [156, 243], [157, 242], [158, 241], [163, 238], [167, 234], [171, 231], [172, 229], [177, 225], [179, 223], [180, 221], [181, 220], [184, 217], [187, 214], [193, 210], [194, 208], [196, 206], [198, 204], [203, 200], [204, 199], [210, 195], [211, 193], [218, 189], [223, 184], [227, 179], [229, 177], [231, 172], [232, 170], [233, 169], [236, 166], [245, 157], [246, 156], [251, 150], [254, 147], [255, 146], [257, 145], [258, 142], [259, 141], [264, 136], [265, 135], [266, 134], [267, 133], [268, 132], [274, 128], [279, 124], [282, 121], [286, 119], [288, 115], [290, 113], [294, 108], [295, 106], [296, 101], [297, 95], [303, 91], [305, 88], [306, 87], [307, 84], [310, 82], [313, 79], [314, 78], [322, 72], [325, 70], [326, 68], [329, 66], [330, 63], [331, 62], [332, 61], [337, 58], [340, 55], [349, 48], [350, 47], [351, 44], [355, 39], [356, 38], [357, 37], [358, 35], [359, 34], [360, 33], [363, 31], [364, 29], [365, 28], [369, 23], [374, 19], [375, 17], [376, 16], [378, 13], [380, 11], [381, 10], [385, 8], [386, 5], [388, 2], [571, 0]]
length: 166

Last fiddled with by slandrum on 2022-02-14 at 03:51
slandrum is offline   Reply With Quote
Old 2022-02-14, 04:08   #7
SmartMersenne
 
Sep 2017

139 Posts
Default

Thanks for the explanation.
SmartMersenne is offline   Reply With Quote
Old 2022-02-14, 04:44   #8
slandrum
 
Jan 2021
California

1111000112 Posts
Default

Quote:
Originally Posted by slandrum View Post
First hint is that inspection of small numbers shows that there are multiple ways to encode many of them, and if the numbers are sufficiently large, then there are many ways to encode them.
The above statement isn't completely true - if a number can be encoded as a single summand, then that's the only encoding for the number. And there are other large numbers that can only be encoded with one particular set of summands, but the vast majority of sufficiently large numbers will have many different possible encodings.
slandrum is offline   Reply With Quote
Old 2022-02-22, 22:40   #9
dg211
 
Jun 2016

110002 Posts
Default

Just curious what the smallest sets people have come up with so far are?

The best I have so far are 102 and 159, but uau's post suggests <150 is possible for the starred problem.

I found this month's puzzle a pretty tough one.
dg211 is offline   Reply With Quote
Old 2022-02-22, 23:16   #10
uau
 
Jan 2017

15210 Posts
Default

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.
uau is offline   Reply With Quote
Old 2022-02-23, 10:36   #11
dg211
 
Jun 2016

23·3 Posts
Default

I think whether the bonus question is harder than the base question probably depends a lot on the approach you take. I was stuck for a while on 146 for the base question and nowhere near the target for the bonus. I tried a different approach since then and got much better answers, but still nowhere near as good as yours.
dg211 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 07:14.


Thu Dec 1 07:14:22 UTC 2022 up 105 days, 4:42, 0 users, load averages: 1.18, 1.10, 1.05

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.

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