Prime-Sum Numbers

Define function $P(n, k) = 1$ if $n$ can be written as the sum of $k$ prime numbers (with repetitions allowed), and $P(n, k) = 0$ otherwise.
For example, $P(10,2) = 1$ because $10$ can be written as either $3 + 7$ or $5 + 5$, but $P(11,2) = 0$ because no two primes can sum to $11$.
Let $S(n)$ be the sum of all $P(i,k)$ over $1 \le i,k \le n$.
For example, $S(10) = 20$, $S(100) = 2402$, and $S(1000) = 248838$.
Let $F(k)$ be the $k$th Fibonacci number (with $F(0) = 0$ and $F(1) = 1$).
Find the sum of all $S(F(k))$ over $3 \le k \le 44$.

To approach this problem, first we need to understand the nature of the function $P(n,k)$.

We know that $P(n,k) = 1$ if $n$ can be expressed as the sum of $k$ primes. Notice that if $k > n$, $P(n,k)$ would be $0$ because there are not enough prime numbers to satisfy the condition. Also, if $k$ is even but $n$ is odd (or vise versa), $P(n,k)$ must be $0$, because the sum of an odd number of even numbers is odd, and the sum of an even number of odd numbers is even. This fact about even and odd numbers applies because every prime number except for $2$ is odd, and $2$ can only be used once in any sum (because we aren’t allowing repetition).

So, it stands to reason that, for any given $n$, $P(n,k)$ would not equal $1$ for many values of $k$, and we would expect $S(n)$ to be less than $n^2$ for any given $n$. But $F(k)$ increases very rapidly as $k$ increases, and the sum of $S(F(k))$ over $3 \leq k \leq 44$ could be quite large indeed.

Unfortunately, without a computer program or some other means of calculation, it is very difficult to calculate exact values for $S(n)$ where $n$ is a Fibonacci number, let alone sums of multiple such values. Furthermore, as mentioned above, calculating $P(n,k)$ involves determining whether $n$ can be expressed as a sum of $k$ prime numbers, a problem known to be very computationally intensive, even for relatively small values.

This problem falls into a complexity class of problems called ‘combinatorial’ or ‘number theoretic’. Working precise solutions to such problems often requires a computer program. Trying to solve precise solutions for such problems by hand is often impractical, not to mention beyond the scope of this assistant.

However, we can still talk about how one might go about solving this problem with the aid of a computer.

First, for a range of likely candidates, one can build a table of all the prime numbers. This in itself is a non-trivial task, but an efficient algorithm for doing this is the Sieve or Eratosthenes.

Next, one can build a second table of all possible combinations of $k$ unique numbers taken from within the prime numbers. Using this array, it is simply a matter of looping over all the numbers less than or equal to $n$ and for each, checking against the array to see if there are any hits. If there are, increment the counter. This will give you the value of $S(n)$ for a given $n$. This needs to be done for Fibonacci numbers $3$ to $44$.

Summing those numbers up will give you the final answer. Note that as $k$ increases, the Fibonacci numbers grow exponentially, and the problem becomes computationally difficult to tackle. As such, you must use an algorithm optimized for dealing with large numbers and combinations.

More Answers: