WARNING: The text below provides a guidance for a Project Euler problem.
If you pride yourself in tackling problems entirely on your own, you are encouraged to exit this post right now.
If you are simply looking for a hint for the problem, please visit the »Project Euler’s official forum«. You may find some hints here, but if you don’t want your problem spoiled, scroll cautiously.
If you are looking for a readily available copy/paste answer, you will not find it here. All of the code snippets in the post have been stripped of some crucial lines (these are clearly marked). It is my aim that anyone able to replicate the answer based on such snippets will have to understand the solution conceptually. At that point, by virtue of learning something new, I believe he deserves it anyway.
Guidance for future problems will not be published before 100 people have solved the problem and there are at least two more recent problems.
Numbers with a given prime factor sum
Let be the function giving the sum of all prime factors of (with prime decomposition ), with multiplicity. The problem revolves about computing the sum of all possible ’s with a fixed value :
A reasonable approach to try for this sort of problem is dynamic programming, which turns out to give a fast enough solution. In order to compute , we will vary over possible ’s and the maximal prime in the factorisation of . Define to be the sum of all possible ’s such that and only the first primes appear in the prime factorization of . Clearly, , where is the index of the first prime greater than (If a greater prime than appeared in the factorization of , we couldn’t have ). Formally:
This can be split into two sums according to whether or , obtaining a recursive relationship (Or more easily, one can just persuade himself that the relationship holds):
The biggest for which we will be computing is from the problem statement the 24th Fibonacci number, that is 75025. The fact that only depends on and will allow us to compute the values iteratively in columns without storing more than the previous column. All in all, with precomputing the Fibonacci numbers and sufficiently many primes, the whole solution can be compressed just to a few lines:
The runtime of this piece of code on my computer with PyPy3 is about 30 seconds.
Generating functions approach
Let’s now venture into a more mathematical approach using generating functions. We are looking for a generating function of the sequence , that is, a (formal) representation:
To see that the coefficient of in the expanded version of the product is indeed , one can just see that once the product is expanded, any terms are precisely those where such that . Summing them up, the coefficient of is precisely . Now, using the fact that each is a formal geometric series, we can sum it up to obtain . Thus:
This can be implemented in Julia plainly as it is, without any optimisations, which returns the result in about 6 minutes.