mersenneforum.org February 2022
 Register FAQ Search Today's Posts Mark Forums Read

 2022-02-02, 13:44 #1 tgan   Jul 2015 37 Posts February 2022
 2022-02-03, 07:41 #2 uau   Jan 2017 15310 Posts 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).
 2022-02-13, 20:05 #3 Max0526   "Max" Jun 2016 Toronto 929 Posts 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.
 2022-02-13, 20:51 #4 slandrum   Jan 2021 California 487 Posts 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)]
 2022-02-13, 23:05 #5 SmartMersenne   Sep 2017 139 Posts 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?
2022-02-14, 03:45   #6
slandrum

Jan 2021
California

487 Posts

Quote:
 Originally Posted by SmartMersenne 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

 2022-02-14, 04:08 #7 SmartMersenne   Sep 2017 13910 Posts Thanks for the explanation.
2022-02-14, 04:44   #8
slandrum

Jan 2021
California

487 Posts

Quote:
 Originally Posted by slandrum 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.

 2022-02-22, 22:40 #9 dg211   Jun 2016 2410 Posts 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.
 2022-02-22, 23:16 #10 uau   Jan 2017 2318 Posts 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.
 2022-02-23, 10:36 #11 dg211   Jun 2016 23·3 Posts 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.

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

All times are UTC. The time now is 07:18.

Wed Dec 7 07:18:55 UTC 2022 up 111 days, 4:47, 0 users, load averages: 0.83, 0.90, 0.90