February 2022

tgan · 2022-02-02, 13:44

https://research.ibm.com/haifa/ponde...ruary2022.html

uau · 2022-02-03, 07:41

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).

Max0526 · 2022-02-13, 20:05

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.

slandrum · 2022-02-13, 20:51

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)]

SmartMersenne · 2022-02-13, 23:05

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?

slandrum · 2022-02-14, 03:45

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

SmartMersenne · 2022-02-14, 04:08

Thanks for the explanation.

slandrum · 2022-02-14, 04:44

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.

dg211 · 2022-02-22, 22:40

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.

uau · 2022-02-22, 23:16

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.

dg211 · 2022-02-23, 10:36

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.

2022-02-02, 13:44	#1
tgan Jul 2015 2·19 Posts	February 2022 https://research.ibm.com/haifa/ponde...ruary2022.html

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

2022-02-03, 07:41	#2
uau Jan 2017 5×31 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 20B₁₆ 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 2·73 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, 04:08	#7
SmartMersenne Sep 2017 10010010₂ Posts	Thanks for the explanation.

2022-02-22, 22:40	#9
dg211 Jun 2016 2²×7 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 5·31 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 11100₂ 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.