Project Euler Forum

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)

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

Ted wrote: Sat Sep 12, 2020 12:14 am 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.

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)

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

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

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

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

margaret wrote: Sun Apr 10, 2022 4:23 am ... 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!

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?

MikeTangoAlpha wrote: Tue May 28, 2024 5:26 am [...] 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.

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.

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.

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.

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

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.