For this problem, the required total can be rewritten as the odd totient prefix sum
$$G(n)=\sum_{\substack{1\le m\le n\\ m\text{ odd}}}\varphi(m),$$
where \(\varphi\) is Euler's totient function. At the target scale \(n=500000000\), directly evaluating every odd \(\varphi(m)\) is too expensive. The implementation therefore replaces the raw summation by a divisor identity, a closed formula for an auxiliary prefix sum, and a memoized divide-and-conquer recurrence.
We keep the notation
$$G(n)=\sum_{\substack{1\le m\le n\\ m\text{ odd}}}\varphi(m)$$
and define the odd part of a positive integer by
$$\operatorname{odd}(x)=\frac{x}{2^{v_2(x)}}.$$
The auxiliary summatory function used by the implementation is
$$A(n)=\sum_{x=1}^{n}\operatorname{odd}(x).$$
Every odd divisor of \(x\) is exactly a divisor of \(\operatorname{odd}(x)\). The classical identity
$$\sum_{d\mid m}\varphi(d)=m$$
therefore gives
$$\sum_{\substack{d\mid x\\ d\text{ odd}}}\varphi(d)=\sum_{d\mid \operatorname{odd}(x)}\varphi(d)=\operatorname{odd}(x).$$
This is the key arithmetic fact behind the whole algorithm: instead of summing totients directly, we first sum the odd parts of all integers up to \(n\).
Summing the previous identity over \(1\le x\le n\) and exchanging the order of summation yields
$$A(n)=\sum_{x=1}^{n}\sum_{\substack{d\mid x\\ d\text{ odd}}}\varphi(d)=\sum_{\substack{d\le n\\ d\text{ odd}}}\varphi(d)\left\lfloor\frac{n}{d}\right\rfloor.$$
Now use the standard floor-sum rearrangement
$$\sum_{d\le n} a(d)\left\lfloor\frac{n}{d}\right\rfloor=\sum_{t=1}^{n}\sum_{d\le \lfloor n/t\rfloor}a(d).$$
With \(a(d)=\varphi(d)\) for odd \(d\) and \(a(d)=0\) for even \(d\), this becomes
$$A(n)=\sum_{t=1}^{n}G\left(\left\lfloor\frac{n}{t}\right\rfloor\right).$$
The term for \(t=1\) is exactly \(G(n)\), so we isolate it and obtain the recurrence
$$G(n)=A(n)-\sum_{t=2}^{n}G\left(\left\lfloor\frac{n}{t}\right\rfloor\right).$$
Write every positive integer uniquely as \(x=2^j u\) with \(u\) odd. Then \(\operatorname{odd}(x)=u\), so grouping by the exponent \(j\) gives
$$A(n)=\sum_{j\ge 0}\ \sum_{\substack{u\le \lfloor n/2^j\rfloor\\ u\text{ odd}}}u.$$
If \(r=\left\lfloor\frac{u+1}{2}\right\rfloor\), then the odd numbers up to \(u\) are \(1,3,\dots,2r-1\), and
$$1+3+\cdots+(2r-1)=r^2.$$
Therefore the inner sum has the closed form
$$\sum_{\substack{v\le u\\ v\text{ odd}}}v=\left\lfloor\frac{u+1}{2}\right\rfloor^2,$$
and hence
$$A(n)=\sum_{j\ge 0}\left(\left\lfloor\frac{\lfloor n/2^j\rfloor+1}{2}\right\rfloor\right)^2.$$
Only \(O(\log n)\) terms are present, because \(\lfloor n/2^j\rfloor=0\) once \(2^j>n\).
The recurrence still seems to sum over all \(t\), but the quotient \(\left\lfloor n/t\right\rfloor\) repeats on long intervals. If
$$q=\left\lfloor\frac{n}{\ell}\right\rfloor,$$
then the same quotient persists for every
$$t\in[\ell,r],\qquad r=\left\lfloor\frac{n}{q}\right\rfloor.$$
So one whole block contributes
$$\sum_{t=\ell}^{r}G\left(\left\lfloor\frac{n}{t}\right\rfloor\right)=(r-\ell+1)\,G(q).$$
This reduces the cost of one recursive evaluation from linear in \(n\) to the number of distinct quotients, which is \(O(\sqrt n)\).
The same quotient values appear again and again inside different blocks, so the recurrence is evaluated only once for each distinct argument. After a value \(G(q)\) has been computed, later requests reuse the cached result instead of recomputing the entire subtree.
This turns the formula above into a practical divide-and-conquer algorithm for very large \(n\).
First compute \(A(10)\) from the closed form:
$$A(10)=\left\lfloor\frac{10+1}{2}\right\rfloor^2+\left\lfloor\frac{5+1}{2}\right\rfloor^2+\left\lfloor\frac{2+1}{2}\right\rfloor^2+\left\lfloor\frac{1+1}{2}\right\rfloor^2=25+9+1+1=36.$$
Now use quotient blocks for \(t\ge 2\):
$$\left\lfloor\frac{10}{t}\right\rfloor=5,3,2,2,1,1,1,1,1 \qquad (t=2,\dots,10).$$
Hence
$$G(10)=36-\bigl(G(5)+G(3)+2G(2)+5G(1)\bigr).$$
The smaller values are
$$G(1)=1,\qquad G(2)=1,\qquad G(3)=1+\varphi(3)=3,\qquad G(5)=1+\varphi(3)+\varphi(5)=7.$$
Therefore
$$G(10)=36-(7+3+2+5)=19.$$
A direct check agrees:
$$\varphi(1)+\varphi(3)+\varphi(5)+\varphi(7)+\varphi(9)=1+2+4+6+6=19.$$
The C++, Python, and Java implementations all follow the same structure. For a requested \(n\), the implementation first computes \(A(n)\) by repeatedly halving the current bound and adding the square of the number of odd integers up to that bound. It then evaluates the recurrence for \(G(n)\) by scanning quotient blocks \([\ell,r]\), recursively requesting the smaller value \(G(q)\), and subtracting \((r-\ell+1)G(q)\) from the running total.
A cache keyed by the argument stores every completed subproblem, so each distinct value is solved only once. The three language versions differ only in surface syntax and data-structure choice; mathematically they implement the same recurrence, the same block decomposition, and the same exact integer arithmetic.
Computing \(A(n)\) costs \(O(\log n)\) time because the argument is halved at each step. A single recursive evaluation on argument \(m\) processes one interval for each distinct quotient \(\lfloor m/t\rfloor\), so that call uses \(O(\sqrt m)\) block iterations. If \(M\) denotes the set of distinct cached arguments generated from the original input, the total running time is
$$O\left(\sum_{m\in M}\sqrt{m}\right),$$
and the memory usage is \(O(|M|)\). In particular, the top-level quotient list already has only \(O(\sqrt n)\) distinct values, which is why this approach is dramatically faster than summing \(\varphi(m)\) for every odd \(m\le n\).
Für diese Aufgabe lässt sich die gesuchte Größe auf die ungerade Totientensumme
$$G(n)=\sum_{\substack{1\le m\le n\\ m\text{ ungerade}}}\varphi(m)$$
zurückführen. Für den Zielwert \(n=500000000\) wäre es viel zu teuer, \(\varphi(m)\) für alle ungeraden \(m\) direkt auszurechnen. Deshalb verwendet die Implementierung eine Divisorenidentität, eine geschlossene Formel für eine Hilfssumme und eine memoisierten Divide-and-Conquer-Rekursion.
Wir schreiben weiterhin
$$G(n)=\sum_{\substack{1\le m\le n\\ m\text{ ungerade}}}\varphi(m)$$
und definieren den ungeraden Anteil einer positiven ganzen Zahl durch
$$\operatorname{odd}(x)=\frac{x}{2^{v_2(x)}}.$$
Die Hilfsfunktion der Lösung ist
$$A(n)=\sum_{x=1}^{n}\operatorname{odd}(x).$$
Jeder ungerade Teiler von \(x\) ist genau ein Teiler von \(\operatorname{odd}(x)\). Mit der klassischen Identität
$$\sum_{d\mid m}\varphi(d)=m$$
folgt daher
$$\sum_{\substack{d\mid x\\ d\text{ ungerade}}}\varphi(d)=\sum_{d\mid \operatorname{odd}(x)}\varphi(d)=\operatorname{odd}(x).$$
Das ist der zentrale Zahlentheorie-Schritt: Statt die Totienten direkt zu summieren, summieren wir zuerst die ungeraden Anteile aller Zahlen bis \(n\).
Summiert man die vorige Identität über \(1\le x\le n\) und vertauscht die Summationsreihenfolge, erhält man
$$A(n)=\sum_{x=1}^{n}\sum_{\substack{d\mid x\\ d\text{ ungerade}}}\varphi(d)=\sum_{\substack{d\le n\\ d\text{ ungerade}}}\varphi(d)\left\lfloor\frac{n}{d}\right\rfloor.$$
Nun benutzt man die Standardumformung
$$\sum_{d\le n} a(d)\left\lfloor\frac{n}{d}\right\rfloor=\sum_{t=1}^{n}\sum_{d\le \lfloor n/t\rfloor}a(d).$$
Für \(a(d)=\varphi(d)\) bei ungeradem \(d\) und \(a(d)=0\) bei geradem \(d\) wird daraus
$$A(n)=\sum_{t=1}^{n}G\left(\left\lfloor\frac{n}{t}\right\rfloor\right).$$
Der Term zu \(t=1\) ist genau \(G(n)\). Also folgt die Rekursion
$$G(n)=A(n)-\sum_{t=2}^{n}G\left(\left\lfloor\frac{n}{t}\right\rfloor\right).$$
Jede positive ganze Zahl lässt sich eindeutig als \(x=2^j u\) mit ungeradem \(u\) schreiben. Dann gilt \(\operatorname{odd}(x)=u\), also
$$A(n)=\sum_{j\ge 0}\ \sum_{\substack{u\le \lfloor n/2^j\rfloor\\ u\text{ ungerade}}}u.$$
Ist \(r=\left\lfloor\frac{u+1}{2}\right\rfloor\), so sind die ungeraden Zahlen bis \(u\) gerade \(1,3,\dots,2r-1\), und damit
$$1+3+\cdots+(2r-1)=r^2.$$
Also hat die innere Summe die Form
$$\sum_{\substack{v\le u\\ v\text{ ungerade}}}v=\left\lfloor\frac{u+1}{2}\right\rfloor^2,$$
und somit
$$A(n)=\sum_{j\ge 0}\left(\left\lfloor\frac{\lfloor n/2^j\rfloor+1}{2}\right\rfloor\right)^2.$$
Es gibt nur \(O(\log n)\) Summanden, weil \(\lfloor n/2^j\rfloor\) ab einem gewissen Punkt null wird.
Die Rekursion summiert scheinbar über alle \(t\), aber der Quotient \(\left\lfloor n/t\right\rfloor\) bleibt auf langen Intervallen konstant. Setzt man
$$q=\left\lfloor\frac{n}{\ell}\right\rfloor,$$
dann gilt derselbe Quotient für alle
$$t\in[\ell,r],\qquad r=\left\lfloor\frac{n}{q}\right\rfloor.$$
Ein ganzer Block trägt also
$$\sum_{t=\ell}^{r}G\left(\left\lfloor\frac{n}{t}\right\rfloor\right)=(r-\ell+1)\,G(q)$$
bei. Dadurch sinkt der Aufwand eines Rekursionsschritts von linear in \(n\) auf die Anzahl verschiedener Quotienten, also \(O(\sqrt n)\).
Dieselben Quotienten erscheinen in vielen Blöcken wieder. Deshalb wird jeder Wert \(G(q)\) nur einmal berechnet und anschließend aus einem Cache wiederverwendet. Erst diese Kombination aus Quotientenblöcken und Memoisierung macht die Methode für sehr große \(n\) praktikabel.
Zuerst berechnen wir \(A(10)\):
$$A(10)=\left\lfloor\frac{10+1}{2}\right\rfloor^2+\left\lfloor\frac{5+1}{2}\right\rfloor^2+\left\lfloor\frac{2+1}{2}\right\rfloor^2+\left\lfloor\frac{1+1}{2}\right\rfloor^2=25+9+1+1=36.$$
Für \(t\ge 2\) sind die Quotienten
$$\left\lfloor\frac{10}{t}\right\rfloor=5,3,2,2,1,1,1,1,1 \qquad (t=2,\dots,10).$$
Daher
$$G(10)=36-\bigl(G(5)+G(3)+2G(2)+5G(1)\bigr).$$
Die kleineren Werte lauten
$$G(1)=1,\qquad G(2)=1,\qquad G(3)=1+\varphi(3)=3,\qquad G(5)=1+\varphi(3)+\varphi(5)=7.$$
Somit
$$G(10)=36-(7+3+2+5)=19.$$
Die direkte Kontrolle bestätigt das:
$$\varphi(1)+\varphi(3)+\varphi(5)+\varphi(7)+\varphi(9)=1+2+4+6+6=19.$$
Die C++-, Python- und Java-Implementierungen folgen derselben Struktur. Für ein gegebenes \(n\) berechnet die Implementierung zuerst \(A(n)\), indem sie die Schranke wiederholt halbiert und jeweils das Quadrat der Anzahl ungerader Zahlen bis zu dieser Schranke addiert. Danach wertet sie die Rekursion für \(G(n)\) über Quotientenblöcke \([\ell,r]\) aus, fordert rekursiv den kleineren Wert \(G(q)\) an und subtrahiert \((r-\ell+1)G(q)\) vom laufenden Ergebnis.
Ein Cache speichert jedes bereits gelöste Teilproblem nach seinem Argument, sodass jeder verschiedene Wert nur einmal berechnet wird. Die drei Sprachversionen unterscheiden sich nur syntaktisch; mathematisch verwenden sie dieselbe Rekursion, dieselbe Blockzerlegung und dieselbe exakte Ganzzahlarithmetik.
Die Berechnung von \(A(n)\) kostet \(O(\log n)\) Zeit, weil der Parameter in jedem Schritt halbiert wird. Ein einzelner Rekursionsaufruf auf Argument \(m\) verarbeitet genau einen Block pro verschiedenem Quotienten \(\lfloor m/t\rfloor\), also \(O(\sqrt m)\) Blockschritte. Bezeichnet \(M\) die Menge aller verschiedenen zwischengespeicherten Argumente, so ist die Gesamtlaufzeit
$$O\left(\sum_{m\in M}\sqrt{m}\right),$$
während der Speicherbedarf \(O(|M|)\) beträgt. Schon auf oberster Ebene gibt es nur \(O(\sqrt n)\) verschiedene Quotienten, weshalb dieses Verfahren viel schneller ist als eine direkte Totientensummierung über alle ungeraden \(m\le n\).
Bu problemde istenen toplam, tek sayılar üzerindeki totient önek toplamına indirgenebilir:
$$G(n)=\sum_{\substack{1\le m\le n\\ m\text{ tek}}}\varphi(m).$$
Hedef giriş \(n=500000000\) olduğunda her tek \(m\) için \(\varphi(m)\) değerini doğrudan hesaplamak çok pahalıdır. Bu yüzden çözüm, bir bölen özdeşliği, yardımcı bir önek toplam için kapalı form ve önbellekli böl-ve-yönet türü bir bağıntı kullanır.
Gösterimi
$$G(n)=\sum_{\substack{1\le m\le n\\ m\text{ tek}}}\varphi(m)$$
olarak koruyalım ve bir sayının tek kısmını
$$\operatorname{odd}(x)=\frac{x}{2^{v_2(x)}}$$
şeklinde tanımlayalım. Çözümde kullanılan yardımcı toplam ise
$$A(n)=\sum_{x=1}^{n}\operatorname{odd}(x).$$
\(x\)'in her tek böleni, tam olarak \(\operatorname{odd}(x)\)'in bir bölenidir. Klasik özdeşlik
$$\sum_{d\mid m}\varphi(d)=m$$
bu nedenle
$$\sum_{\substack{d\mid x\\ d\text{ tek}}}\varphi(d)=\sum_{d\mid \operatorname{odd}(x)}\varphi(d)=\operatorname{odd}(x)$$
sonucunu verir. Algoritmanın asıl fikri budur: totientleri doğrudan toplamak yerine önce \(1\) ile \(n\) arasındaki sayıların tek kısımlarını toplarız.
Önceki özdeşliği \(1\le x\le n\) için toplayıp toplam sırasını değiştirirsek
$$A(n)=\sum_{x=1}^{n}\sum_{\substack{d\mid x\\ d\text{ tek}}}\varphi(d)=\sum_{\substack{d\le n\\ d\text{ tek}}}\varphi(d)\left\lfloor\frac{n}{d}\right\rfloor$$
elde edilir. Şimdi standart taban-toplam dönüşümünü kullanalım:
$$\sum_{d\le n} a(d)\left\lfloor\frac{n}{d}\right\rfloor=\sum_{t=1}^{n}\sum_{d\le \lfloor n/t\rfloor}a(d).$$
\(a(d)\) tek \(d\) için \(\varphi(d)\), çift \(d\) için \(0\) seçilirse
$$A(n)=\sum_{t=1}^{n}G\left(\left\lfloor\frac{n}{t}\right\rfloor\right)$$
olur. \(t=1\) terimi doğrudan \(G(n)\) verdiğinden
$$G(n)=A(n)-\sum_{t=2}^{n}G\left(\left\lfloor\frac{n}{t}\right\rfloor\right)$$
bağıntısını elde ederiz.
Her pozitif tam sayı tekil olarak \(x=2^j u\) biçiminde, \(u\) tek olacak şekilde yazılabilir. O zaman \(\operatorname{odd}(x)=u\) olur ve
$$A(n)=\sum_{j\ge 0}\ \sum_{\substack{u\le \lfloor n/2^j\rfloor\\ u\text{ tek}}}u$$
elde edilir. Eğer \(r=\left\lfloor\frac{u+1}{2}\right\rfloor\) ise \(u\)'ya kadar olan tek sayılar \(1,3,\dots,2r-1\) olur ve
$$1+3+\cdots+(2r-1)=r^2.$$
Dolayısıyla iç toplam
$$\sum_{\substack{v\le u\\ v\text{ tek}}}v=\left\lfloor\frac{u+1}{2}\right\rfloor^2$$
şeklindedir ve sonuçta
$$A(n)=\sum_{j\ge 0}\left(\left\lfloor\frac{\lfloor n/2^j\rfloor+1}{2}\right\rfloor\right)^2$$
olur. Çünkü \(\lfloor n/2^j\rfloor\) belli bir noktadan sonra sıfır olur, bu toplam sadece \(O(\log n)\) terim içerir.
Bağıntı sanki bütün \(t\) değerleri üzerinde dolaşıyor gibi görünür, ancak \(\left\lfloor n/t\right\rfloor\) uzun aralıklarda sabittir. Eğer
$$q=\left\lfloor\frac{n}{\ell}\right\rfloor$$
ise aynı bölüm değeri
$$t\in[\ell,r],\qquad r=\left\lfloor\frac{n}{q}\right\rfloor$$
aralığındaki tüm \(t\)'ler için geçerlidir. Böylece bir blok
$$\sum_{t=\ell}^{r}G\left(\left\lfloor\frac{n}{t}\right\rfloor\right)=(r-\ell+1)\,G(q)$$
katkısı yapar. Bu fikir tek bir özyinelemeli çağrının maliyetini lineer olmaktan çıkarıp farklı bölüm sayısı mertebesine, yani \(O(\sqrt n)\)'ye indirir.
Aynı bölüm değerleri farklı bloklarda tekrar tekrar ortaya çıkar. Bu yüzden \(G(q)\) bir kez hesaplandıktan sonra saklanır ve sonraki ihtiyaçlarda doğrudan kullanılır. Bloklama ile önbelleklemenin birleşimi, yöntemi çok büyük \(n\) değerlerinde uygulanabilir hale getirir.
Önce kapalı form ile \(A(10)\) hesaplanır:
$$A(10)=\left\lfloor\frac{10+1}{2}\right\rfloor^2+\left\lfloor\frac{5+1}{2}\right\rfloor^2+\left\lfloor\frac{2+1}{2}\right\rfloor^2+\left\lfloor\frac{1+1}{2}\right\rfloor^2=25+9+1+1=36.$$
\(t\ge 2\) için bölüm değerleri
$$\left\lfloor\frac{10}{t}\right\rfloor=5,3,2,2,1,1,1,1,1 \qquad (t=2,\dots,10)$$
olduğundan
$$G(10)=36-\bigl(G(5)+G(3)+2G(2)+5G(1)\bigr)$$
yazılır. Küçük değerler
$$G(1)=1,\qquad G(2)=1,\qquad G(3)=1+\varphi(3)=3,\qquad G(5)=1+\varphi(3)+\varphi(5)=7$$
olduğu için
$$G(10)=36-(7+3+2+5)=19$$
elde edilir. Doğrudan kontrol de aynısını verir:
$$\varphi(1)+\varphi(3)+\varphi(5)+\varphi(7)+\varphi(9)=1+2+4+6+6=19.$$
C++, Python ve Java uygulamalarının üçü de aynı matematiksel planı izler. Bir \(n\) değeri için uygulama önce sınırı tekrar tekrar ikiye bölerek ve her aşamada o sınıra kadar olan tek sayı sayısının karesini ekleyerek \(A(n)\)'i hesaplar. Ardından \(G(n)\) bağıntısını, \([\ell,r]\) bölüm blokları üzerinden dolaşarak değerlendirir; daha küçük \(G(q)\) değerini özyinelemeli olarak ister ve \((r-\ell+1)G(q)\) katkısını toplamdan çıkarır.
Her tamamlanmış alt problem, argümanına göre bir önbellekte tutulur; böylece her farklı değer sadece bir kez çözülür. Diller arasındaki farklar yalnızca sözdizimi ve veri yapısı düzeyindedir; matematiksel olarak aynı bağıntı, aynı blok ayrıştırması ve aynı tam sayı hesabı uygulanır.
\(A(n)\)'in hesabı, argüman her adımda yarıya indiği için \(O(\log n)\) zaman alır. Argümanı \(m\) olan tek bir özyinelemeli çağrı, \(\lfloor m/t\rfloor\) ifadesinin her farklı değeri için bir blok işler; bu da \(O(\sqrt m)\) blok demektir. Başlangıç girişinden türeyen farklı önbellekli argümanların kümesi \(M\) ise toplam süre
$$O\left(\sum_{m\in M}\sqrt{m}\right)$$
olur; bellek kullanımı ise \(O(|M|)\)'dir. Özellikle en üst çağrıda bile yalnızca \(O(\sqrt n)\) farklı bölüm değeri bulunduğu için bu yöntem, tüm tek \(m\le n\) için \(\varphi(m)\) toplamaktan çok daha hızlıdır.
En este problema, la cantidad pedida puede reescribirse como la suma prefija de totientes impares
$$G(n)=\sum_{\substack{1\le m\le n\\ m\text{ impar}}}\varphi(m).$$
Para el valor objetivo \(n=500000000\), calcular \(\varphi(m)\) para todos los \(m\) impares de forma directa es demasiado costoso. Por eso la implementación sustituye la suma ingenua por una identidad sobre divisores, una fórmula cerrada para una suma auxiliar y una recurrencia divide y vencerás con memoización.
Mantenemos la notación
$$G(n)=\sum_{\substack{1\le m\le n\\ m\text{ impar}}}\varphi(m)$$
y definimos la parte impar de un entero positivo por
$$\operatorname{odd}(x)=\frac{x}{2^{v_2(x)}}.$$
La función auxiliar utilizada por la solución es
$$A(n)=\sum_{x=1}^{n}\operatorname{odd}(x).$$
Todo divisor impar de \(x\) es exactamente un divisor de \(\operatorname{odd}(x)\). Entonces, usando la identidad clásica
$$\sum_{d\mid m}\varphi(d)=m,$$
obtenemos
$$\sum_{\substack{d\mid x\\ d\text{ impar}}}\varphi(d)=\sum_{d\mid \operatorname{odd}(x)}\varphi(d)=\operatorname{odd}(x).$$
Éste es el hecho aritmético central: en lugar de sumar totientes directamente, primero sumamos la parte impar de todos los enteros entre \(1\) y \(n\).
Si sumamos la identidad anterior para \(1\le x\le n\) e intercambiamos el orden de sumación, resulta
$$A(n)=\sum_{x=1}^{n}\sum_{\substack{d\mid x\\ d\text{ impar}}}\varphi(d)=\sum_{\substack{d\le n\\ d\text{ impar}}}\varphi(d)\left\lfloor\frac{n}{d}\right\rfloor.$$
Ahora aplicamos la reorganización estándar
$$\sum_{d\le n} a(d)\left\lfloor\frac{n}{d}\right\rfloor=\sum_{t=1}^{n}\sum_{d\le \lfloor n/t\rfloor}a(d).$$
Tomando \(a(d)=\varphi(d)\) si \(d\) es impar y \(a(d)=0\) si \(d\) es par, obtenemos
$$A(n)=\sum_{t=1}^{n}G\left(\left\lfloor\frac{n}{t}\right\rfloor\right).$$
El término con \(t=1\) es exactamente \(G(n)\), así que queda la recurrencia
$$G(n)=A(n)-\sum_{t=2}^{n}G\left(\left\lfloor\frac{n}{t}\right\rfloor\right).$$
Todo entero positivo se escribe de manera única como \(x=2^j u\) con \(u\) impar. Entonces \(\operatorname{odd}(x)=u\), y al agrupar por \(j\) se obtiene
$$A(n)=\sum_{j\ge 0}\ \sum_{\substack{u\le \lfloor n/2^j\rfloor\\ u\text{ impar}}}u.$$
Si \(r=\left\lfloor\frac{u+1}{2}\right\rfloor\), los impares hasta \(u\) son \(1,3,\dots,2r-1\), de modo que
$$1+3+\cdots+(2r-1)=r^2.$$
Por tanto, la suma interior vale
$$\sum_{\substack{v\le u\\ v\text{ impar}}}v=\left\lfloor\frac{u+1}{2}\right\rfloor^2,$$
y en consecuencia
$$A(n)=\sum_{j\ge 0}\left(\left\lfloor\frac{\lfloor n/2^j\rfloor+1}{2}\right\rfloor\right)^2.$$
Sólo aparecen \(O(\log n)\) términos porque \(\lfloor n/2^j\rfloor\) acaba siendo cero.
La recurrencia parece recorrer todos los valores de \(t\), pero el cociente \(\left\lfloor n/t\right\rfloor\) se repite en intervalos largos. Si
$$q=\left\lfloor\frac{n}{\ell}\right\rfloor,$$
ese mismo valor permanece para todos los
$$t\in[\ell,r],\qquad r=\left\lfloor\frac{n}{q}\right\rfloor.$$
Así, un bloque completo aporta
$$\sum_{t=\ell}^{r}G\left(\left\lfloor\frac{n}{t}\right\rfloor\right)=(r-\ell+1)\,G(q).$$
Esto reduce el coste de una evaluación recursiva desde lineal en \(n\) hasta el número de cocientes distintos, que es \(O(\sqrt n)\).
Los mismos cocientes reaparecen una y otra vez dentro de distintos bloques. Por eso cada valor \(G(q)\) se calcula una sola vez y luego se recupera desde una caché. La combinación de bloques por cociente y memoización convierte la fórmula en un algoritmo práctico para entradas muy grandes.
Primero se calcula \(A(10)\) con la fórmula cerrada:
$$A(10)=\left\lfloor\frac{10+1}{2}\right\rfloor^2+\left\lfloor\frac{5+1}{2}\right\rfloor^2+\left\lfloor\frac{2+1}{2}\right\rfloor^2+\left\lfloor\frac{1+1}{2}\right\rfloor^2=25+9+1+1=36.$$
Para \(t\ge 2\), los cocientes son
$$\left\lfloor\frac{10}{t}\right\rfloor=5,3,2,2,1,1,1,1,1 \qquad (t=2,\dots,10).$$
Por tanto
$$G(10)=36-\bigl(G(5)+G(3)+2G(2)+5G(1)\bigr).$$
Los valores pequeños son
$$G(1)=1,\qquad G(2)=1,\qquad G(3)=1+\varphi(3)=3,\qquad G(5)=1+\varphi(3)+\varphi(5)=7.$$
Entonces
$$G(10)=36-(7+3+2+5)=19.$$
La comprobación directa coincide:
$$\varphi(1)+\varphi(3)+\varphi(5)+\varphi(7)+\varphi(9)=1+2+4+6+6=19.$$
Las implementaciones en C++, Python y Java siguen exactamente la misma idea. Dado un \(n\), la implementación calcula primero \(A(n)\) reduciendo repetidamente el límite a la mitad y sumando el cuadrado del número de enteros impares hasta ese límite. Después evalúa la recurrencia para \(G(n)\) recorriendo bloques \([\ell,r]\) con el mismo cociente, pide recursivamente el valor menor \(G(q)\) y resta \((r-\ell+1)G(q)\) del total acumulado.
Una caché indexada por el argumento guarda cada subproblema ya resuelto, de modo que cada valor distinto se calcula una sola vez. Las tres versiones cambian sólo en la sintaxis y en la estructura concreta de almacenamiento; matemáticamente implementan la misma recurrencia, la misma descomposición por bloques y la misma aritmética exacta con enteros.
Calcular \(A(n)\) cuesta \(O(\log n)\) tiempo porque el argumento se divide entre \(2\) en cada paso. Una sola evaluación recursiva sobre un argumento \(m\) procesa un bloque por cada cociente distinto \(\lfloor m/t\rfloor\), así que requiere \(O(\sqrt m)\) iteraciones de bloques. Si \(M\) es el conjunto de argumentos distintos almacenados en caché a partir de la entrada original, el tiempo total es
$$O\left(\sum_{m\in M}\sqrt{m}\right),$$
mientras que la memoria usada es \(O(|M|)\). En particular, incluso en el nivel superior sólo hay \(O(\sqrt n)\) cocientes distintos, por lo que este método es muchísimo más rápido que sumar \(\varphi(m)\) para cada impar \(m\le n\).
这道题要求的总量可以改写成奇数位置上的欧拉函数前缀和：
$$G(n)=\sum_{\substack{1\le m\le n\\ m\text{ 为奇数}}}\varphi(m).$$
当目标输入达到 \(n=500000000\) 时，若直接对所有奇数 \(m\) 逐个计算 \(\varphi(m)\) 再求和，代价会非常高。实现采用的是另一条路线：先用一个关于奇数因子的恒等式把问题改写，再把辅助前缀和写成闭式，最后配合记忆化和按商分块的递归完成计算。
记
$$G(n)=\sum_{\substack{1\le m\le n\\ m\text{ 为奇数}}}\varphi(m),$$
并把正整数 \(x\) 的奇数部分定义为
$$\operatorname{odd}(x)=\frac{x}{2^{v_2(x)}}.$$
实现中还会用到辅助函数
$$A(n)=\sum_{x=1}^{n}\operatorname{odd}(x).$$
\(x\) 的每一个奇因子，恰好也是 \(\operatorname{odd}(x)\) 的一个因子。再利用经典恒等式
$$\sum_{d\mid m}\varphi(d)=m,$$
立刻得到
$$\sum_{\substack{d\mid x\\ d\text{ 为奇数}}}\varphi(d)=\sum_{d\mid \operatorname{odd}(x)}\varphi(d)=\operatorname{odd}(x).$$
这一步是整个算法的核心。它说明与其直接求奇数上的 \(\varphi\) 之和，不如先把所有整数的奇数部分加起来，再反推出目标函数。
把上面的恒等式对 \(1\le x\le n\) 求和，并交换求和顺序，可得
$$A(n)=\sum_{x=1}^{n}\sum_{\substack{d\mid x\\ d\text{ 为奇数}}}\varphi(d)=\sum_{\substack{d\le n\\ d\text{ 为奇数}}}\varphi(d)\left\lfloor\frac{n}{d}\right\rfloor.$$
接着使用标准的整除分块重排公式
$$\sum_{d\le n} a(d)\left\lfloor\frac{n}{d}\right\rfloor=\sum_{t=1}^{n}\sum_{d\le \lfloor n/t\rfloor}a(d).$$
如果令 \(a(d)=\varphi(d)\) 当且仅当 \(d\) 为奇数，否则 \(a(d)=0\)，就得到
$$A(n)=\sum_{t=1}^{n}G\left(\left\lfloor\frac{n}{t}\right\rfloor\right).$$
其中 \(t=1\) 这一项正好就是 \(G(n)\)，因此可以把它移到左边，得到递推式
$$G(n)=A(n)-\sum_{t=2}^{n}G\left(\left\lfloor\frac{n}{t}\right\rfloor\right).$$
每个正整数都能唯一写成 \(x=2^j u\)，其中 \(u\) 为奇数。于是 \(\operatorname{odd}(x)=u\)，按 \(j\) 分类可得
$$A(n)=\sum_{j\ge 0}\ \sum_{\substack{u\le \lfloor n/2^j\rfloor\\ u\text{ 为奇数}}}u.$$
若 \(r=\left\lfloor\frac{u+1}{2}\right\rfloor\)，那么不超过 \(u\) 的奇数正好是 \(1,3,\dots,2r-1\)，而它们的和满足
$$1+3+\cdots+(2r-1)=r^2.$$
所以内层求和可以直接写成
$$\sum_{\substack{v\le u\\ v\text{ 为奇数}}}v=\left\lfloor\frac{u+1}{2}\right\rfloor^2,$$
从而
$$A(n)=\sum_{j\ge 0}\left(\left\lfloor\frac{\lfloor n/2^j\rfloor+1}{2}\right\rfloor\right)^2.$$
因为当 \(2^j>n\) 时 \(\lfloor n/2^j\rfloor=0\)，所以这一部分只需要 \(O(\log n)\) 项。
虽然递推式看起来要遍历所有 \(t\)，但 \(\left\lfloor n/t\right\rfloor\) 会在一整段区间内保持不变。若
$$q=\left\lfloor\frac{n}{\ell}\right\rfloor,$$
则对于区间
$$t\in[\ell,r],\qquad r=\left\lfloor\frac{n}{q}\right\rfloor,$$
中的每个 \(t\)，都有 \(\left\lfloor n/t\right\rfloor=q\)。因此这个整段区间的贡献可以合并成
$$\sum_{t=\ell}^{r}G\left(\left\lfloor\frac{n}{t}\right\rfloor\right)=(r-\ell+1)\,G(q).$$
这样一来，一次递归求值不再是线性枚举，而只需要处理不同商值对应的那些块，其数量为 \(O(\sqrt n)\)。
不同区间中会反复出现相同的商值 \(q\)。因此每个 \(G(q)\) 只在第一次需要时计算一次，之后就从缓存中直接读取。按商分块减少了每次调用的工作量，而记忆化又消除了重复子问题，这两者结合起来才使得大规模输入成为可计算的问题。
先用闭式计算 \(A(10)\)：
$$A(10)=\left\lfloor\frac{10+1}{2}\right\rfloor^2+\left\lfloor\frac{5+1}{2}\right\rfloor^2+\left\lfloor\frac{2+1}{2}\right\rfloor^2+\left\lfloor\frac{1+1}{2}\right\rfloor^2=25+9+1+1=36.$$
再看 \(t\ge 2\) 时的商值：
$$\left\lfloor\frac{10}{t}\right\rfloor=5,3,2,2,1,1,1,1,1 \qquad (t=2,\dots,10).$$
于是
$$G(10)=36-\bigl(G(5)+G(3)+2G(2)+5G(1)\bigr).$$
小规模值分别是
$$G(1)=1,\qquad G(2)=1,\qquad G(3)=1+\varphi(3)=3,\qquad G(5)=1+\varphi(3)+\varphi(5)=7.$$
代回后得到
$$G(10)=36-(7+3+2+5)=19.$$
直接求和也完全一致：
$$\varphi(1)+\varphi(3)+\varphi(5)+\varphi(7)+\varphi(9)=1+2+4+6+6=19.$$
C++、Python 和 Java 实现采用的是同一个算法框架。对于输入 \(n\)，实现先通过不断把当前上界除以 \(2\)，并累加“该上界以内奇数个数的平方”，快速算出 \(A(n)\)。随后它按照商值分块的方式遍历区间 \([\ell,r]\)，递归请求较小参数上的 \(G(q)\)，再从当前结果中减去 \((r-\ell+1)G(q)\)。
每个已经求出的子问题都会按参数值存入缓存，因此同一个参数只会真正计算一次。三种语言的实现只是在语法和容器形式上不同；从数学上看，它们执行的是同一条递推、同一种分块方式以及同样的精确整数运算。
计算 \(A(n)\) 的时间是 \(O(\log n)\)，因为上界每次都会减半。对于参数为 \(m\) 的单次递归调用，需要处理的块数等于不同的 \(\lfloor m/t\rfloor\) 值的个数，所以是 \(O(\sqrt m)\)。若把从原始输入出发最终进入缓存的不同参数集合记为 \(M\)，则总时间可以写成
$$O\left(\sum_{m\in M}\sqrt{m}\right),$$
空间复杂度为 \(O(|M|)\)。特别地，顶层调用本身就只有 \(O(\sqrt n)\) 个不同商值，因此该方法远快于对所有奇数 \(m\le n\) 逐个求 \(\varphi(m)\) 再累加。
В этой задаче искомую величину удобно переписать как сумму значений функции Эйлера по нечётным аргументам:
$$G(n)=\sum_{\substack{1\le m\le n\\ m\text{ нечётное}}}\varphi(m).$$
При целевом значении \(n=500000000\) прямой перебор всех нечётных \(m\) и вычисление \(\varphi(m)\) слишком дорог. Поэтому реализация использует тождество по делителям, замкнутую формулу для вспомогательной префиксной суммы и рекурсию divide-and-conquer с мемоизацией.
Будем использовать обозначение
$$G(n)=\sum_{\substack{1\le m\le n\\ m\text{ нечётное}}}\varphi(m)$$
и введём нечётную часть числа:
$$\operatorname{odd}(x)=\frac{x}{2^{v_2(x)}}.$$
Вспомогательная сумматорная функция имеет вид
$$A(n)=\sum_{x=1}^{n}\operatorname{odd}(x).$$
Каждый нечётный делитель числа \(x\) является в точности делителем \(\operatorname{odd}(x)\). Тогда классическое тождество
$$\sum_{d\mid m}\varphi(d)=m$$
немедленно даёт
$$\sum_{\substack{d\mid x\\ d\text{ нечётный}}}\varphi(d)=\sum_{d\mid \operatorname{odd}(x)}\varphi(d)=\operatorname{odd}(x).$$
Это ключевой арифметический факт решения: вместо прямой суммы по \(\varphi\) мы сначала суммируем нечётные части всех чисел до \(n\).
Просуммируем предыдущее тождество по всем \(1\le x\le n\) и поменяем порядок суммирования:
$$A(n)=\sum_{x=1}^{n}\sum_{\substack{d\mid x\\ d\text{ нечётный}}}\varphi(d)=\sum_{\substack{d\le n\\ d\text{ нечётный}}}\varphi(d)\left\lfloor\frac{n}{d}\right\rfloor.$$
Теперь используем стандартную перестановку сумм
$$\sum_{d\le n} a(d)\left\lfloor\frac{n}{d}\right\rfloor=\sum_{t=1}^{n}\sum_{d\le \lfloor n/t\rfloor}a(d).$$
Если положить \(a(d)=\varphi(d)\) для нечётных \(d\) и \(a(d)=0\) для чётных, получаем
$$A(n)=\sum_{t=1}^{n}G\left(\left\lfloor\frac{n}{t}\right\rfloor\right).$$
Слагаемое при \(t=1\) равно \(G(n)\), поэтому
$$G(n)=A(n)-\sum_{t=2}^{n}G\left(\left\lfloor\frac{n}{t}\right\rfloor\right).$$
Любое положительное число единственным образом записывается в виде \(x=2^j u\), где \(u\) нечётно. Тогда \(\operatorname{odd}(x)=u\), и после группировки по \(j\) имеем
$$A(n)=\sum_{j\ge 0}\ \sum_{\substack{u\le \lfloor n/2^j\rfloor\\ u\text{ нечётно}}}u.$$
Если \(r=\left\lfloor\frac{u+1}{2}\right\rfloor\), то нечётные числа до \(u\) равны \(1,3,\dots,2r-1\), а их сумма равна
$$1+3+\cdots+(2r-1)=r^2.$$
Следовательно, внутренняя сумма записывается как
$$\sum_{\substack{v\le u\\ v\text{ нечётно}}}v=\left\lfloor\frac{u+1}{2}\right\rfloor^2,$$
и значит
$$A(n)=\sum_{j\ge 0}\left(\left\lfloor\frac{\lfloor n/2^j\rfloor+1}{2}\right\rfloor\right)^2.$$
Терминов здесь только \(O(\log n)\), потому что \(\lfloor n/2^j\rfloor\) быстро становится нулём.
Хотя рекурсия выглядит как сумма по всем \(t\), значение \(\left\lfloor n/t\right\rfloor\) повторяется на длинных интервалах. Если
$$q=\left\lfloor\frac{n}{\ell}\right\rfloor,$$
то тот же самый частный сохраняется для всех
$$t\in[\ell,r],\qquad r=\left\lfloor\frac{n}{q}\right\rfloor.$$
Тогда вклад целого блока равен
$$\sum_{t=\ell}^{r}G\left(\left\lfloor\frac{n}{t}\right\rfloor\right)=(r-\ell+1)\,G(q).$$
Тем самым стоимость одного рекурсивного вычисления уменьшается с линейной по \(n\) до количества различных частных, то есть до \(O(\sqrt n)\).
Одни и те же значения \(q\) появляются во многих блоках. Поэтому каждое значение \(G(q)\) вычисляется только один раз, а затем берётся из кэша. Именно сочетание блочной обработки частных и мемоизации делает метод достаточно быстрым для больших входных данных.
Сначала найдём \(A(10)\) по замкнутой формуле:
$$A(10)=\left\lfloor\frac{10+1}{2}\right\rfloor^2+\left\lfloor\frac{5+1}{2}\right\rfloor^2+\left\lfloor\frac{2+1}{2}\right\rfloor^2+\left\lfloor\frac{1+1}{2}\right\rfloor^2=25+9+1+1=36.$$
Для \(t\ge 2\) частные равны
$$\left\lfloor\frac{10}{t}\right\rfloor=5,3,2,2,1,1,1,1,1 \qquad (t=2,\dots,10).$$
Следовательно,
$$G(10)=36-\bigl(G(5)+G(3)+2G(2)+5G(1)\bigr).$$
Малые значения таковы:
$$G(1)=1,\qquad G(2)=1,\qquad G(3)=1+\varphi(3)=3,\qquad G(5)=1+\varphi(3)+\varphi(5)=7.$$
Итак,
$$G(10)=36-(7+3+2+5)=19.$$
Прямая проверка даёт тот же ответ:
$$\varphi(1)+\varphi(3)+\varphi(5)+\varphi(7)+\varphi(9)=1+2+4+6+6=19.$$
Реализации на C++, Python и Java устроены одинаково. Для заданного \(n\) реализация сначала вычисляет \(A(n)\): многократно делит текущую границу пополам и добавляет квадрат количества нечётных чисел до этой границы. Затем она вычисляет \(G(n)\) по рекуррентной формуле, проходя по блокам \([\ell,r]\) с одинаковым частным, рекурсивно запрашивая меньшее значение \(G(q)\) и вычитая \((r-\ell+1)G(q)\) из текущего результата.
Каждая уже решённая подзадача сохраняется в кэше по своему аргументу, поэтому одно и то же значение действительно вычисляется только один раз. Различия между тремя версиями касаются лишь синтаксиса и выбора контейнера; математически во всех случаях используется одна и та же рекурсия, одно и то же разбиение по блокам и одна и та же точная целочисленная арифметика.
Вычисление \(A(n)\) требует \(O(\log n)\) времени, поскольку аргумент на каждом шаге делится пополам. Один рекурсивный вызов с аргументом \(m\) обрабатывает по одному блоку на каждое различное значение \(\lfloor m/t\rfloor\), то есть использует \(O(\sqrt m)\) блочных шагов. Если \(M\) обозначает множество различных аргументов, оказавшихся в кэше, то общее время равно
$$O\left(\sum_{m\in M}\sqrt{m}\right),$$
а память равна \(O(|M|)\). Уже на верхнем уровне имеется только \(O(\sqrt n)\) различных частных, поэтому метод значительно быстрее прямого суммирования \(\varphi(m)\) по всем нечётным \(m\le n\).
في هذه المسألة يمكن إعادة كتابة الكمية المطلوبة على شكل مجموع تراكمي لدالة أويلر فوق الأعداد الفردية:
$$G(n)=\sum_{\substack{1\le m\le n\\ m\text{ odd}}}\varphi(m).$$
عند القيمة الهدف \(n=500000000\)، يكون حساب \(\varphi(m)\) لكل عدد فردي مباشرةً مكلفًا جدًا. لذلك تعتمد الحلول على هوية تتعلق بالقواسم الفردية، ثم على صيغة مغلقة لمجموع مساعد، ثم على علاقة عودية من نوع divide-and-conquer مع التذكّر.
سنستعمل الترميز
$$G(n)=\sum_{\substack{1\le m\le n\\ m\text{ odd}}}\varphi(m)$$
ونعرّف الجزء الفردي للعدد الصحيح الموجب بالصيغة
$$\operatorname{odd}(x)=\frac{x}{2^{v_2(x)}}.$$
كما نعرّف الدالة المساعدة
$$A(n)=\sum_{x=1}^{n}\operatorname{odd}(x).$$
كل قاسم فردي للعدد \(x\) هو بالضبط قاسم للعدد \(\operatorname{odd}(x)\). ومع الهوية الكلاسيكية
$$\sum_{d\mid m}\varphi(d)=m$$
نحصل مباشرة على
$$\sum_{\substack{d\mid x\\ d\text{ odd}}}\varphi(d)=\sum_{d\mid \operatorname{odd}(x)}\varphi(d)=\operatorname{odd}(x).$$
هذه هي الفكرة الحسابية الأساسية في الحل: بدل جمع قيم \(\varphi\) مباشرة، نجمع أولًا الأجزاء الفردية لكل الأعداد من \(1\) إلى \(n\).
بجمع الهوية السابقة على جميع \(x\) من \(1\) إلى \(n\)، ثم تبديل ترتيب الجمع، نحصل على
$$A(n)=\sum_{x=1}^{n}\sum_{\substack{d\mid x\\ d\text{ odd}}}\varphi(d)=\sum_{\substack{d\le n\\ d\text{ odd}}}\varphi(d)\left\lfloor\frac{n}{d}\right\rfloor.$$
ثم نستخدم إعادة الترتيب القياسية
$$\sum_{d\le n} a(d)\left\lfloor\frac{n}{d}\right\rfloor=\sum_{t=1}^{n}\sum_{d\le \lfloor n/t\rfloor}a(d).$$
وباختيار \(a(d)=\varphi(d)\) عندما يكون \(d\) فرديًا و\(a(d)=0\) عندما يكون زوجيًا، تصبح الصيغة
$$A(n)=\sum_{t=1}^{n}G\left(\left\lfloor\frac{n}{t}\right\rfloor\right).$$
والحد الموافق لـ \(t=1\) يساوي \(G(n)\) تمامًا، ولذلك نحصل على العلاقة
$$G(n)=A(n)-\sum_{t=2}^{n}G\left(\left\lfloor\frac{n}{t}\right\rfloor\right).$$
كل عدد صحيح موجب يمكن كتابته بشكل وحيد على الصورة \(x=2^j u\) حيث \(u\) فردي. عندئذٍ يكون \(\operatorname{odd}(x)=u\)، وبالتالي
$$A(n)=\sum_{j\ge 0}\ \sum_{\substack{u\le \lfloor n/2^j\rfloor\\ u\text{ odd}}}u.$$
إذا وضعنا \(r=\left\lfloor\frac{u+1}{2}\right\rfloor\)، فإن الأعداد الفردية حتى \(u\) هي \(1,3,\dots,2r-1\)، ومجموعها يساوي
$$1+3+\cdots+(2r-1)=r^2.$$
إذن يمكن كتابة المجموع الداخلي على الصورة
$$\sum_{\substack{v\le u\\ v\text{ odd}}}v=\left\lfloor\frac{u+1}{2}\right\rfloor^2,$$
ومن ثم
$$A(n)=\sum_{j\ge 0}\left(\left\lfloor\frac{\lfloor n/2^j\rfloor+1}{2}\right\rfloor\right)^2.$$
ولا يظهر هنا سوى \(O(\log n)\) حدود، لأن \(\lfloor n/2^j\rfloor\) يصبح صفرًا بعد عدد قليل من القسمة على \(2\).
تبدو العلاقة العودية وكأنها تمر على كل \(t\)، لكن القيمة \(\left\lfloor n/t\right\rfloor\) تتكرر على فترات طويلة. إذا كان
$$q=\left\lfloor\frac{n}{\ell}\right\rfloor,$$
فإن هذا الحاصل يبقى ثابتًا لكل
$$t\in[\ell,r],\qquad r=\left\lfloor\frac{n}{q}\right\rfloor.$$
وعندئذٍ تكون مساهمة الكتلة كاملة هي
$$\sum_{t=\ell}^{r}G\left(\left\lfloor\frac{n}{t}\right\rfloor\right)=(r-\ell+1)\,G(q).$$
وهكذا تنخفض كلفة التقييم الواحد من خطية في \(n\) إلى عدد الحواصل المختلفة فقط، أي إلى رتبة \(O(\sqrt n)\).
القيم نفسها \(G(q)\) تظهر مرات كثيرة داخل كتل مختلفة. لذلك تُحسب كل قيمة مرة واحدة فقط، ثم تُستعاد من ذاكرة التخزين المؤقت عند الحاجة. اجتماع التجميع على أساس الحاصل مع التذكّر هو ما يجعل الخوارزمية عملية حتى عند القيم الكبيرة جدًا.
أولًا نحسب \(A(10)\) من الصيغة المغلقة:
$$A(10)=\left\lfloor\frac{10+1}{2}\right\rfloor^2+\left\lfloor\frac{5+1}{2}\right\rfloor^2+\left\lfloor\frac{2+1}{2}\right\rfloor^2+\left\lfloor\frac{1+1}{2}\right\rfloor^2=25+9+1+1=36.$$
أما الحواصل عندما \(t\ge 2\) فهي
$$\left\lfloor\frac{10}{t}\right\rfloor=5,3,2,2,1,1,1,1,1 \qquad (t=2,\dots,10).$$
إذن
$$G(10)=36-\bigl(G(5)+G(3)+2G(2)+5G(1)\bigr).$$
والقيم الأصغر هي
$$G(1)=1,\qquad G(2)=1,\qquad G(3)=1+\varphi(3)=3,\qquad G(5)=1+\varphi(3)+\varphi(5)=7.$$
ومن ثم
$$G(10)=36-(7+3+2+5)=19.$$
والتحقق المباشر يعطي النتيجة نفسها:
$$\varphi(1)+\varphi(3)+\varphi(5)+\varphi(7)+\varphi(9)=1+2+4+6+6=19.$$
تنفّذ صيغ C++ وPython وJava الخطة الرياضية نفسها. عند طلب قيمة \(n\)، تحسب التنفيذات أولًا \(A(n)\) عبر تقليص الحد الحالي إلى النصف مرارًا، وإضافة مربع عدد الأعداد الفردية حتى ذلك الحد. بعد ذلك تُقيِّم العلاقة الخاصة بـ \(G(n)\) على شكل كتل \([\ell,r]\) لها الحاصل نفسه، وتطلب عوديًا القيمة الأصغر \(G(q)\)، ثم تطرح \((r-\ell+1)G(q)\) من المجموع الجاري.
تُخزَّن كل مسألة فرعية مكتملة في ذاكرة مؤقتة مفهرسة بقيمة الوسيط، وبذلك لا يُعاد حساب القيمة نفسها أكثر من مرة. الاختلاف بين اللغات الثلاث يقتصر على الصياغة البرمجية وبنية التخزين؛ أما رياضيًا فهي تطبّق العلاقة نفسها، والتجميع نفسه، والحساب الصحيح نفسه بالأعداد الصحيحة.
حساب \(A(n)\) يحتاج إلى زمن \(O(\log n)\) لأن الوسيط ينقسم على \(2\) في كل خطوة. أما الاستدعاء العودي الواحد على وسيط \(m\) فيعالج كتلة واحدة لكل قيمة مختلفة من \(\lfloor m/t\rfloor\)، ولذلك يحتاج إلى \(O(\sqrt m)\) من خطوات الكتل. إذا رمزنا بمجموعة القيم المختلفة المخزنة في الذاكرة المؤقتة إلى \(M\)، فإن زمن التنفيذ الكلي هو
$$O\left(\sum_{m\in M}\sqrt{m}\right),$$
بينما يكون استهلاك الذاكرة \(O(|M|)\). وحتى على المستوى الأعلى لا يوجد إلا \(O(\sqrt n)\) من الحواصل المختلفة، ولهذا تكون الطريقة أسرع بكثير من جمع \(\varphi(m)\) مباشرة لكل \(m\) فردي حتى \(n\).