20220227, 06:16  #12  
Jan 2021
California
2^{2}·131 Posts 
Quote:
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. 

20220227, 14:18  #13  
Sep 2017
2×73 Posts 
Quote:


20220227, 20:33  #14 
Jan 2017
5·31 Posts 

20220228, 02:40  #15 
Jan 2017
5·31 Posts 
Improved to 68 and 100 (well below half the targets now).

20220301, 23:29  #16  
Jan 2017
5×31 Posts 
Here's a notquiteasolution 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:


20220309, 08:30  #17 
Sep 2017
2·73 Posts 
The new puzzlemaster has outdone himself and is now updating the website less frequently than a month!

20220311, 09:05  #18 
Jan 2021
110_{2} Posts 
Solutions for february still not uploaded
Pages even gives a 404.
Good puzzles, but way to lazy puzzlemaster. 
20220322, 00:56  #19  
Jan 2017
5·31 Posts 
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:
Quote:
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 10^{N} because that effectively gives a smaller target number of 5^{N}  if you have a representation of 5^{N}, you can just add N to all the powers of 2 to get a valid representation of 10^{N}. To generally find representations of the required form, you can consider divisibility by either 2 or 3. My bestperforming 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. 625256 = 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. 4132 = 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 nonnegative, 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 smallerthanmaximal power of 2. Note that the nondivisibility requirement implies that the powers of 2 must be decreasing  if you picked 625  4 = 621, 621/27 = 23, you'd get 232 = 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 20220322 at 00:56 

20220323, 07:30  #20  
Oct 2017
139 Posts 
Quote:
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. 

20220323, 17:30  #21 
Jan 2021
California
1014_{8} Posts 
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^2001)/9 (200 digits of 1) that's 147 in length, which is an amusing solution to the problem. 
20220323, 21:59  #22 
Jan 2021
California
2^{2}·131 Posts 

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 