Problem 719

[scienalc]

My algorithm found 7 S-Numbers lesser or equal than 10000 with a sum of 31233. The given sum is 41333, however.

Just to make clear I understood the problem statement, please confirm or correct the following statements:

• only addition is allowed, i.e. one can't subtract or similar

• the order of the digits must me observed, i.e. it is not allowed to convert 6724 to 62 + 7 + 4, for example

I also manually looked through the first 100 numbers and didn't find any that could meet the criteria.

These are the S-Numbers my algorithm found: 81, 1296, 2025, 3025, 6724, 8281, 9801. Which am I missing? (I don't consider them spoilers, as they don't reveal anything about the algorithm, but if they are, feel free to remove them)

[Ted]

You'll smack your forehead when you find the missing 10100. Just remember that zeros can be addends.

[scienalc]

You'll smack your forehead when you find the missing 10100. Just remember that zeros can be addends.

I did, I literally did. The error wasn't even in the core part of the algorithm, but in the part of code that determines the number of digits - it was off by one in those cases.

[oleglyamin]

Can someone confirm there's only 190 S-numbers satisfying <= 10^11? If not, how far off am I?

EDIT: Never mind. Should have read the statement more carefully. (facepalm)

[gorees]

You have overlooked (as I did) even powers of 10, 10^2, 10^4... They are S numbers

[margaret]

I am having a lot of trouble getting it to run in under a minute. I usually start with a brute force and then try to optimize it from there. Is there something I'm missing with how to check numbers? A lot of other problems you can throw out a lot of numbers (like evens or odds or primes, etc.), but it looks like I'll have to check every number....

[oms1953]

My S-Numbers are [1, 81, 100, 1296, 6724, 8281,9801] . Summing to 26284.

[oms1953]

I got it right already. I needed to exclude #1 as an S-number and include 2 pairs of 2-digits in the combination.

[quintus-veranius]

... but it looks like I'll have to check every number....

If you stare long enough on the numbers in the problem description you'll indeed find a easy recognizable pattern how to prune the search space!

[MikeTangoAlpha]

I am working on a solution for this problem, and unless I am missing something obvious (which might very well be the case ), I don't feel that this should be a 5% difficulty. At least compared to other 5% problems, this one requires much more work to get a working and efficient algorithm going.

Or is it really much simpler than I imagine, and we don't need to actually check all "digit-partitions" of N to test if any one sums to the square root?

[philiplu]

[...] I don't feel that this should be a 5% difficulty [...] Or is it really much simpler than I imagine [...]

The thing to remember is that the difficulty is set mechanically. It's not a judgement call by anyone, just an algorithm that looks at how quickly a problem reaches 100 solvers [*]. And this one reached 100 solvers in under 1h20m after it was published, so there were plenty of people who found a quick solution. So yes, chances are good it's simpler than you imagine.

I'll grant, though, that 5% on a problem in the 700s might be very different than 5% in the first 100 problems. There are a lot of solvers who've seen problems like this before and can find an answer quickly. So maybe it would have been 10% or 15% if it had appeared much earlier, but even then, the techniques to solve it can't be very complicated.

[*] Mostly. As far as I know, the exact details haven't been explained, but rarely, a problem's difficulty will change long after reaching 100 solvers, so there's something more going on.

[pim.mfs.0]

The way I am solving this problem, it seems like quite a bit more of effort than a 5% problem in the first 100 problems. BTW, while the Problem Development Team was developing this problem, did they intend for the solvers to pick a tool like Mathematica or Python 3.12+ to solve this problem? The way I am solving this problem, without some of Python 3.12+'s built-in's + libraries it would have needed quite a bit more effort.

[pjt33]

I can't speak to someone else's intentions, but my Python solution uses no built-ins or libraries at all and runs in pypy3 in 20 seconds.

[pim.mfs.0]

I just took the problem definition and translated it into code with the one obvious optimization. This required use of Python3's libraries and built-ins. It took about 117 seconds in PyPy3. Will take a look at your code if it is posted in the thread.

[philiplu]

Take a look at the python code in the first forum post, by aaazalea. Only library functions I see there are print() and range(). Code takes 1 second on my machine under pypy (admittedly, I have a fast PC with an AMD 9950X that's only about 6 months old, but even on my previous ancient PC, that would only be about 6 seconds). Takes 13.7s in CPython, so nice showing by pypy, but nothing extraordinary (I've seen 50x speedups on other code).

[pim.mfs.0]

I saw aaazalea's solution in Python, I do not fully understand how it works. In fact, I am doing what aaazalea's solution is doing, but without recursion. I saw the other non-trivial optimization (which has a very trivial proof) and now am able to solve the problem in under 30 seconds on PyPy.