Project Euler 618 - Numbers with a given prime factor sum

Official link: https://projecteuler.net/problem=618

Thought Process

For this problem we need to focus on the primes being used, and because we are looking for decomposition of numbers where the sum of those numbers will go as high as 46,368 (24th fibonacci number) we are going to be dealing with huge numbers, so we need an efficient way to find them.

Let d(k) represent the sum of all numbers whose prime factor sum is equal to k

I made the small table on the right and noticed a few things.

In the first column - d(k) = 2*d(k-2)
If we subtract the first column from the second one (because the 2nd one contains the first one as 3 > 2) we see that same thing for p = 3, which is that d(k) = 3*d(k-3), so there is definitely a pattern here
General pattern for d(k) and a prime p is: d(k) = p*d(k-p)

After I found this it became obvious why this was true, because we are working with sum of factors but the number we are looking for are multiples.

For example for d(6) and primes <= 2, we know d(4) = 4, because of 2*2, now obviously one way to get from d(4) to d(6) is to do 2*2*2 which is exactly d(4).

We also know d(3) = 3 for primes <= 3, and do get from d(3) to d(6) all we need to do is 3*3 which is again 3*d(3)!

As usual I used my prime generation function to generate the necessary primes

Interactive Code

Input an integer (yourinput)

Code will output S(yourinput)

Note: I made a prime sieve to calculate smaller values quickly, for easier testing of your code, my actual code is included aswell

Page updated

Google Sites

Report abuse