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)\).
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.
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.
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).$$
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.$$
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.$$
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.
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.$$
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.
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\).
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.
Für ganze Zahlen \(n\ge 1\) und \(k\ge 1\) sei \(P(n,k)=1\), falls sich \(n\) als Summe von genau \(k\) Primzahlen schreiben lässt, und \(P(n,k)=0\) sonst. Dann ist
$$S(n)=\sum_{i=1}^{n}\sum_{k=1}^{i} P(i,k).$$
Wiederholungen von Primzahlen sind erlaubt, aber es zählt nur die Existenz: Selbst wenn es viele verschiedene Zerlegungen in \(k\) Primzahlen gibt, trägt das Paar \((n,k)\) nur \(1\) bei. Gesucht ist
$$\sum_{r=3}^{44} S(F_r),$$
wobei \(F_1=1\), \(F_2=1\) und \(F_r=F_{r-1}+F_{r-2}\) die Fibonacci-Folge ist. Eine direkte Suche über alle Primzahlsummen wäre viel zu teuer, daher formt die Lösung die Existenzbedingungen in eine geschlossene Formel für \(S(n)\) um.
Die Implementierungen trennen die Fälle \(k=1\), \(k=2\) und \(k\ge 3\). Der erste Fall ist reine Primzahlerkennung, der zweite kombiniert ein Paritätsargument mit dem in der Lösung verwendeten Goldbach-Muster, und der dritte fällt auf eine einfache Ungleichung zurück.
Für ein festes \(i\) zählt die innere Summe \(\sum_k P(i,k)\), für wie viele Längen \(k\) überhaupt eine Darstellung existiert, nicht wie viele verschiedene Primzahlpartitionen es gibt. Also zählt \(S(n)\) die zulässigen Paare \((i,k)\) mit \(1\le i\le n\).
Genau dieser Perspektivwechsel macht die Aufgabe einfach genug: Die Implementierung konstruiert keine Summen explizit, sondern entscheidet nur, ob eine Darstellung der Länge \(k\) existiert.
Für \(k=1\) ist die Situation direkt: Genau die Primzahlen tragen bei, also
$$A_1(n)=\pi(n).$$
Für \(k=2\) entscheidet die Parität. Im Zahlenbereich der Aufgabe behandelt die Implementierung jede gerade Zahl \(i\ge 4\) als zulässige Summe zweier Primzahlen. Daher ist
$$A_{2,\mathrm{even}}(n)=\max\left(\left\lfloor\frac{n}{2}\right\rfloor-1,0\right).$$
Eine ungerade Summe aus zwei Primzahlen muss die Form \(2+p\) mit einer ungeraden Primzahl \(p\) haben. Deshalb erhält man
$$A_{2,\mathrm{odd}}(n)=\max\left(\pi(n-2)-1,0\right).$$
Ist \(n\) eine Summe aus \(k\) Primzahlen, dann gilt zwingend \(n\ge 2k\), weil jede Primzahl mindestens \(2\) ist.
Umgekehrt ist für den von der Lösung behandelten Bereich \(n\ge 2k\) auch hinreichend, sobald \(k\ge 3\). Man zieht \(k-3\) Kopien der Primzahl \(2\) ab und erhält den Rest
$$n-2(k-3).$$
Ist dieser Rest ungerade, dann ist er mindestens \(7\) und damit nach dem schwachen Goldbach-Satz eine Summe aus drei Primzahlen. Ist er gerade, dann ist er mindestens \(6\); man schreibt ihn als \(2\) plus eine gerade Zahl \(\ge 4\), und dieser gerade Teil fällt wieder unter den schon benutzten Zweiprimzahlen-Fall.
Somit gilt für alle \(k\ge 3\)
$$P(n,k)=1 \iff n\ge 2k.$$
Sei \(i=2t\) gerade. Dann sind genau die Längen \(k=3,4,\dots,t\) zulässig, also gibt es \(t-2\) mögliche Werte von \(k\), sobald \(t\ge 3\). Summiert man das über alle geraden \(i\le n\), erhält man
$$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.$$
Nun sei \(i=2t+1\) ungerade. Auch hier sind die zulässigen Längen \(k=3,4,\dots,t\), also wieder \(t-2\) Stück für \(t\ge 3\). Daher folgt
$$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.$$
Die Summe der Beiträge für eine Primzahl, zwei Primzahlen und mindestens drei Primzahlen ist
$$\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),}$$
mit
$$m=\left\lfloor\frac{n}{2}\right\rfloor,\qquad m'=\left\lfloor\frac{n-1}{2}\right\rfloor.$$
Genau diesen Ausdruck werten die Implementierungen aus.
Der Kontrollwert aus der Aufgabenstellung folgt sofort aus der Zerlegung.
Zunächst ist \(\pi(10)=4\), also tragen \(2,3,5,7\) den Ein-Primzahl-Fall.
Für \(k=2\) liefern die geraden Zahlen \(4,6,8,10\) den Beitrag \(4\), und die ungeraden Zahlen \(5,7,9\) liefern den Beitrag \(3\).
Für \(k\ge 3\) ergibt sich bei geraden Zahlen \(1+2+3=6\), weil \(6\) nur \(k=3\) erlaubt, \(8\) die Werte \(k=3,4\) und \(10\) die Werte \(k=3,4,5\).
Bei ungeraden Zahlen erhält man \(1+2=3\), denn \(7\) erlaubt nur \(k=3\) und \(9\) erlaubt \(k=3,4\).
Also gilt
$$S(10)=4+4+3+6+3=20.$$
Sobald \(S(n)\) in geschlossener Form vorliegt, ist die äußere Aufgabe einfach: Man erzeugt \(F_3,F_4,\dots,F_{44}\) iterativ und addiert die zugehörigen Werte. Eine Suche nach Primzahlsummen ist dann nicht mehr nötig; jeder Summand reduziert sich auf zwei Primzahlzählungen und einige direkte Ganzzahlformeln.
Die C++-, Python- und Java-Implementierungen bauen zuerst eine Primzahlliste und eine Präfixtabelle für \(\pi(x)\) bis fünf Millionen auf. Für größere Anfragen nach \(\pi(x)\) verwenden sie eine Lehmer-artige Rekursion mit Memoisierung; dabei dienen ganzzahlige Quadratwurzel-, Kubikwurzel- und vierte-Wurzel-Schranken zur Aufteilung in kleinere Teilprobleme.
Für jeden Fibonacci-Wert \(F_r\) benötigt die Implementierung nur \(\pi(F_r)\) und \(\pi(F_r-2)\). Diese beiden Werte werden in die geschlossene Formel eingesetzt, und die Beiträge für \(k=2\) sowie \(k\ge 3\) werden direkt mit Ganzzahlarithmetik berechnet. Anschließend summiert die Hauptschleife diese Werte für \(r=3\) bis \(44\). Dieselbe Logik reproduziert auch die Kontrollwerte \(S(10)=20\), \(S(100)=2402\) und \(S(1000)=248838\).
Sei \(B=5{,}000{,}000\) die Siebgrenze. Der Aufbau der Primzahlliste kostet \(O(B\log\log B)\) Zeit und \(O(B)\) Speicher. Danach benötigt jede Auswertung von \(S(n)\) zwei sublineare Primzahlzählabfragen sowie \(O(1)\)-Arithmetik. Da die äußere Summe nur \(42\) Fibonacci-Argumente enthält, wird die Gesamtlaufzeit praktisch vollständig von der Primzahlzählroutine bestimmt; der geschlossene Teil fällt dagegen kaum ins Gewicht.
\(n\ge 1\) ve \(k\ge 1\) için \(P(n,k)\), \(n\) sayısı tam olarak \(k\) asalın toplamı olarak yazılabiliyorsa \(1\), aksi halde \(0\) olsun. O zaman
$$S(n)=\sum_{i=1}^{n}\sum_{k=1}^{i} P(i,k).$$
Aynı asalın birden fazla kez kullanılması serbesttir; ancak sadece varlık bilgisi önemlidir. Yani bir sayı \(k\) asalın toplamı olarak birçok farklı biçimde yazılabiliyorsa bile \((n,k)\) çifti yalnızca \(1\) katkı yapar. Amaç
$$\sum_{r=3}^{44} S(F_r)$$
toplamını bulmaktır; burada \(F_1=1\), \(F_2=1\) ve \(F_r=F_{r-1}+F_{r-2}\) Fibonacci dizisidir. Tüm asal toplamlarını doğrudan aramak çok pahalı olduğundan, çözüm \(S(n)\) için kapalı bir formül kurar.
Uygulamalar sayımı \(k=1\), \(k=2\) ve \(k\ge 3\) durumlarına ayırır. İlk parça doğrudan asallık sayımıdır, ikinci parça paritye ve çözümün kullandığı Goldbach desenine dayanır, üçüncü parça ise basit bir eşitsizliğe indirgenir.
Sabit bir \(i\) için iç toplam \(\sum_k P(i,k)\), kaç farklı asal bölüşümü olduğunu değil, kaç farklı uzunluğun mümkün olduğunu sayar. Dolayısıyla \(S(n)\), \(1\le i\le n\) aralığındaki uygun \((i,k)\) çiftlerinin toplamıdır.
Bu bakış açısı kritiktir; çünkü uygulama gerçek asal toplamlarını üretmez. Yalnızca uzunluğu \(k\) olan en az bir temsil bulunup bulunmadığını belirler.
\(k=1\) olduğunda katkı yapan sayılar tam olarak asallardır. Bu yüzden
$$A_1(n)=\pi(n).$$
\(k=2\) için parite belirleyicidir. Problemin ihtiyaç duyduğu sayısal aralıkta uygulama, \(i\ge 4\) olan her çift sayıyı iki asallı geçerli bir toplam olarak sayar. Böylece
$$A_{2,\mathrm{even}}(n)=\max\left(\left\lfloor\frac{n}{2}\right\rfloor-1,0\right).$$
İki asalın toplamı tek ise biçim zorunlu olarak \(2+p\) olur; burada \(p\) tek bir asaldır. Bu nedenle tek katkı
$$A_{2,\mathrm{odd}}(n)=\max\left(\pi(n-2)-1,0\right)$$
şeklindedir.
\(n\), \(k\) asalın toplamıysa her asal en az \(2\) olduğundan mutlaka \(n\ge 2k\) olmalıdır.
Ters yönde, çözümün kapsadığı aralıkta \(k\ge 3\) iken \(n\ge 2k\) koşulu aynı zamanda yeterlidir. \(k-3\) tane \(2\) çıkaralım. Geriye
$$n-2(k-3)$$
kalır. Bu kalan tek ise en az \(7\)'dir ve zayıf Goldbach teoremi sayesinde üç asalın toplamı olarak yazılabilir. Kalan çift ise en az \(6\)'dır; bunu \(2\) artı en az \(4\) olan bir çift sayı şeklinde yazarız ve geriye kalan çift parça yukarıdaki iki asallı Goldbach durumuna düşer.
Böylece tüm \(k\ge 3\) için
$$P(n,k)=1 \iff n\ge 2k$$
sonucu elde edilir.
\(i=2t\) çift olsun. O zaman uygun uzunluklar \(k=3,4,\dots,t\) olur; yani \(t\ge 3\) için geçerli \(k\) sayısı \(t-2\)'dir. Tüm \(i\le n\) çift değerleri üzerinden toplayınca
$$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$$
elde edilir. Şimdi \(i=2t+1\) tek olsun. Uygun uzunluklar yine \(k=3,4,\dots,t\) olduğundan sayı \(t-2\)'dir. Dolayısıyla
$$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.$$
Bir asal, iki asal ve en az üç asal durumları toplanınca
$$\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),}$$
burada
$$m=\left\lfloor\frac{n}{2}\right\rfloor,\qquad m'=\left\lfloor\frac{n-1}{2}\right\rfloor$$
olur. Uygulamanın doğrudan hesapladığı ifade tam olarak budur.
Verilen kontrol değeri bu ayrışım üzerinden hemen görülür.
Önce \(\pi(10)=4\), yani \(2,3,5,7\) tek asallı katkı yapar.
\(k=2\) için çift sayılar \(4,6,8,10\) olduğundan katkı \(4\), tek sayılar \(5,7,9\) olduğundan katkı \(3\) gelir.
\(k\ge 3\) için çift sayılar \(1+2+3=6\) katkı verir; çünkü \(6\) yalnızca \(k=3\), \(8\) ise \(k=3,4\), \(10\) ise \(k=3,4,5\) uzunluklarını destekler.
Tek sayılar da \(1+2=3\) katkı verir; çünkü \(7\) yalnızca \(k=3\), \(9\) ise \(k=3,4\) için uygundur.
Sonuç olarak
$$S(10)=4+4+3+6+3=20.$$
\(S(n)\) kapalı biçimde elde edildikten sonra dış problem basitleşir: \(F_3,F_4,\dots,F_{44}\) ardışık olarak üretilir ve karşılık gelen değerler toplanır. Artık asal toplamlarını aramaya gerek yoktur; her terim yalnızca iki asal sayım sorgusu ve birkaç tamsayı formülüne indirgenir.
C++, Python ve Java uygulamaları önce beş milyona kadar olan asal sayıları ve \(\pi(x)\) önek tablosunu üretir. Daha büyük \(\pi(x)\) sorguları için, tam sayı karekök, küpkök ve dördüncü kök eşiklerini kullanan, belleklemeli Lehmer tarzı özyinelemeli bir yöntem uygulanır.
Her Fibonacci değeri \(F_r\) için uygulama yalnızca \(\pi(F_r)\) ve \(\pi(F_r-2)\) değerlerini ister. Bu iki sayı yukarıdaki kapalı formüle yerleştirilir; \(k=2\) ve \(k\ge 3\) terimleri ise doğrudan tamsayı aritmetiğiyle hesaplanır. Son döngü bu değerleri \(r=3\) ile \(44\) arasında toplar. Aynı mantık kontrol noktaları olan \(S(10)=20\), \(S(100)=2402\) ve \(S(1000)=248838\) değerlerini de üretir.
\(B=5{,}000{,}000\) eleme sınırı olsun. İlk asal tablosunun kurulması \(O(B\log\log B)\) zaman ve \(O(B)\) bellek gerektirir. Bundan sonra her \(S(n)\) hesabı iki adet doğrusal-altı asal sayım sorgusu ve \(O(1)\) aritmetik yapar. Dış toplam yalnızca \(42\) Fibonacci girdisi içerdiği için toplam çalışma süresini esas olarak asal sayım yordamı belirler; kapalı form kısmının maliyeti bunun yanında ihmal edilebilir kalır.
Para enteros \(n\ge 1\) y \(k\ge 1\), definimos \(P(n,k)=1\) si \(n\) puede escribirse como suma de exactamente \(k\) números primos, y \(P(n,k)=0\) en caso contrario. Entonces
$$S(n)=\sum_{i=1}^{n}\sum_{k=1}^{i} P(i,k).$$
Se permite repetir primos, pero solo importa la existencia: aunque haya muchas descomposiciones distintas en \(k\) primos, el par \((n,k)\) aporta solo \(1\). El objetivo es calcular
$$\sum_{r=3}^{44} S(F_r),$$
donde \(F_1=1\), \(F_2=1\) y \(F_r=F_{r-1}+F_{r-2}\) es la sucesión de Fibonacci. Una búsqueda directa sobre todas las sumas de primos sería inviable, así que la solución convierte la cuestión de existencia en una fórmula cerrada para \(S(n)\).
Las implementaciones separan el conteo en los casos \(k=1\), \(k=2\) y \(k\ge 3\). El primer caso es puro conteo de primos, el segundo usa un argumento de paridad junto con el patrón de Goldbach adoptado por la solución, y el tercero se reduce a una desigualdad muy simple.
Para un valor fijo de \(i\), la suma interior \(\sum_k P(i,k)\) cuenta cuántas longitudes \(k\) son posibles, no cuántas particiones primas distintas existen. Por tanto, \(S(n)\) cuenta los pares admisibles \((i,k)\) con \(1\le i\le n\).
Esta reformulación es la clave, porque la implementación nunca enumera todas las sumas primas concretas. Solo decide si existe al menos una representación de longitud \(k\).
Cuando \(k=1\), contribuyen exactamente los números primos, así que
$$A_1(n)=\pi(n).$$
Cuando \(k=2\), la paridad obliga a separar el problema. En el rango numérico relevante, la implementación cuenta todo número par \(i\ge 4\) como una suma válida de dos primos, de modo que
$$A_{2,\mathrm{even}}(n)=\max\left(\left\lfloor\frac{n}{2}\right\rfloor-1,0\right).$$
Una suma impar de dos primos debe tener la forma \(2+p\), donde \(p\) es un primo impar. Por ello, la contribución impar es
$$A_{2,\mathrm{odd}}(n)=\max\left(\pi(n-2)-1,0\right).$$
Si \(n\) se expresa como suma de \(k\) primos, necesariamente \(n\ge 2k\), porque cada primo es al menos \(2\).
En sentido inverso, dentro del rango tratado por la solución, \(n\ge 2k\) también es suficiente cuando \(k\ge 3\). Quitamos \(k-3\) copias del primo \(2\), y queda
$$n-2(k-3).$$
Si ese resto es impar, entonces es al menos \(7\), por lo que puede escribirse como suma de tres primos mediante el teorema débil de Goldbach. Si es par, entonces es al menos \(6\); se escribe como \(2\) más un número par de al menos \(4\), y esa parte par queda cubierta por el mismo caso de dos primos usado arriba.
Por tanto, para todo \(k\ge 3\),
$$P(n,k)=1 \iff n\ge 2k.$$
Sea \(i=2t\) par. Entonces las longitudes admisibles son \(k=3,4,\dots,t\), así que el número de valores válidos de \(k\) es \(t-2\) siempre que \(t\ge 3\). Sumando sobre todos los \(i\) pares con \(i\le n\), obtenemos
$$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.$$
Ahora sea \(i=2t+1\) impar. Las longitudes admisibles vuelven a ser \(k=3,4,\dots,t\), de modo que el conteo es otra vez \(t-2\) para \(t\ge 3\). Por consiguiente,
$$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.$$
Al sumar los casos de una, dos y al menos tres primos se obtiene
$$\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),}$$
con
$$m=\left\lfloor\frac{n}{2}\right\rfloor,\qquad m'=\left\lfloor\frac{n-1}{2}\right\rfloor.$$
Esa es exactamente la expresión que evalúan las implementaciones.
El valor de control del enunciado aparece de inmediato.
Primero, \(\pi(10)=4\), correspondientes a \(2,3,5,7\).
Para \(k=2\), los valores pares \(4,6,8,10\) aportan \(4\), y los valores impares \(5,7,9\) aportan \(3\).
Para \(k\ge 3\), los números pares aportan \(1+2+3=6\), porque \(6\) solo admite \(k=3\), \(8\) admite \(k=3,4\) y \(10\) admite \(k=3,4,5\).
Los números impares aportan \(1+2=3\), porque \(7\) solo admite \(k=3\) y \(9\) admite \(k=3,4\).
Así,
$$S(10)=4+4+3+6+3=20.$$
Una vez obtenida la forma cerrada de \(S(n)\), la tarea exterior es directa: se generan \(F_3,F_4,\dots,F_{44}\) iterativamente y se suman los valores correspondientes. Ya no es necesario buscar descomposiciones en primos; cada término se reduce a dos consultas de conteo de primos y unas pocas fórmulas enteras.
Las implementaciones en C++, Python y Java construyen primero una tabla de primos y una tabla prefijo para \(\pi(x)\) hasta cinco millones. Las consultas grandes de \(\pi(x)\) se resuelven con una recursión de estilo Lehmer con memoización, usando cortes en la raíz cuadrada, cúbica y cuarta para dividir el trabajo en subproblemas más pequeños.
Para cada valor de Fibonacci \(F_r\), la implementación solo necesita \(\pi(F_r)\) y \(\pi(F_r-2)\). Esos dos conteos se sustituyen en la fórmula cerrada anterior, y los términos de \(k=2\) y \(k\ge 3\) se calculan directamente con aritmética entera. El bucle final acumula estos valores para \(r=3\) hasta \(44\). La misma lógica reproduce además los puntos de control \(S(10)=20\), \(S(100)=2402\) y \(S(1000)=248838\).
Sea \(B=5{,}000{,}000\) el límite del cribado. Construir la tabla inicial de primos cuesta \(O(B\log\log B)\) tiempo y \(O(B)\) memoria. Después, cada evaluación de \(S(n)\) realiza dos consultas sublineales a la función contadora de primos y \(O(1)\) aritmética adicional. Como la suma exterior contiene solo \(42\) argumentos de Fibonacci, el tiempo total queda dominado por la rutina de conteo de primos; la parte cerrada es comparativamente despreciable.
对整数 \(n\ge 1\) 和 \(k\ge 1\)，定义 \(P(n,k)=1\) 当且仅当 \(n\) 可以表示成恰好 \(k\) 个质数之和；否则 \(P(n,k)=0\)。于是
$$S(n)=\sum_{i=1}^{n}\sum_{k=1}^{i} P(i,k).$$
这里允许质数重复使用，但只关心“是否存在”这种表示，而不关心表示方式有多少种。也就是说，即使某个 \((n,k)\) 对应很多不同的质数拆分，它对 \(S(n)\) 的贡献仍然只有 \(1\)。目标是求
$$\sum_{r=3}^{44} S(F_r),$$
其中 \(F_1=1\)、\(F_2=1\)、\(F_r=F_{r-1}+F_{r-2}\) 是 Fibonacci 数列。若直接枚举所有质数和，成本会极高，因此解法把“是否能表示”改写成 \(S(n)\) 的闭式计数公式。
实现把计数拆成三部分：\(k=1\)、\(k=2\) 和 \(k\ge 3\)。第一部分只是质数计数；第二部分依赖奇偶性分析以及解法采用的 Goldbach 型结论；第三部分则简化为一个非常直接的不等式条件。
对固定的 \(i\)，内层求和 \(\sum_k P(i,k)\) 统计的是“有多少个长度 \(k\) 可行”，而不是“有多少种不同的质数拆分”。因此 \(S(n)\) 的真正含义，是所有满足 \(1\le i\le n\) 且至少存在一种长度为 \(k\) 的质数表示的 \((i,k)\) 对的个数。
这一点非常关键，因为实现过程中根本不枚举具体的质数和，只判断某个长度 \(k\) 是否至少存在一种表示即可。
当 \(k=1\) 时，只有质数本身才能贡献，因此
$$A_1(n)=\pi(n).$$
当 \(k=2\) 时，奇偶性立刻把情况分开。在本题涉及的数值范围内，实现把所有满足 \(i\ge 4\) 的偶数都视为可写成两个质数之和，因此偶数部分的贡献为
$$A_{2,\mathrm{even}}(n)=\max\left(\left\lfloor\frac{n}{2}\right\rfloor-1,0\right).$$
而两个质数的和若是奇数，则必定只能是 \(2+p\)，其中 \(p\) 是奇质数，所以奇数部分的贡献为
$$A_{2,\mathrm{odd}}(n)=\max\left(\pi(n-2)-1,0\right).$$
如果 \(n\) 能表示成 \(k\) 个质数之和，那么显然必须有 \(n\ge 2k\)，因为每个质数至少都是 \(2\)。
反过来，在本解法处理的范围里，只要 \(k\ge 3\) 且 \(n\ge 2k\)，就一定可以构造出表示。做法是先拿掉 \(k-3\) 个 \(2\)，剩下
$$n-2(k-3).$$
如果这个余数是奇数，那么它至少为 \(7\)，可由弱 Goldbach 定理写成三个质数之和。如果这个余数是偶数，那么它至少为 \(6\)；把它写成 \(2\) 加上一个至少为 \(4\) 的偶数，而这个偶数部分正好落回上面已经使用过的“两质数”情形。
因此，对所有 \(k\ge 3\) 都有
$$P(n,k)=1 \iff n\ge 2k.$$
先看偶数 \(i=2t\)。此时允许的长度恰好是 \(k=3,4,\dots,t\)，所以当 \(t\ge 3\) 时，可行的 \(k\) 个数为 \(t-2\)。把所有不超过 \(n\) 的偶数都加起来，得到
$$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.$$
再看奇数 \(i=2t+1\)。允许的长度同样是 \(k=3,4,\dots,t\)，因此贡献仍然是 \(t-2\)。于是
$$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.$$
把“一质数”“两质数”“至少三质数”三部分加起来，就得到
$$\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),}$$
其中
$$m=\left\lfloor\frac{n}{2}\right\rfloor,\qquad m'=\left\lfloor\frac{n-1}{2}\right\rfloor.$$
这正是实现中逐项计算的表达式。
题目给出的校验值可以直接由上面的拆分得到。
首先，\(\pi(10)=4\)，对应 \(2,3,5,7\)。
当 \(k=2\) 时，偶数 \(4,6,8,10\) 贡献 \(4\)，奇数 \(5,7,9\) 贡献 \(3\)。
当 \(k\ge 3\) 时，偶数部分贡献 \(1+2+3=6\)：因为 \(6\) 只允许 \(k=3\)，\(8\) 允许 \(k=3,4\)，\(10\) 允许 \(k=3,4,5\)。
奇数部分贡献 \(1+2=3\)：因为 \(7\) 只允许 \(k=3\)，\(9\) 允许 \(k=3,4\)。
因此
$$S(10)=4+4+3+6+3=20.$$
一旦 \(S(n)\) 已经有了闭式，外层问题就很直接了：按顺序生成 \(F_3,F_4,\dots,F_{44}\)，并把对应的 \(S(F_r)\) 相加即可。此时完全不需要搜索任何质数拆分；每一项都只剩两次质数计数查询和若干常数时间的整数公式。
C++、Python 和 Java 的实现都会先构造一个到五百万为止的质数表，以及对应的 \(\pi(x)\) 前缀计数表。对于更大的 \(\pi(x)\) 查询，则使用带记忆化的 Lehmer 风格递归，并通过整数平方根、立方根和四次根阈值把大问题切分成更小的子问题。
对每个 Fibonacci 值 \(F_r\)，实现实际上只需要 \(\pi(F_r)\) 与 \(\pi(F_r-2)\)。把这两个数代回上面的闭式公式，再用整数运算直接算出 \(k=2\) 和 \(k\ge 3\) 的多项式项即可。最后一个循环把 \(r=3\) 到 \(44\) 的结果累加起来。同样的逻辑也会得到题目中的校验值 \(S(10)=20\)、\(S(100)=2402\) 和 \(S(1000)=248838\)。
设筛法上界为 \(B=5{,}000{,}000\)。预先建立质数表需要 \(O(B\log\log B)\) 时间和 \(O(B)\) 空间。之后每次计算 \(S(n)\) 只需进行两次次线性的质数计数查询，再加上 \(O(1)\) 的整数运算。由于外层总共只处理 \(42\) 个 Fibonacci 参数，所以总体运行时间主要由质数计数过程决定，闭式部分的代价相对可以忽略。
Для целых \(n\ge 1\) и \(k\ge 1\) положим \(P(n,k)=1\), если число \(n\) можно представить в виде суммы ровно \(k\) простых чисел, и \(P(n,k)=0\) в противном случае. Тогда
$$S(n)=\sum_{i=1}^{n}\sum_{k=1}^{i} P(i,k).$$
Повторения простых разрешены, но учитывается только факт существования представления: даже если разложений на \(k\) простых много, пара \((n,k)\) даёт вклад лишь \(1\). Требуется вычислить
$$\sum_{r=3}^{44} S(F_r),$$
где \(F_1=1\), \(F_2=1\), \(F_r=F_{r-1}+F_{r-2}\) — числа Фибоначчи. Прямой перебор всех сумм простых слишком дорог, поэтому решение сводит задачу к замкнутой формуле для \(S(n)\).
Реализации разбивают подсчёт на случаи \(k=1\), \(k=2\) и \(k\ge 3\). Первый случай — это просто подсчёт простых чисел, второй использует рассуждение о чётности и тот Goldbach-паттерн, на который опирается решение, а третий сводится к очень простой неравенственной проверке.
Для фиксированного \(i\) внутренняя сумма \(\sum_k P(i,k)\) считает, для скольких длин \(k\) существует хотя бы одно представление, а не число различных разбиений на простые. Значит, \(S(n)\) — это просто число допустимых пар \((i,k)\) при \(1\le i\le n\).
Именно эта точка зрения и делает задачу удобной: реализация не строит сами суммы простых, а лишь проверяет существование представления нужной длины.
При \(k=1\) вклад дают ровно простые числа, поэтому
$$A_1(n)=\pi(n).$$
При \(k=2\) всё определяется чётностью. В числовом диапазоне задачи реализация считает каждое чётное \(i\ge 4\) корректной суммой двух простых, так что
$$A_{2,\mathrm{even}}(n)=\max\left(\left\lfloor\frac{n}{2}\right\rfloor-1,0\right).$$
Нечётная сумма двух простых обязана иметь вид \(2+p\), где \(p\) — нечётное простое. Следовательно, нечётная часть равна
$$A_{2,\mathrm{odd}}(n)=\max\left(\pi(n-2)-1,0\right).$$
Если \(n\) представимо как сумма \(k\) простых, то обязательно \(n\ge 2k\), поскольку каждое простое не меньше \(2\).
Обратно, в диапазоне, который обрабатывает решение, этого условия уже достаточно при \(k\ge 3\). Уберём \(k-3\) копий числа \(2\). Останется
$$n-2(k-3).$$
Если остаток нечётный, то он не меньше \(7\), а значит представим как сумма трёх простых по слабой теореме Гольдбаха. Если остаток чётный, то он не меньше \(6\); его можно записать как \(2\) плюс чётное число не меньше \(4\), а этот чётный хвост уже покрывается тем же двухпростым Goldbach-случаем, который использовался выше.
Итак, для всех \(k\ge 3\)
$$P(n,k)=1 \iff n\ge 2k.$$
Пусть \(i=2t\) — чётное число. Тогда допустимые длины равны \(k=3,4,\dots,t\), то есть при \(t\ge 3\) имеется \(t-2\) возможных значений \(k\). Суммирование по всем чётным \(i\le n\) даёт
$$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.$$
Теперь пусть \(i=2t+1\) — нечётное число. Допустимые длины снова \(k=3,4,\dots,t\), так что вклад опять равен \(t-2\). Следовательно,
$$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.$$
Суммируя вклад от одного простого, двух простых и не менее трёх простых, получаем
$$\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),}$$
где
$$m=\left\lfloor\frac{n}{2}\right\rfloor,\qquad m'=\left\lfloor\frac{n-1}{2}\right\rfloor.$$
Именно это выражение и вычисляют реализации.
Контрольное значение из условия немедленно получается из этого разложения.
Сначала \(\pi(10)=4\), то есть вклад в случае \(k=1\) дают числа \(2,3,5,7\).
Для \(k=2\) чётные значения \(4,6,8,10\) дают вклад \(4\), а нечётные \(5,7,9\) дают вклад \(3\).
Для \(k\ge 3\) чётные числа дают \(1+2+3=6\): число \(6\) допускает только \(k=3\), число \(8\) допускает \(k=3,4\), а число \(10\) допускает \(k=3,4,5\).
Нечётные числа дают \(1+2=3\): число \(7\) допускает только \(k=3\), а число \(9\) допускает \(k=3,4\).
Итак,
$$S(10)=4+4+3+6+3=20.$$
После получения замкнутой формулы для \(S(n)\) внешняя часть задачи становится простой: числа \(F_3,F_4,\dots,F_{44}\) генерируются итеративно, и для каждого из них вычисляется значение \(S(F_r)\). Поиск разложений на простые больше не нужен; каждый член суммы сводится к двум запросам к функции \(\pi(x)\) и нескольким формулам над целыми числами.
Реализации на C++, Python и Java сначала строят список простых и префиксную таблицу значений \(\pi(x)\) до пяти миллионов. Для больших запросов \(\pi(x)\) используется рекурсия в стиле Lehmer с мемоизацией, а разбиение на подзадачи выполняется с помощью целочисленных квадратного, кубического и четвёртого корней.
Для каждого числа Фибоначчи \(F_r\) реализации фактически нужны только \(\pi(F_r)\) и \(\pi(F_r-2)\). Эти два значения подставляются в замкнутую формулу выше, а члены для \(k=2\) и \(k\ge 3\) вычисляются напрямую целочисленной арифметикой. Затем итоговый цикл суммирует результаты для \(r=3,\dots,44\). Та же логика воспроизводит и контрольные значения \(S(10)=20\), \(S(100)=2402\) и \(S(1000)=248838\).
Пусть \(B=5{,}000{,}000\) — предел предварительного решета. Построение начальной таблицы простых требует \(O(B\log\log B)\) времени и \(O(B)\) памяти. После этого каждое вычисление \(S(n)\) содержит две сублинейные процедуры подсчёта простых и \(O(1)\) дополнительной арифметики. Так как во внешней сумме всего \(42\) аргумента Фибоначчи, общее время почти полностью определяется процедурой вычисления \(\pi(x)\), а стоимость замкнутой части по сравнению с этим мала.
لأي عددين صحيحين \(n\ge 1\) و\(k\ge 1\)، نعرّف \(P(n,k)=1\) إذا كان بالإمكان كتابة \(n\) على صورة مجموع مكوّن من \(k\) أعداد أولية بالضبط، و\(P(n,k)=0\) خلاف ذلك. وعندئذ
$$S(n)=\sum_{i=1}^{n}\sum_{k=1}^{i} P(i,k).$$
يسمح بتكرار الأعداد الأولية، لكن المهم هو وجود التمثيل فقط لا عدد الطرق المختلفة. أي إن الزوج \((n,k)\) يضيف \(1\) فقط حتى لو وُجدت له عدة تفكيكات مختلفة إلى \(k\) أعداد أولية. المطلوب هو حساب
$$\sum_{r=3}^{44} S(F_r),$$
حيث \(F_1=1\)، و\(F_2=1\)، و\(F_r=F_{r-1}+F_{r-2}\) هي متتالية فيبوناتشي. البحث المباشر في جميع المجاميع الأولية مكلف جداً، لذلك يحوّل الحل سؤال الوجود إلى صيغة مغلقة للدالة \(S(n)\).
تقسم التطبيقات العد إلى الحالات \(k=1\)، و\(k=2\)، و\(k\ge 3\). الحالة الأولى مجرد عدٍّ للأعداد الأولية، والحالة الثانية تعتمد على تحليل الزوجية وعلى النمط المرتبط بغولدباخ الذي يستخدمه الحل، أما الحالة الثالثة فتنهار إلى متراجحة بسيطة جداً.
عند تثبيت \(i\)، فإن المجموع الداخلي \(\sum_k P(i,k)\) لا يعد عدد التفكيكات المختلفة، بل يعد عدد القيم الممكنة لـ\(k\) التي يوجد لها تمثيل واحد على الأقل. لذلك فإن \(S(n)\) يساوي عدد الأزواج الممكنة \((i,k)\) حيث \(1\le i\le n\).
هذه إعادة الصياغة هي الفكرة الأساسية، لأن التطبيق لا يبني جميع المجاميع الأولية فعلياً، بل يقرر فقط ما إذا كان يوجد تمثيل بطول \(k\) أم لا.
عندما يكون \(k=1\)، فإن الأعداد المساهمة هي الأعداد الأولية فقط، وبالتالي
$$A_1(n)=\pi(n).$$
وعندما يكون \(k=2\)، تصبح الزوجية هي العامل الحاسم. في المجال العددي المطلوب في هذه المسألة، يعامل التطبيق كل عدد زوجي \(i\ge 4\) على أنه مجموع صالح لعددين أوليين، ومن ثم
$$A_{2,\mathrm{even}}(n)=\max\left(\left\lfloor\frac{n}{2}\right\rfloor-1,0\right).$$
أما المجموع الفردي لعددين أوليين فلا بد أن يكون على الصورة \(2+p\)، حيث \(p\) عدد أولي فردي. لذلك تكون المساهمة الفردية
$$A_{2,\mathrm{odd}}(n)=\max\left(\pi(n-2)-1,0\right).$$
إذا كان \(n\) مجموع \(k\) أعداد أولية، فلا بد أن يكون \(n\ge 2k\)، لأن كل عدد أولي لا يقل عن \(2\).
وبالعكس، في النطاق الذي يعالجه الحل يصبح هذا الشرط كافياً أيضاً متى كان \(k\ge 3\). نحذف \(k-3\) نسخاً من العدد \(2\)، فيتبقى
$$n-2(k-3).$$
إذا كان هذا الباقي فردياً، فهو لا يقل عن \(7\)، ومن ثم يمكن كتابته كمجموع ثلاثة أعداد أولية بفضل نظرية غولدباخ الضعيفة. وإذا كان زوجياً، فهو لا يقل عن \(6\)؛ نكتبه على صورة \(2\) مضافاً إلى عدد زوجي لا يقل عن \(4\)، والجزء الزوجي المتبقي يقع تحت نفس حالة المجموع المكوّن من عددين أوليين المستخدمة أعلاه.
إذن، لكل \(k\ge 3\)،
$$P(n,k)=1 \iff n\ge 2k.$$
لنفرض أن \(i=2t\) عدد زوجي. عندئذ تكون القيم المسموح بها لـ\(k\) هي \(3,4,\dots,t\)، ولذلك يكون عدد القيم الصالحة هو \(t-2\) متى كان \(t\ge 3\). وبجمع ذلك على جميع القيم الزوجية \(i\le n\) نحصل على
$$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.$$
والآن لنفرض أن \(i=2t+1\) عدد فردي. القيم المسموح بها تبقى \(k=3,4,\dots,t\)، ولذلك تكون المساهمة مرة أخرى \(t-2\). ومن ثم
$$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.$$
بجمع مساهمات العدد الأولي الواحد، وحالتي العددين الأوليين، والحالات ذات ثلاثة أعداد أولية فأكثر، نحصل على
$$\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),}$$
حيث
$$m=\left\lfloor\frac{n}{2}\right\rfloor,\qquad m'=\left\lfloor\frac{n-1}{2}\right\rfloor.$$
وهذا هو التعبير نفسه الذي تحسبه التطبيقات مباشرة.
قيمة التحقق المعطاة في المسألة تظهر فوراً من هذا التفكيك.
أولاً، لدينا \(\pi(10)=4\)، أي إن \(2,3,5,7\) تمثل مساهمة حالة \(k=1\).
بالنسبة إلى \(k=2\)، تعطي القيم الزوجية \(4,6,8,10\) مساهمة مقدارها \(4\)، بينما تعطي القيم الفردية \(5,7,9\) مساهمة مقدارها \(3\).
وبالنسبة إلى \(k\ge 3\)، فإن الأعداد الزوجية تعطي \(1+2+3=6\)، لأن \(6\) يسمح فقط بـ\(k=3\)، و\(8\) يسمح بـ\(k=3,4\)، و\(10\) يسمح بـ\(k=3,4,5\).
أما الأعداد الفردية فتعطي \(1+2=3\)، لأن \(7\) يسمح فقط بـ\(k=3\)، و\(9\) يسمح بـ\(k=3,4\).
إذن
$$S(10)=4+4+3+6+3=20.$$
بعد الحصول على صيغة مغلقة لـ\(S(n)\)، تصبح المهمة الخارجية مباشرة: نولّد \(F_3,F_4,\dots,F_{44}\) بالتتابع، ثم نجمع القيم الموافقة. لم نعد بحاجة إلى البحث عن تفكيكات إلى أعداد أولية؛ فكل حد يختزل إلى استعلامين عن عدد الأعداد الأولية وبعض الصيغ الصحيحة البسيطة.
تبدأ تطبيقات C++ وPython وJava ببناء جدول للأعداد الأولية وجدول تراكمي لقيم \(\pi(x)\) حتى خمسة ملايين. أما الاستعلامات الأكبر عن \(\pi(x)\) فتُعالج بخوارزمية من نمط Lehmer مع تخزين النتائج الوسيطة، مع استخدام حدود الجذر التربيعي والتكعيبي والرابع لتقسيم المسألة إلى مسائل أصغر.
لكل قيمة Fibonacci من الشكل \(F_r\)، يحتاج التنفيذ فعلياً إلى \(\pi(F_r)\) و\(\pi(F_r-2)\) فقط. ثم تُوضع هاتان القيمتان في الصيغة المغلقة أعلاه، وتُحسب حدود \(k=2\) و\(k\ge 3\) مباشرةً بالحساب الصحيح. وفي النهاية تجمع الحلقة الرئيسية هذه القيم من \(r=3\) حتى \(44\). والمنهج نفسه يعيد أيضاً قيم التحقق \(S(10)=20\)، و\(S(100)=2402\)، و\(S(1000)=248838\).
لنكتب \(B=5{,}000{,}000\) لحد الغربلة. بناء جدول الأعداد الأولية الابتدائي يكلف \(O(B\log\log B)\) زمناً و\(O(B)\) ذاكرة. بعد ذلك، يحتاج كل تقييم لـ\(S(n)\) إلى استعلامين دون خطيين عن دالة عدّ الأوليات، إضافة إلى حسابات من رتبة \(O(1)\). وبما أن المجموع الخارجي يحتوي على \(42\) حدّاً من حدود فيبوناتشي فقط، فإن زمن التنفيذ الكلي تهيمن عليه خوارزمية عدّ الأوليات، بينما تبقى كلفة الجزء المغلق صغيرة بالمقارنة.