20220202, 13:44  #1 
Jul 2015
2×19 Posts 
February 2022

20220203, 07:41  #2 
Jan 2017
5·31 Posts 
Better puzzle this time IMO  some of the recent puzzles have just asked to implement a straightforward bruteforce search with little actual "puzzle" component that would require figuring out anything nonobvious, 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 length200 standard question would be more than enough for the length300 bonus too).

20220213, 20:05  #3 
"Max"
Jun 2016
Toronto
929 Posts 
My glitchy Python code produced a nostar solution with 149 summands where I practically guessed the 200digit 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. 
20220213, 20:51  #4 
Jan 2021
California
1000001011_{2} 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)] 
20220213, 23:05  #5 
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?

20220214, 03:45  #6  
Jan 2021
California
523 Posts 
Quote:
For example, I'll give here a solution to (10^2001)/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:
Quote:
Last fiddled with by slandrum on 20220214 at 03:51 

20220214, 04:08  #7 
Sep 2017
2·73 Posts 
Thanks for the explanation.

20220214, 04:44  #8 
Jan 2021
California
1013_{8} Posts 
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.

20220222, 22:40  #9 
Jun 2016
2^{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. 
20220222, 23:16  #10 
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. 
20220223, 10:36  #11 
Jun 2016
28_{10} 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.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
February 2019  Xyzzy  Puzzles  17  20190307 21:05 
February 2018  Xyzzy  Puzzles  27  20180308 06:31 
February 2017  R. Gerbicz  Puzzles  1  20170302 23:13 
February 2016  Xyzzy  Puzzles  1  20160307 02:48 
February 2015  Xyzzy  Puzzles  1  20150302 19:01 