Detailed mathematical approach

Problem Summary

For integers \(n\ge 1\) and \(k\ge 1\), let \(P(n,k)=1\) if \(n\) can be written as a sum of exactly \(k\) primes, and let \(P(n,k)=0\) otherwise. Then

$S(n)=\sum_{i=1}^{n}\sum_{k=1}^{i} P(i,k).$

Prime repetitions are allowed, but only existence matters: even if a number has many different decompositions into \(k\) primes, the pair \((n,k)\) contributes only \(1\). The goal is to evaluate

$\sum_{r=3}^{44} S(F_r),$

where \(F_1=1\), \(F_2=1\), and \(F_r=F_{r-1}+F_{r-2}\). A direct search through all prime sums is far too expensive, so the solution turns the existence questions into a closed formula for \(S(n)\).

Mathematical Approach

The implementations split the count into the cases \(k=1\), \(k=2\), and \(k\ge 3\). The first is pure primality, the second is a parity argument combined with the Goldbach pattern used by the solution, and the third reduces to a simple inequality.

Step 1: Count admissible pairs instead of decompositions

For a fixed integer \(i\), the inner sum \(\sum_k P(i,k)\) counts how many lengths \(k\) are possible, not how many different prime partitions exist. Therefore \(S(n)\) counts admissible pairs \((i,k)\) with \(1\le i\le n\).

This viewpoint is decisive because the implementation never enumerates actual prime sums. It only determines whether a representation of length \(k\) exists.

Step 2: Handle the cases \(k=1\) and \(k=2\)

When \(k=1\), a number contributes exactly when it is prime, so

$A_1(n)=\pi(n).$

When \(k=2\), parity forces a split. In the numeric range needed by the problem, the implementation counts every even integer \(i\ge 4\) as a valid two-prime sum, giving

$A_{2,\mathrm{even}}(n)=\max\left(\left\lfloor\frac{n}{2}\right\rfloor-1,0\right).$

An odd sum of two primes must be \(2+p\) with \(p\) an odd prime, so the odd contribution is

$A_{2,\mathrm{odd}}(n)=\max\left(\pi(n-2)-1,0\right).$

Step 3: Show that for \(k\ge 3\), only the bound \(n\ge 2k\) matters

If \(n\) is written as a sum of \(k\) primes, then certainly \(n\ge 2k\), because every prime is at least \(2\).

Conversely, for the range handled by the solution, \(n\ge 2k\) is also sufficient once \(k\ge 3\). Remove \(k-3\) copies of \(2\), leaving the remainder

$n-2(k-3).$

If this remainder is odd, then it is at least \(7\), so it can be expressed as a sum of three primes by the weak Goldbach theorem. If it is even, then it is at least \(6\); write it as \(2\) plus an even number at least \(4\), and the remaining even part is handled by the same Goldbach-type two-prime case used above.

Therefore, for all \(k\ge 3\),

$P(n,k)=1 \iff n\ge 2k.$

Step 4: Sum all contributions with at least three primes

Let \(i=2t\) be even. Then the admissible lengths are \(k=3,4,\dots,t\), so the number of valid \(k\) values is \(t-2\) whenever \(t\ge 3\). Summing over all even \(i\le n\) gives

$A_{\ge 3,\mathrm{even}}(n)=\sum_{t=3}^{\lfloor n/2\rfloor}(t-2)=\max\left(\frac{(m-1)(m-2)}{2},0\right),\qquad m=\left\lfloor\frac{n}{2}\right\rfloor.$

Now let \(i=2t+1\) be odd. The admissible lengths are again \(k=3,4,\dots,t\), so the count is \(t-2\) for \(t\ge 3\). Hence

$A_{\ge 3,\mathrm{odd}}(n)=\sum_{t=3}^{\lfloor (n-1)/2\rfloor}(t-2)=\max\left(\frac{(m'-1)(m'-2)}{2},0\right),\qquad m'=\left\lfloor\frac{n-1}{2}\right\rfloor.$

Step 5: Combine the pieces into one closed formula

Adding the one-prime, two-prime, and at-least-three-prime parts yields

$\boxed{S(n)=\pi(n)+\max\left(\left\lfloor\frac{n}{2}\right\rfloor-1,0\right)+\max\left(\pi(n-2)-1,0\right)+\max\left(\frac{(m-1)(m-2)}{2},0\right)+\max\left(\frac{(m'-1)(m'-2)}{2},0\right),}$

with

$m=\left\lfloor\frac{n}{2}\right\rfloor,\qquad m'=\left\lfloor\frac{n-1}{2}\right\rfloor.$

This is exactly the expression evaluated by the implementations.

Worked Example: \(S(10)=20\)

The sample checkpoint follows immediately from the decomposition above.

First, \(\pi(10)=4\), corresponding to \(2,3,5,7\).

For \(k=2\), the even values are \(4,6,8,10\), contributing \(4\), and the odd values are \(5,7,9\), contributing \(3\).

For \(k\ge 3\), the even numbers contribute \(1+2+3=6\), because \(6\) allows only \(k=3\), \(8\) allows \(k=3,4\), and \(10\) allows \(k=3,4,5\).

The odd numbers contribute \(1+2=3\), because \(7\) allows only \(k=3\) and \(9\) allows \(k=3,4\).

Therefore

$S(10)=4+4+3+6+3=20.$

Step 6: Apply the formula to the Fibonacci inputs

Once \(S(n)\) is available in closed form, the outer task is simple: generate \(F_3,F_4,\dots,F_{44}\) iteratively and add the corresponding values. No search over prime sums is needed any more; each term reduces to two prime-counting queries and a few integer formulas.

How the Code Works

The C++, Python, and Java implementations first build a table of primes and a prefix table for \(\pi(x)\) up to five million. Larger prime-counting queries are handled by a Lehmer-style recursion with memoization, using integer square-root, cube-root, and fourth-root cutoffs to break the problem into smaller subproblems.

For each Fibonacci value \(F_r\), the implementation asks only for \(\pi(F_r)\) and \(\pi(F_r-2)\). Those two counts are inserted into the closed formula above, and the \(k=2\) and \(k\ge 3\) terms are computed directly with integer arithmetic. The final loop accumulates these values for \(r=3\) through \(44\). The same logic also reproduces the checkpoints \(S(10)=20\), \(S(100)=2402\), and \(S(1000)=248838\).

Complexity Analysis

Let \(B=5{,}000{,}000\) be the sieve limit. Building the initial prime table costs \(O(B\log\log B)\) time and \(O(B)\) memory. After that, each evaluation of \(S(n)\) performs two sublinear prime-counting queries plus \(O(1)\) arithmetic. Since the outer sum contains only \(42\) Fibonacci arguments, the total runtime is dominated by the prime-counting routine, while the closed-form part is negligible by comparison.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=543
2. Prime-counting function: Wikipedia — Prime-counting function
3. Goldbach's conjecture: Wikipedia — Goldbach's conjecture
4. Weak Goldbach theorem: Wikipedia — Goldbach's weak conjecture
5. Fibonacci number: Wikipedia — Fibonacci number