|
2022-02-27, 06:16
|
#12 | |
|
Jan 2021
California
523 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. |
|
|
|
|
2022-02-27, 14:18
|
#13 | |
|
Sep 2017
2×73 Posts |
Quote:
|
|
|
|
|
|
2022-02-27, 20:33
|
#14 | |
|
Jan 2017
15510 Posts |
Quote:
|
|
|
|
|
|
2022-02-28, 02:40
|
#15 |
|
Jan 2017
5·31 Posts |
Improved to 68 and 100 (well below half the targets now).
|
|
|
|
|
2022-03-01, 23:29
|
#16 | |
|
Jan 2017
5×31 Posts |
Here's a not-quite-a-solution 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:
|
|
|
|
|
|
2022-03-09, 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!
|
|
|
|
|
2022-03-11, 09:05
|
#18 |
|
Jan 2021
2×3 Posts |
Solutions for february still not uploaded
Pages even gives a 404.
Good puzzles, but way to lazy puzzlemaster. |
|
|
|
|
2022-03-22, 00:56
|
#19 | ||
|
Jan 2017
100110112 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 10N because that effectively gives a smaller target number of 5N - if you have a representation of 5N, you can just add N to all the powers of 2 to get a valid representation of 10N. To generally find representations of the required form, you can consider divisibility by either 2 or 3. My best-performing 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. 625-256 = 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. 41-32 = 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 non-negative, 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 smaller-than-maximal power of 2. Note that the non-divisibility requirement implies that the powers of 2 must be decreasing - if you picked 625 - 4 = 621, 621/27 = 23, you'd get 23-2 = 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 2022-03-22 at 00:56 |
||
|
|
|
|
2022-03-23, 07:30
|
#20 | |
|
Oct 2017
2138 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. 
|
|
|
|
|
|
2022-03-23, 17:30
|
#21 |
|
Jan 2021
California
20B16 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^200-1)/9 (200 digits of 1) that's 147 in length, which is an amusing solution to the problem. |
|
|
|
|
2022-03-23, 21:59
|
#22 | |
|
Jan 2021
California
523 Posts |
Quote:
|
|
|
|
|
 |
| 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 |
