Problem 448

[Willindigo]

I have written the code to solve the problem, and my algorithm indeed solves the sample S(100)=122726 correctly.

My issue is that given the S(99999999019) portion of the question, it would take years to iterate through the entirety of the sets. Is this problem truly solvable in under 1 minute via mathematical formula or are people using distributed computing clusters to brute force some of the later problems?

Many thanks!

[Marcus_Andrews]

From the mainpage of the PE site:

Each problem has been designed according to a "one-minute rule", which means that although it may take several hours to design a successful algorithm with more difficult problems, an efficient implementation will allow a solution to be obtained on a modestly powered computer in less than one minute.

Distributed computing clusters are not necessary to solve any given problem within the minute rule.

[Willindigo]

Thank you for the response Marcus. I am a newcomer to the site so I was unsure if I was at a disadvantage due to lack of computing power. I will reexamine my code, but I have a feeling I need more math theory to solve this one more efficiently. Apparently it is a wetware problem.

[Marcus_Andrews]

Thank you for the response Marcus. I am a newcomer to the site so I was unsure if I was at a disadvantage due to lack of computing power. I will reexamine my code, but I have a feeling I need more math theory to solve this one more efficiently. Apparently it is a wetware problem.

Whenever you're stuck, there are usually older problems that will give you the tools you need to tackle the harder variants. You can also check out the solution forums (which you gain access to when you solve a problem) to learn some of the more advanced techniques that other solvers have used.

[keith-cancel]

I was looking at this problem as well, and I have an algorithm that solves the problem with about O(n^2) time complexity but that is huge for this problem. I am also perplexed as I don't really see an other way to approach it.

[keith-cancel]

Also when I Just run a loop just from 1 to 99999999019 it takes 249.83 seconds. I am using C++ so this makes me wonder is it even possible to do under a minute? Hmm...

[Marcus_Andrews]

Sometimes you have to find a way that is better than O(N) time complexity.

[keith-cancel]

I guess before keep trying to figure this out. Is this problem possible for someone with only Calc 2 and some basic discrete mathematics knowledge to solve?

[keith-cancel]

I guess before keep trying to figure this out. Is this problem possible for someone with only Calc 2 and some basic discrete mathematics knowledge to solve? I can solve the example in the problem but the number is soo huge and don't really see way to get below O(n). I can only see maybe O(n log(n) maybe?

[hk]

One of most important concepts behind Project Euler is inductive self learning.
That means that by solving the problems one gradually gathers the knowledge to solve other problems. (Greatly enhanced by reading the entries in the fora).
However, this also means that it might be the case that one has to have solved some previous problems to be able to solve a higher numbered problem.
When one jumps straight to some of the most recent problems chances are high that one hasn't gathered enough knowledge from previous problems yet.
I actually doubt that formal learning to whatever level will be enough to solve some of the problems although it might help a bit.
One simply must have the patience to solve some lower numered problems first.