The task is to evaluate the cumulative quantity
$$S(m)=\sum_{n=1}^{m}\big(J_A(n)+J_B(n)\big)$$
for the very large input \(m=123456789\), rounded to eight decimal places. The direct definitions of \(J_A(n)\) and \(J_B(n)\) are far too expensive to sum term by term up to that scale, so the solution replaces them with a short analytic formula built from harmonic numbers and a rapidly convergent binary-weighted series.
A useful checkpoint is \(n=6\), where the sample values are
$$J_A(6)=0.39505208,\qquad J_B(6)=0.43333333,\qquad S(6)=7.58932292.$$
The implementations are designed so that these small values are reproduced exactly enough to justify the large-\(m\) shortcut.
The whole reduction revolves around harmonic numbers
$$H_n=\sum_{k=1}^{n}\frac{1}{k}$$
and an auxiliary sequence that captures the contribution of \(J_B(n)\).
Introduce
$$B_n=\sum_{j=0}^{n-1}\frac{2^{-j}}{n-j}.$$
Changing variables with \(k=n-j\) gives the equivalent form
$$B_n=\frac{1}{2^n}\sum_{k=1}^{n}\frac{2^k}{k}.$$
The key observation used by the implementations is that
$$J_B(n)=B_n.$$
This is already a major simplification: instead of recomputing the original game expression, we only need to understand one weighted reciprocal sum.
The transformed form makes the recurrence immediate. Starting from
$$B_n=\frac{1}{2^n}\sum_{k=1}^{n}\frac{2^k}{k},\qquad B_{n-1}=\frac{1}{2^{n-1}}\sum_{k=1}^{n-1}\frac{2^k}{k},$$
we multiply the second equation by \(1/2\):
$$\frac{1}{2}B_{n-1}=\frac{1}{2^n}\sum_{k=1}^{n-1}\frac{2^k}{k}.$$
Subtracting yields
$$B_n-\frac{1}{2}B_{n-1}=\frac{1}{2^n}\cdot\frac{2^n}{n}=\frac{1}{n},$$
so the recurrence is
$$\boxed{B_n=\frac{1}{n}+\frac{1}{2}B_{n-1}}$$
with starting value \(B_1=1\). This recurrence is the engine behind both the exact small-\(n\) validation and the later summation identity.
The implementations also use
$$J_A(n)=B_n-\frac{H_n}{2^n}.$$
Combining this with \(J_B(n)=B_n\) gives the termwise identity
$$J_A(n)+J_B(n)=2B_n-\frac{H_n}{2^n}.$$
Therefore the whole problem becomes
$$S(m)=2\sum_{n=1}^{m}B_n-\sum_{n=1}^{m}\frac{H_n}{2^n}.$$
At this stage the original combinatorial definitions have disappeared; everything is now expressed using standard analytic objects.
Let
$$T_m=\sum_{n=1}^{m}B_n.$$
Summing the recurrence \(B_n-\frac{1}{2}B_{n-1}=1/n\) from \(n=1\) to \(m\) gives
$$\sum_{n=1}^{m}B_n-\frac{1}{2}\sum_{n=1}^{m}B_{n-1}=H_m.$$
Because \(B_0=0\), we have
$$\sum_{n=1}^{m}B_{n-1}=B_0+B_1+\cdots+B_{m-1}=T_m-B_m.$$
Substituting this into the previous line gives
$$T_m-\frac{1}{2}(T_m-B_m)=H_m,$$
hence
$$\boxed{T_m=2H_m-B_m.}$$
So the cumulative sum simplifies to
$$\boxed{S(m)=4H_m-2B_m-\sum_{n=1}^{m}\frac{H_n}{2^n}.}$$
The remaining finite sum has a classic generating-function evaluation. For \(|x|<1\),
$$\sum_{n\ge 1}H_nx^n=\sum_{n\ge 1}\sum_{k=1}^{n}\frac{x^n}{k}=\sum_{k\ge 1}\frac{1}{k}\sum_{n\ge k}x^n=\frac{1}{1-x}\sum_{k\ge 1}\frac{x^k}{k}=-\frac{\log(1-x)}{1-x}.$$
Setting \(x=\tfrac12\) gives
$$\sum_{n\ge 1}\frac{H_n}{2^n}=2\log 2.$$
Therefore
$$S(m)=4H_m-2B_m-2\log 2+R_m,$$
where the omitted tail is
$$R_m=\sum_{n=m+1}^{\infty}\frac{H_n}{2^n}.$$
A convenient bound comes from rearranging the tail:
$$R_m=\frac{H_m}{2^m}+2\sum_{k=m+1}^{\infty}\frac{1}{k2^k}\le \frac{1}{2^m}\left(H_m+\frac{2}{m+1}\right).$$
For \(m=123456789\), this error is astronomically smaller than \(10^{-8}\), so rounding to eight decimals is unchanged if we replace the finite sum by \(2\log 2\).
The harmonic number is estimated with the Euler-Maclaurin expansion
$$H_m=\log m+\gamma+\frac{1}{2m}-\frac{1}{12m^2}+O\!\left(\frac{1}{m^4}\right),$$
where \(\gamma\) is the Euler-Mascheroni constant. At \(m=123456789\), the neglected terms are far below the required precision.
For \(B_m\), the implementations evaluate the short truncation
$$B_m\approx \sum_{j=0}^{200}\frac{2^{-j}}{m-j}.$$
The discarded tail obeys
$$0\le \sum_{j=201}^{m-1}\frac{2^{-j}}{m-j}\le \sum_{j=201}^{\infty}2^{-j}=2^{-200},$$
so the truncation error is again negligible. Numerically, the large-\(m\) computation is therefore stable and effectively constant time.
Starting from \(B_1=1\) and using \(B_n=\frac1n+\frac12B_{n-1}\), we get
$$B_2=1,\qquad B_3=\frac{5}{6},\qquad B_4=\frac{2}{3},\qquad B_5=\frac{8}{15},\qquad B_6=\frac{13}{30}.$$
Also
$$H_6=1+\frac12+\frac13+\frac14+\frac15+\frac16=\frac{49}{20}.$$
Hence
$$J_B(6)=B_6=\frac{13}{30}=0.43333333\ldots$$
and
$$J_A(6)=B_6-\frac{H_6}{2^6}=\frac{13}{30}-\frac{49}{1280}=\frac{1517}{3840}=0.39505208\ldots$$
Summing the first six values of \(J_A(n)+J_B(n)\) gives
$$S(6)=7.5893229166\ldots,$$
which rounds to \(7.58932292\), matching the stated checkpoint.
The C++, Python, and Java implementations all use the same final formula. They compute \(H_m\) from the short Euler-Maclaurin expansion, evaluate \(B_m\) by summing only the first 201 terms of the binary-weighted reciprocal series, substitute the constant \(2\log 2\) for the infinite harmonic series, and return
$$4H_m-2B_m-2\log 2$$
to the requested eight-decimal precision.
This avoids any loop up to \(m\). The recurrence for \(B_n\) is still useful conceptually and for small worked examples, but the actual large-input computation uses only a fixed amount of arithmetic.
The final evaluation path uses a fixed number of floating-point operations: a few arithmetic terms for the harmonic asymptotic, a 201-term truncation for \(B_m\), and constant-time logarithms. Therefore the runtime is \(O(1)\) and the memory usage is \(O(1)\). If one were to compute small checkpoints directly from the recurrence, that auxiliary validation would be \(O(m)\), but it is not part of the final large-\(m\) solver.
Gesucht ist der kumulative Wert
$$S(m)=\sum_{n=1}^{m}\big(J_A(n)+J_B(n)\big)$$
für den sehr großen Eingabewert \(m=123456789\), gerundet auf acht Nachkommastellen. Die direkten Definitionen von \(J_A(n)\) und \(J_B(n)\) wären für so große Indizes viel zu teuer, daher ersetzt die Lösung sie durch eine kurze analytische Formel mit harmonischen Zahlen und einer sehr schnell konvergierenden binär gewichteten Reihe.
Ein wichtiger Kontrollpunkt ist \(n=6\). Dort gelten
$$J_A(6)=0.39505208,\qquad J_B(6)=0.43333333,\qquad S(6)=7.58932292.$$
Die Implementierungen sind genau so aufgebaut, dass diese kleinen Referenzwerte erhalten bleiben und damit die Abkürzung für großes \(m\) rechtfertigen.
Die gesamte Reduktion basiert auf den harmonischen Zahlen
$$H_n=\sum_{k=1}^{n}\frac{1}{k}$$
und auf einer Hilfsfolge, die den Beitrag von \(J_B(n)\) isoliert.
Wir führen ein:
$$B_n=\sum_{j=0}^{n-1}\frac{2^{-j}}{n-j}.$$
Mit dem Variablenwechsel \(k=n-j\) erhält man die äquivalente Form
$$B_n=\frac{1}{2^n}\sum_{k=1}^{n}\frac{2^k}{k}.$$
Die zentrale Beobachtung der Implementierungen lautet dann
$$J_B(n)=B_n.$$
Das ist bereits die wesentliche Vereinfachung: Statt den ursprünglichen Spielausdruck direkt zu berechnen, genügt eine einzige gewichtete Reziprokensumme.
Die transformierte Darstellung macht die Rekurrenz sofort sichtbar. Aus
$$B_n=\frac{1}{2^n}\sum_{k=1}^{n}\frac{2^k}{k},\qquad B_{n-1}=\frac{1}{2^{n-1}}\sum_{k=1}^{n-1}\frac{2^k}{k}$$
folgt nach Multiplikation der zweiten Gleichung mit \(1/2\):
$$\frac{1}{2}B_{n-1}=\frac{1}{2^n}\sum_{k=1}^{n-1}\frac{2^k}{k}.$$
Subtrahiert man, so bleibt
$$B_n-\frac{1}{2}B_{n-1}=\frac{1}{2^n}\cdot\frac{2^n}{n}=\frac{1}{n},$$
also
$$\boxed{B_n=\frac{1}{n}+\frac{1}{2}B_{n-1}}$$
mit Anfangswert \(B_1=1\). Genau diese Rekurrenz trägt sowohl die exakten kleinen Tests als auch die spätere Summenformel.
Zusätzlich benutzen die Implementierungen die Identität
$$J_A(n)=B_n-\frac{H_n}{2^n}.$$
Mit \(J_B(n)=B_n\) folgt damit unmittelbar
$$J_A(n)+J_B(n)=2B_n-\frac{H_n}{2^n}.$$
Das gesamte Problem reduziert sich also auf
$$S(m)=2\sum_{n=1}^{m}B_n-\sum_{n=1}^{m}\frac{H_n}{2^n}.$$
Ab hier sind die ursprünglichen kombinatorischen Definitionen verschwunden; übrig bleiben nur noch Standardobjekte der Analysis.
Setze
$$T_m=\sum_{n=1}^{m}B_n.$$
Summiert man \(B_n-\frac{1}{2}B_{n-1}=1/n\) für \(n=1,\dots,m\), so erhält man
$$\sum_{n=1}^{m}B_n-\frac{1}{2}\sum_{n=1}^{m}B_{n-1}=H_m.$$
Wegen \(B_0=0\) gilt
$$\sum_{n=1}^{m}B_{n-1}=B_0+B_1+\cdots+B_{m-1}=T_m-B_m.$$
Einsetzen liefert
$$T_m-\frac{1}{2}(T_m-B_m)=H_m,$$
also
$$\boxed{T_m=2H_m-B_m.}$$
Daher vereinfacht sich die Gesamtsumme zu
$$\boxed{S(m)=4H_m-2B_m-\sum_{n=1}^{m}\frac{H_n}{2^n}.}$$
Für die verbleibende endliche Summe gibt es eine klassische erzeugende Funktion. Für \(|x|<1\) gilt
$$\sum_{n\ge 1}H_nx^n=\sum_{n\ge 1}\sum_{k=1}^{n}\frac{x^n}{k}=\sum_{k\ge 1}\frac{1}{k}\sum_{n\ge k}x^n=\frac{1}{1-x}\sum_{k\ge 1}\frac{x^k}{k}=-\frac{\log(1-x)}{1-x}.$$
Für \(x=\tfrac12\) folgt
$$\sum_{n\ge 1}\frac{H_n}{2^n}=2\log 2.$$
Damit wird
$$S(m)=4H_m-2B_m-2\log 2+R_m,$$
wobei der abgeschnittene Rest
$$R_m=\sum_{n=m+1}^{\infty}\frac{H_n}{2^n}$$
ist. Eine praktische Schranke erhält man durch Umordnung:
$$R_m=\frac{H_m}{2^m}+2\sum_{k=m+1}^{\infty}\frac{1}{k2^k}\le \frac{1}{2^m}\left(H_m+\frac{2}{m+1}\right).$$
Für \(m=123456789\) ist dieser Fehler astronomisch kleiner als \(10^{-8}\). Deshalb darf die endliche Summe für die geforderte Rundung gefahrlos durch \(2\log 2\) ersetzt werden.
Die harmonische Zahl wird mit der Euler-Maclaurin-Entwicklung angenähert:
$$H_m=\log m+\gamma+\frac{1}{2m}-\frac{1}{12m^2}+O\!\left(\frac{1}{m^4}\right),$$
wobei \(\gamma\) die Euler-Mascheroni-Konstante ist. Bei \(m=123456789\) liegen die ausgelassenen Terme weit unter der geforderten Genauigkeit.
Für \(B_m\) berechnen die Implementierungen die kurze Trunkierung
$$B_m\approx \sum_{j=0}^{200}\frac{2^{-j}}{m-j}.$$
Der abgeschnittene Rest erfüllt
$$0\le \sum_{j=201}^{m-1}\frac{2^{-j}}{m-j}\le \sum_{j=201}^{\infty}2^{-j}=2^{-200},$$
sodass auch hier der Fehler praktisch verschwindet. Numerisch ist die große Rechnung damit stabil und effektiv konstant schnell.
Ausgehend von \(B_1=1\) und der Rekurrenz \(B_n=\frac1n+\frac12B_{n-1}\) erhält man
$$B_2=1,\qquad B_3=\frac{5}{6},\qquad B_4=\frac{2}{3},\qquad B_5=\frac{8}{15},\qquad B_6=\frac{13}{30}.$$
Außerdem gilt
$$H_6=1+\frac12+\frac13+\frac14+\frac15+\frac16=\frac{49}{20}.$$
Damit folgt
$$J_B(6)=B_6=\frac{13}{30}=0.43333333\ldots$$
und
$$J_A(6)=B_6-\frac{H_6}{2^6}=\frac{13}{30}-\frac{49}{1280}=\frac{1517}{3840}=0.39505208\ldots$$
Die Summe der ersten sechs Werte \(J_A(n)+J_B(n)\) ist
$$S(6)=7.5893229166\ldots,$$
also gerundet \(7.58932292\), genau der Kontrollwert aus der Aufgabenstellung.
Die Implementierungen in C++, Python und Java verwenden alle dieselbe Endformel. Sie berechnen \(H_m\) über die kurze Euler-Maclaurin-Entwicklung, werten \(B_m\) über nur 201 Terme der binär gewichteten Reziprokensumme aus, setzen für die unendliche harmonische Reihe die Konstante \(2\log 2\) ein und geben dann
$$4H_m-2B_m-2\log 2$$
mit der verlangten Genauigkeit von acht Nachkommastellen zurück.
Ein Durchlauf bis \(m\) findet also nicht statt. Die Rekurrenz für \(B_n\) bleibt zwar für kleine Beispiele und Kontrollrechnungen wichtig, der eigentliche Solver für den großen Eingabewert benutzt jedoch nur eine feste Menge arithmetischer Operationen.
Der finale Rechenweg benötigt nur eine feste Anzahl von Fließkommaoperationen: einige wenige Terme der harmonischen Asymptotik, eine 201-gliedrige Trunkierung für \(B_m\) und konstante viele Logarithmen. Damit ist die Laufzeit \(O(1)\) und der Speicherbedarf \(O(1)\). Würde man kleine Kontrollwerte direkt über die Rekurrenz berechnen, entstünde dort zwar ein \(O(m)\)-Zusatzpfad, doch dieser gehört nicht zum eigentlichen Solver für großes \(m\).
İstenen büyüklük
$$S(m)=\sum_{n=1}^{m}\big(J_A(n)+J_B(n)\big)$$
toplamının çok büyük \(m=123456789\) girdisi için sekiz ondalık basamağa yuvarlanmış değeridir. \(J_A(n)\) ve \(J_B(n)\) ifadelerini doğrudan kullanıp \(1\)'den \(m\)'ye kadar toplamak pratik değildir; bu yüzden çözüm, bunları harmonik sayılar ve çok hızlı yakınsayan ikili ağırlıklı bir seri cinsinden kısa bir analitik ifadeye indirger.
Önemli bir kontrol noktası \(n=6\) değeridir:
$$J_A(6)=0.39505208,\qquad J_B(6)=0.43333333,\qquad S(6)=7.58932292.$$
Uygulamalar, büyük-\(m\) kısayoluna geçmeden önce bu küçük örneği doğru verecek şekilde kuruludur.
Tüm indirgeme, harmonik sayılar
$$H_n=\sum_{k=1}^{n}\frac{1}{k}$$
ve \(J_B(n)\) katkısını tek başına taşıyan yardımcı bir dizi etrafında döner.
Şunu tanımlayalım:
$$B_n=\sum_{j=0}^{n-1}\frac{2^{-j}}{n-j}.$$
\(k=n-j\) değişken dönüşümüyle eşdeğer biçim
$$B_n=\frac{1}{2^n}\sum_{k=1}^{n}\frac{2^k}{k}$$
elde edilir. Uygulamaların kullandığı ana gözlem
$$J_B(n)=B_n$$
eşitliğidir. Böylece özgün oyun ifadesi yerine yalnızca tek bir ağırlıklı tersler toplamını anlamamız yeterli olur.
Dönüştürülmüş biçim yinelemeyi doğrudan verir. Çünkü
$$B_n=\frac{1}{2^n}\sum_{k=1}^{n}\frac{2^k}{k},\qquad B_{n-1}=\frac{1}{2^{n-1}}\sum_{k=1}^{n-1}\frac{2^k}{k}$$
olduğundan ikinci eşitliği \(1/2\) ile çarparsak
$$\frac{1}{2}B_{n-1}=\frac{1}{2^n}\sum_{k=1}^{n-1}\frac{2^k}{k}$$
olur. Çıkarınca
$$B_n-\frac{1}{2}B_{n-1}=\frac{1}{2^n}\cdot\frac{2^n}{n}=\frac{1}{n},$$
yani
$$\boxed{B_n=\frac{1}{n}+\frac{1}{2}B_{n-1}}$$
bulunur. Başlangıç değeri \(B_1=1\) olur. Bu yineleme hem küçük örneklerin tam hesabını hem de daha sonra kullanılacak toplam özdeşliğini sağlar.
Uygulamalar ayrıca
$$J_A(n)=B_n-\frac{H_n}{2^n}$$
özdeşliğini kullanır. Bunu \(J_B(n)=B_n\) ile birleştirince
$$J_A(n)+J_B(n)=2B_n-\frac{H_n}{2^n}$$
elde edilir. Dolayısıyla problem artık
$$S(m)=2\sum_{n=1}^{m}B_n-\sum_{n=1}^{m}\frac{H_n}{2^n}$$
biçimine indirgenmiştir. Bu aşamada özgün kombinatorik tanımlar ortadan kalkar ve yerini standart analitik nesneler alır.
$$T_m=\sum_{n=1}^{m}B_n$$
olsun. \(B_n-\frac{1}{2}B_{n-1}=1/n\) eşitliğini \(n=1\)'den \(m\)'ye kadar toplarsak
$$\sum_{n=1}^{m}B_n-\frac{1}{2}\sum_{n=1}^{m}B_{n-1}=H_m$$
elde edilir. \(B_0=0\) olduğundan
$$\sum_{n=1}^{m}B_{n-1}=B_0+B_1+\cdots+B_{m-1}=T_m-B_m$$
yazabiliriz. Yerine koyunca
$$T_m-\frac{1}{2}(T_m-B_m)=H_m,$$
dolayısıyla
$$\boxed{T_m=2H_m-B_m.}$$
Böylece toplam
$$\boxed{S(m)=4H_m-2B_m-\sum_{n=1}^{m}\frac{H_n}{2^n}.}$$
şeklini alır.
Kalan sonlu toplam için klasik bir üreteç fonksiyonu hesabı vardır. \(|x|<1\) için
$$\sum_{n\ge 1}H_nx^n=\sum_{n\ge 1}\sum_{k=1}^{n}\frac{x^n}{k}=\sum_{k\ge 1}\frac{1}{k}\sum_{n\ge k}x^n=\frac{1}{1-x}\sum_{k\ge 1}\frac{x^k}{k}=-\frac{\log(1-x)}{1-x}.$$
\(x=\tfrac12\) seçilirse
$$\sum_{n\ge 1}\frac{H_n}{2^n}=2\log 2$$
çıkar. Bu yüzden
$$S(m)=4H_m-2B_m-2\log 2+R_m,$$
burada ihmal edilen kuyruk
$$R_m=\sum_{n=m+1}^{\infty}\frac{H_n}{2^n}$$
olarak tanımlanır. Kullanışlı bir üst sınır
$$R_m=\frac{H_m}{2^m}+2\sum_{k=m+1}^{\infty}\frac{1}{k2^k}\le \frac{1}{2^m}\left(H_m+\frac{2}{m+1}\right)$$
şeklindedir. \(m=123456789\) için bu hata \(10^{-8}\)'den akıl almaz derecede küçüktür; dolayısıyla sekiz basamaklı sonuç değişmez.
Harmonik sayı Euler-Maclaurin açılımıyla yaklaşık hesaplanır:
$$H_m=\log m+\gamma+\frac{1}{2m}-\frac{1}{12m^2}+O\!\left(\frac{1}{m^4}\right),$$
burada \(\gamma\) Euler-Mascheroni sabitidir. \(m=123456789\) için atlanan terimler istenen hassasiyetin çok altındadır.
\(B_m\) için uygulamalar kısa kesilmiş toplamı kullanır:
$$B_m\approx \sum_{j=0}^{200}\frac{2^{-j}}{m-j}.$$
Atılan kuyruk ise
$$0\le \sum_{j=201}^{m-1}\frac{2^{-j}}{m-j}\le \sum_{j=201}^{\infty}2^{-j}=2^{-200}$$
koşulunu sağlar. Yani burada da hata tamamen ihmal edilebilir durumdadır ve büyük girdide hesap neredeyse sabit zamanda yapılır.
\(B_1=1\) ve \(B_n=\frac1n+\frac12B_{n-1}\) yinelemesinden
$$B_2=1,\qquad B_3=\frac{5}{6},\qquad B_4=\frac{2}{3},\qquad B_5=\frac{8}{15},\qquad B_6=\frac{13}{30}$$
elde edilir. Ayrıca
$$H_6=1+\frac12+\frac13+\frac14+\frac15+\frac16=\frac{49}{20}.$$
Dolayısıyla
$$J_B(6)=B_6=\frac{13}{30}=0.43333333\ldots$$
ve
$$J_A(6)=B_6-\frac{H_6}{2^6}=\frac{13}{30}-\frac{49}{1280}=\frac{1517}{3840}=0.39505208\ldots$$
olur. İlk altı terimin toplamı
$$S(6)=7.5893229166\ldots,$$
yani yuvarlanınca \(7.58932292\) çıkar; bu da verilen kontrol değeriyle aynıdır.
C++, Python ve Java uygulamaları aynı son formülü kullanır. Önce \(H_m\) kısa Euler-Maclaurin açılımıyla hesaplanır, sonra \(B_m\) için ikili ağırlıklı tersler serisinin yalnızca ilk 201 terimi toplanır, sonsuz harmonik seri yerine \(2\log 2\) sabiti konur ve sonuç olarak
$$4H_m-2B_m-2\log 2$$
sekiz ondalık basamağa uygun biçimde döndürülür.
Böylece \(m\)'ye kadar dönen bir döngüye gerek kalmaz. \(B_n\) yinelemesi küçük örnekleri açıklamak için önemini korur, fakat büyük girişte asıl hesap sabit sayıda aritmetik işlemle tamamlanır.
Son değerlendirme yolu sabit sayıda kayan noktalı işlem kullanır: harmonik asimptotik için birkaç terim, \(B_m\) için 201 terimlik kesme ve sabit sayıda logaritma. Bu nedenle zaman karmaşıklığı \(O(1)\), bellek karmaşıklığı \(O(1)\)'dir. Küçük kontrol değerleri yineleme ile ayrıca hesaplansa bu yan yol \(O(m)\) olurdu; ancak bu büyük-\(m\) çözücüsünün parçası değildir.
La cantidad pedida es
$$S(m)=\sum_{n=1}^{m}\big(J_A(n)+J_B(n)\big)$$
para la entrada enorme \(m=123456789\), redondeada a ocho decimales. Usar directamente las definiciones de \(J_A(n)\) y \(J_B(n)\) y sumar término a término hasta ese índice sería demasiado costoso, así que la solución las reemplaza por una fórmula analítica corta en función de números armónicos y de una serie ponderada por potencias de \(2\) que converge muy deprisa.
Un punto de control útil es \(n=6\), donde se tiene
$$J_A(6)=0.39505208,\qquad J_B(6)=0.43333333,\qquad S(6)=7.58932292.$$
Las implementaciones están construidas precisamente para reproducir estos valores pequeños antes de aplicar el atajo para \(m\) grande.
Toda la reducción gira alrededor de los números armónicos
$$H_n=\sum_{k=1}^{n}\frac{1}{k}$$
y de una sucesión auxiliar que recoge la contribución de \(J_B(n)\).
Introducimos
$$B_n=\sum_{j=0}^{n-1}\frac{2^{-j}}{n-j}.$$
Con el cambio de variable \(k=n-j\) se obtiene la forma equivalente
$$B_n=\frac{1}{2^n}\sum_{k=1}^{n}\frac{2^k}{k}.$$
La observación central usada por las implementaciones es
$$J_B(n)=B_n.$$
Esta ya es la simplificación esencial: en vez de recalcular la expresión original del juego, basta estudiar una sola suma recíproca con pesos binarios.
La forma transformada hace que la recurrencia sea inmediata. A partir de
$$B_n=\frac{1}{2^n}\sum_{k=1}^{n}\frac{2^k}{k},\qquad B_{n-1}=\frac{1}{2^{n-1}}\sum_{k=1}^{n-1}\frac{2^k}{k},$$
multiplicamos la segunda igualdad por \(1/2\):
$$\frac{1}{2}B_{n-1}=\frac{1}{2^n}\sum_{k=1}^{n-1}\frac{2^k}{k}.$$
Al restar aparece
$$B_n-\frac{1}{2}B_{n-1}=\frac{1}{2^n}\cdot\frac{2^n}{n}=\frac{1}{n},$$
así que
$$\boxed{B_n=\frac{1}{n}+\frac{1}{2}B_{n-1}}$$
con condición inicial \(B_1=1\). Esta recurrencia es la base de las comprobaciones exactas para \(n\) pequeño y de la identidad sumada que se usa después.
Las implementaciones usan además
$$J_A(n)=B_n-\frac{H_n}{2^n}.$$
Combinando esto con \(J_B(n)=B_n\) obtenemos
$$J_A(n)+J_B(n)=2B_n-\frac{H_n}{2^n}.$$
Por tanto, el problema completo pasa a ser
$$S(m)=2\sum_{n=1}^{m}B_n-\sum_{n=1}^{m}\frac{H_n}{2^n}.$$
A partir de aquí ya no aparecen las definiciones combinatorias originales; todo queda escrito en términos analíticos estándar.
Sea
$$T_m=\sum_{n=1}^{m}B_n.$$
Si sumamos \(B_n-\frac{1}{2}B_{n-1}=1/n\) desde \(n=1\) hasta \(m\), resulta
$$\sum_{n=1}^{m}B_n-\frac{1}{2}\sum_{n=1}^{m}B_{n-1}=H_m.$$
Como \(B_0=0\), se cumple
$$\sum_{n=1}^{m}B_{n-1}=B_0+B_1+\cdots+B_{m-1}=T_m-B_m.$$
Sustituyendo,
$$T_m-\frac{1}{2}(T_m-B_m)=H_m,$$
de donde
$$\boxed{T_m=2H_m-B_m.}$$
Así la suma total se reduce a
$$\boxed{S(m)=4H_m-2B_m-\sum_{n=1}^{m}\frac{H_n}{2^n}.}$$
La suma finita restante tiene una evaluación clásica por función generadora. Para \(|x|<1\),
$$\sum_{n\ge 1}H_nx^n=\sum_{n\ge 1}\sum_{k=1}^{n}\frac{x^n}{k}=\sum_{k\ge 1}\frac{1}{k}\sum_{n\ge k}x^n=\frac{1}{1-x}\sum_{k\ge 1}\frac{x^k}{k}=-\frac{\log(1-x)}{1-x}.$$
Tomando \(x=\tfrac12\),
$$\sum_{n\ge 1}\frac{H_n}{2^n}=2\log 2.$$
Por tanto,
$$S(m)=4H_m-2B_m-2\log 2+R_m,$$
donde la cola omitida es
$$R_m=\sum_{n=m+1}^{\infty}\frac{H_n}{2^n}.$$
Una cota útil se obtiene reordenando la suma:
$$R_m=\frac{H_m}{2^m}+2\sum_{k=m+1}^{\infty}\frac{1}{k2^k}\le \frac{1}{2^m}\left(H_m+\frac{2}{m+1}\right).$$
Para \(m=123456789\), este error es muchísimo menor que \(10^{-8}\), de modo que el redondeo final no cambia al sustituir la suma finita por \(2\log 2\).
El número armónico se aproxima mediante Euler-Maclaurin:
$$H_m=\log m+\gamma+\frac{1}{2m}-\frac{1}{12m^2}+O\!\left(\frac{1}{m^4}\right),$$
donde \(\gamma\) es la constante de Euler-Mascheroni. Para \(m=123456789\), los términos ignorados quedan muy por debajo de la precisión requerida.
Para \(B_m\), las implementaciones calculan la truncación corta
$$B_m\approx \sum_{j=0}^{200}\frac{2^{-j}}{m-j}.$$
La cola descartada satisface
$$0\le \sum_{j=201}^{m-1}\frac{2^{-j}}{m-j}\le \sum_{j=201}^{\infty}2^{-j}=2^{-200},$$
así que el error también es despreciable. Numéricamente, el cálculo para \(m\) grande es estable y de tiempo efectivo constante.
Partiendo de \(B_1=1\) y usando \(B_n=\frac1n+\frac12B_{n-1}\), obtenemos
$$B_2=1,\qquad B_3=\frac{5}{6},\qquad B_4=\frac{2}{3},\qquad B_5=\frac{8}{15},\qquad B_6=\frac{13}{30}.$$
Además,
$$H_6=1+\frac12+\frac13+\frac14+\frac15+\frac16=\frac{49}{20}.$$
Entonces
$$J_B(6)=B_6=\frac{13}{30}=0.43333333\ldots$$
y
$$J_A(6)=B_6-\frac{H_6}{2^6}=\frac{13}{30}-\frac{49}{1280}=\frac{1517}{3840}=0.39505208\ldots$$
La suma de los seis primeros valores de \(J_A(n)+J_B(n)\) es
$$S(6)=7.5893229166\ldots,$$
que redondea a \(7.58932292\), exactamente el valor de control.
Las implementaciones en C++, Python y Java comparten la misma ruta final de cálculo. Evalúan \(H_m\) con la expansión corta de Euler-Maclaurin, calculan \(B_m\) sumando solo los primeros 201 términos de la serie recíproca ponderada por potencias de \(2\), sustituyen la constante \(2\log 2\) por la serie armónica infinita y devuelven
$$4H_m-2B_m-2\log 2$$
con la precisión pedida de ocho decimales.
Eso evita cualquier bucle hasta \(m\). La recurrencia de \(B_n\) sigue siendo útil para explicar el método y verificar ejemplos pequeños, pero el cálculo real para la entrada grande usa solo una cantidad fija de operaciones aritméticas.
La ruta final de evaluación realiza un número fijo de operaciones en coma flotante: unos pocos términos de la aproximación armónica, una truncación de 201 términos para \(B_m\) y un número constante de logaritmos. Por lo tanto, el tiempo es \(O(1)\) y la memoria también es \(O(1)\). Si se calcularan los ejemplos pequeños directamente con la recurrencia, ese camino auxiliar sería \(O(m)\), pero no forma parte del solucionador final para \(m\) grande.
题目要求计算累计量
$$S(m)=\sum_{n=1}^{m}\big(J_A(n)+J_B(n)\big)$$
在巨大输入 \(m=123456789\) 时的值，并保留八位小数。若直接按照 \(J_A(n)\) 与 \(J_B(n)\) 的原始定义逐项求到这么大的 \(m\)，代价会非常高，因此解法把它们改写成一个由调和数和一个快速收敛的二进制加权级数组成的解析表达式。
一个重要的校验点是 \(n=6\)。此时有
$$J_A(6)=0.39505208,\qquad J_B(6)=0.43333333,\qquad S(6)=7.58932292.$$
实现中的推导路线正是围绕这些小规模结果展开，先保证低阶样例成立，再把同样的恒等式推广到超大输入。
整个化简过程围绕两个对象展开：调和数
$$H_n=\sum_{k=1}^{n}\frac{1}{k}$$
以及专门刻画 \(J_B(n)\) 的辅助序列。
先引入
$$B_n=\sum_{j=0}^{n-1}\frac{2^{-j}}{n-j}.$$
令 \(k=n-j\) 后，可以得到完全等价的形式
$$B_n=\frac{1}{2^n}\sum_{k=1}^{n}\frac{2^k}{k}.$$
实现所使用的关键观察是
$$J_B(n)=B_n.$$
这一步已经把问题大幅简化：原先来自游戏过程的表达式，被压缩成一个只有倒数与 \(2\) 的幂权重的求和。
改写后的形式几乎直接给出递推。由
$$B_n=\frac{1}{2^n}\sum_{k=1}^{n}\frac{2^k}{k},\qquad B_{n-1}=\frac{1}{2^{n-1}}\sum_{k=1}^{n-1}\frac{2^k}{k}$$
把第二式乘上 \(1/2\)，得到
$$\frac{1}{2}B_{n-1}=\frac{1}{2^n}\sum_{k=1}^{n-1}\frac{2^k}{k}.$$
两式相减后只剩最后一项：
$$B_n-\frac{1}{2}B_{n-1}=\frac{1}{2^n}\cdot\frac{2^n}{n}=\frac{1}{n}.$$
于是得到递推关系
$$\boxed{B_n=\frac{1}{n}+\frac{1}{2}B_{n-1}}$$
并且起始值是 \(B_1=1\)。这个递推既能用来做小范围精确验证，也会在后面直接导出总和公式。
实现还使用了另一个恒等式：
$$J_A(n)=B_n-\frac{H_n}{2^n}.$$
再结合 \(J_B(n)=B_n\)，就得到
$$J_A(n)+J_B(n)=2B_n-\frac{H_n}{2^n}.$$
因此整个问题可以改写成
$$S(m)=2\sum_{n=1}^{m}B_n-\sum_{n=1}^{m}\frac{H_n}{2^n}.$$
到这一步为止，原题中的结构已经完全消失，剩下的是调和数与一个辅助序列的标准分析问题。
记
$$T_m=\sum_{n=1}^{m}B_n.$$
把递推式 \(B_n-\frac{1}{2}B_{n-1}=1/n\) 从 \(n=1\) 累加到 \(n=m\)，有
$$\sum_{n=1}^{m}B_n-\frac{1}{2}\sum_{n=1}^{m}B_{n-1}=H_m.$$
由于 \(B_0=0\)，可写成
$$\sum_{n=1}^{m}B_{n-1}=B_0+B_1+\cdots+B_{m-1}=T_m-B_m.$$
代回去之后得到
$$T_m-\frac{1}{2}(T_m-B_m)=H_m,$$
于是
$$\boxed{T_m=2H_m-B_m.}$$
因此总和进一步简化为
$$\boxed{S(m)=4H_m-2B_m-\sum_{n=1}^{m}\frac{H_n}{2^n}.}$$
剩下的有限和可以用经典生成函数求值。对 \(|x|<1\)，有
$$\sum_{n\ge 1}H_nx^n=\sum_{n\ge 1}\sum_{k=1}^{n}\frac{x^n}{k}=\sum_{k\ge 1}\frac{1}{k}\sum_{n\ge k}x^n=\frac{1}{1-x}\sum_{k\ge 1}\frac{x^k}{k}=-\frac{\log(1-x)}{1-x}.$$
令 \(x=\tfrac12\)，便得到
$$\sum_{n\ge 1}\frac{H_n}{2^n}=2\log 2.$$
于是可以写成
$$S(m)=4H_m-2B_m-2\log 2+R_m,$$
其中被忽略的尾项是
$$R_m=\sum_{n=m+1}^{\infty}\frac{H_n}{2^n}.$$
把这段尾项重新整理后，可以得到方便的上界
$$R_m=\frac{H_m}{2^m}+2\sum_{k=m+1}^{\infty}\frac{1}{k2^k}\le \frac{1}{2^m}\left(H_m+\frac{2}{m+1}\right).$$
当 \(m=123456789\) 时，这个误差比 \(10^{-8}\) 小得不可思议，因此把有限和直接换成 \(2\log 2\) 不会影响最后八位小数的舍入结果。
调和数 \(H_m\) 用 Euler-Maclaurin 展开近似：
$$H_m=\log m+\gamma+\frac{1}{2m}-\frac{1}{12m^2}+O\!\left(\frac{1}{m^4}\right),$$
其中 \(\gamma\) 是 Euler-Mascheroni 常数。对 \(m=123456789\) 这样的规模，省略项远远低于所需精度。
至于 \(B_m\)，实现只计算前 201 项：
$$B_m\approx \sum_{j=0}^{200}\frac{2^{-j}}{m-j}.$$
被截去的尾项满足
$$0\le \sum_{j=201}^{m-1}\frac{2^{-j}}{m-j}\le \sum_{j=201}^{\infty}2^{-j}=2^{-200},$$
所以这一部分误差同样可以忽略。换句话说，大输入时的数值计算不仅快，而且稳定。
从 \(B_1=1\) 出发，利用 \(B_n=\frac1n+\frac12B_{n-1}\)，可依次得到
$$B_2=1,\qquad B_3=\frac{5}{6},\qquad B_4=\frac{2}{3},\qquad B_5=\frac{8}{15},\qquad B_6=\frac{13}{30}.$$
同时
$$H_6=1+\frac12+\frac13+\frac14+\frac15+\frac16=\frac{49}{20}.$$
因此
$$J_B(6)=B_6=\frac{13}{30}=0.43333333\ldots$$
以及
$$J_A(6)=B_6-\frac{H_6}{2^6}=\frac{13}{30}-\frac{49}{1280}=\frac{1517}{3840}=0.39505208\ldots$$
前六项 \(J_A(n)+J_B(n)\) 的和为
$$S(6)=7.5893229166\ldots,$$
四舍五入后正好是 \(7.58932292\)，与校验值一致。
C++、Python 和 Java 三份实现采用完全相同的最终计算路径。它们先用短的 Euler-Maclaurin 展开求 \(H_m\)，再对二进制加权倒数级数只累加前 201 项来近似 \(B_m\)，把无限调和级数替换成常数 \(2\log 2\)，最后返回
$$4H_m-2B_m-2\log 2$$
并保留题目要求的八位小数。
这样就完全避免了从 \(1\) 一直循环到 \(m\) 的代价。递推式 \(B_n=\frac1n+\frac12B_{n-1}\) 仍然用于解释方法和构造小样例，但真正的大输入求值只需要固定数量的浮点运算。
最终求值路径只包含固定数量的浮点运算：调和数近似的几个项、\(B_m\) 的 201 项截断以及常数次对数运算。因此时间复杂度是 \(O(1)\)，空间复杂度也是 \(O(1)\)。如果为了校验而用递推精确算小范围样例，那么那条辅助路径会是 \(O(m)\)，但它并不属于最终的大输入解法。
Нужно вычислить накопленную величину
$$S(m)=\sum_{n=1}^{m}\big(J_A(n)+J_B(n)\big)$$
для очень большого значения \(m=123456789\) с округлением до восьми знаков после запятой. Прямое использование исходных определений \(J_A(n)\) и \(J_B(n)\) и суммирование до такого индекса было бы слишком дорогим, поэтому решение заменяет их короткой аналитической формулой через гармонические числа и быстро сходящийся ряд с весами \(2^{-j}\).
Полезная контрольная точка возникает при \(n=6\):
$$J_A(6)=0.39505208,\qquad J_B(6)=0.43333333,\qquad S(6)=7.58932292.$$
Именно эти малые значения подтверждают, что переход к асимптотической формуле для большого \(m\) выполнен корректно.
Вся редукция строится вокруг гармонических чисел
$$H_n=\sum_{k=1}^{n}\frac{1}{k}$$
и вспомогательной последовательности, которая изолирует вклад \(J_B(n)\).
Введем
$$B_n=\sum_{j=0}^{n-1}\frac{2^{-j}}{n-j}.$$
После замены переменной \(k=n-j\) получаем эквивалентную форму
$$B_n=\frac{1}{2^n}\sum_{k=1}^{n}\frac{2^k}{k}.$$
Ключевое наблюдение, используемое реализациями, состоит в том, что
$$J_B(n)=B_n.$$
Это уже существенное упрощение: вместо исходного выражения из задачи остается один взвешенный ряд обратных величин.
Из преобразованной формы рекурсия получается сразу. Имеем
$$B_n=\frac{1}{2^n}\sum_{k=1}^{n}\frac{2^k}{k},\qquad B_{n-1}=\frac{1}{2^{n-1}}\sum_{k=1}^{n-1}\frac{2^k}{k}.$$
Умножим второе равенство на \(1/2\):
$$\frac{1}{2}B_{n-1}=\frac{1}{2^n}\sum_{k=1}^{n-1}\frac{2^k}{k}.$$
После вычитания остается
$$B_n-\frac{1}{2}B_{n-1}=\frac{1}{2^n}\cdot\frac{2^n}{n}=\frac{1}{n},$$
то есть
$$\boxed{B_n=\frac{1}{n}+\frac{1}{2}B_{n-1}}$$
при начальном условии \(B_1=1\). Эта рекурсия лежит в основе как точных малых проверок, так и формулы для суммы.
Реализации также используют тождество
$$J_A(n)=B_n-\frac{H_n}{2^n}.$$
Совмещая его с \(J_B(n)=B_n\), получаем
$$J_A(n)+J_B(n)=2B_n-\frac{H_n}{2^n}.$$
Значит, вся задача сводится к выражению
$$S(m)=2\sum_{n=1}^{m}B_n-\sum_{n=1}^{m}\frac{H_n}{2^n}.$$
С этого момента исходная комбинаторная постановка уже не нужна: остаются только стандартные аналитические объекты.
Обозначим
$$T_m=\sum_{n=1}^{m}B_n.$$
Суммируя \(B_n-\frac{1}{2}B_{n-1}=1/n\) по \(n=1,\dots,m\), получаем
$$\sum_{n=1}^{m}B_n-\frac{1}{2}\sum_{n=1}^{m}B_{n-1}=H_m.$$
Так как \(B_0=0\), имеем
$$\sum_{n=1}^{m}B_{n-1}=B_0+B_1+\cdots+B_{m-1}=T_m-B_m.$$
Подстановка дает
$$T_m-\frac{1}{2}(T_m-B_m)=H_m,$$
следовательно,
$$\boxed{T_m=2H_m-B_m.}$$
Тем самым итоговая сумма упрощается до
$$\boxed{S(m)=4H_m-2B_m-\sum_{n=1}^{m}\frac{H_n}{2^n}.}$$
Оставшаяся конечная сумма имеет классическое значение через производящую функцию. Для \(|x|<1\)
$$\sum_{n\ge 1}H_nx^n=\sum_{n\ge 1}\sum_{k=1}^{n}\frac{x^n}{k}=\sum_{k\ge 1}\frac{1}{k}\sum_{n\ge k}x^n=\frac{1}{1-x}\sum_{k\ge 1}\frac{x^k}{k}=-\frac{\log(1-x)}{1-x}.$$
Подстановка \(x=\tfrac12\) дает
$$\sum_{n\ge 1}\frac{H_n}{2^n}=2\log 2.$$
Поэтому
$$S(m)=4H_m-2B_m-2\log 2+R_m,$$
где отброшенный хвост равен
$$R_m=\sum_{n=m+1}^{\infty}\frac{H_n}{2^n}.$$
Удобная оценка получается после перестановки сумм:
$$R_m=\frac{H_m}{2^m}+2\sum_{k=m+1}^{\infty}\frac{1}{k2^k}\le \frac{1}{2^m}\left(H_m+\frac{2}{m+1}\right).$$
При \(m=123456789\) эта ошибка несравнимо меньше \(10^{-8}\), так что замена конечной суммы на \(2\log 2\) никак не влияет на округление ответа.
Для гармонического числа используется разложение Эйлера-Маклорена:
$$H_m=\log m+\gamma+\frac{1}{2m}-\frac{1}{12m^2}+O\!\left(\frac{1}{m^4}\right),$$
где \(\gamma\) обозначает постоянную Эйлера-Маскерони. Для \(m=123456789\) отброшенные члены намного меньше требуемой точности.
Последовательность \(B_m\) вычисляется по короткой усеченной сумме
$$B_m\approx \sum_{j=0}^{200}\frac{2^{-j}}{m-j}.$$
Оставшийся хвост удовлетворяет оценке
$$0\le \sum_{j=201}^{m-1}\frac{2^{-j}}{m-j}\le \sum_{j=201}^{\infty}2^{-j}=2^{-200},$$
поэтому и здесь ошибка пренебрежимо мала. На практике вычисление для большого \(m\) устойчиво и требует постоянного времени.
Стартуя с \(B_1=1\) и применяя рекурсию \(B_n=\frac1n+\frac12B_{n-1}\), получаем
$$B_2=1,\qquad B_3=\frac{5}{6},\qquad B_4=\frac{2}{3},\qquad B_5=\frac{8}{15},\qquad B_6=\frac{13}{30}.$$
Кроме того,
$$H_6=1+\frac12+\frac13+\frac14+\frac15+\frac16=\frac{49}{20}.$$
Следовательно,
$$J_B(6)=B_6=\frac{13}{30}=0.43333333\ldots$$
и
$$J_A(6)=B_6-\frac{H_6}{2^6}=\frac{13}{30}-\frac{49}{1280}=\frac{1517}{3840}=0.39505208\ldots$$
Сумма первых шести значений \(J_A(n)+J_B(n)\) равна
$$S(6)=7.5893229166\ldots,$$
что после округления дает \(7.58932292\), то есть точно совпадает с контрольным значением.
Реализации на C++, Python и Java используют один и тот же итоговый путь вычисления. Сначала они оценивают \(H_m\) по короткому разложению Эйлера-Маклорена, затем вычисляют \(B_m\), суммируя только первые 201 члена ряда с весами \(2^{-j}\), подставляют константу \(2\log 2\) вместо бесконечной гармонической суммы и возвращают
$$4H_m-2B_m-2\log 2$$
с требуемой точностью восемь знаков после запятой.
Тем самым полностью избегается цикл до \(m\). Рекурсия для \(B_n\) остается полезной для объяснения метода и малых примеров, но реальное вычисление для большого входа использует лишь фиксированное число арифметических операций.
Финальный путь вычисления содержит фиксированное число операций с плавающей точкой: несколько членов асимптотики гармонического числа, 201 член усечения для \(B_m\) и постоянное число логарифмов. Значит, время работы равно \(O(1)\), а память также \(O(1)\). Если отдельно считать малые контрольные примеры через рекурсию, такой вспомогательный путь имел бы стоимость \(O(m)\), но он не относится к финальному решателю для большого \(m\).
المطلوب هو حساب الكمية التراكمية
$$S(m)=\sum_{n=1}^{m}\big(J_A(n)+J_B(n)\big)$$
عند القيمة الكبيرة جدًا \(m=123456789\) مع التقريب إلى ثمانية منازل عشرية. استخدام التعريفين الأصليين لـ \(J_A(n)\) و\(J_B(n)\) ثم الجمع حدًا حدًا حتى هذا المؤشر سيكون مكلفًا جدًا، لذلك يحول الحل المسألة إلى صيغة تحليلية قصيرة تعتمد على الأعداد التوافقية وعلى متسلسلة ذات أوزان ثنائية تتقارب بسرعة شديدة.
توجد نقطة تحقق مهمة عند \(n=6\)، حيث تكون القيم
$$J_A(6)=0.39505208,\qquad J_B(6)=0.43333333,\qquad S(6)=7.58932292.$$
ولهذا تبني التطبيقات البرهان العددي بحيث تعيد هذه القيم الصغيرة أولًا، ثم تستخدم الاختزال نفسه للحالة الضخمة.
يعتمد الاختزال كله على الأعداد التوافقية
$$H_n=\sum_{k=1}^{n}\frac{1}{k}$$
وعلى متتالية مساعدة تلتقط مساهمة \(J_B(n)\) وحدها.
نعرّف
$$B_n=\sum_{j=0}^{n-1}\frac{2^{-j}}{n-j}.$$
وباستخدام التبديل \(k=n-j\) نحصل على الصيغة المكافئة
$$B_n=\frac{1}{2^n}\sum_{k=1}^{n}\frac{2^k}{k}.$$
الملاحظة الأساسية التي تستخدمها التطبيقات هي
$$J_B(n)=B_n.$$
وهذه هي نقطة التبسيط الحاسمة: بدل التعامل مع التعبير الأصلي القادم من اللعبة، يكفي تحليل مجموع واحد من المقلوبات بأوزان ثنائية.
الصيغة المحوّلة تكشف العلاقة مباشرة. إذ لدينا
$$B_n=\frac{1}{2^n}\sum_{k=1}^{n}\frac{2^k}{k},\qquad B_{n-1}=\frac{1}{2^{n-1}}\sum_{k=1}^{n-1}\frac{2^k}{k}.$$
نضرب المعادلة الثانية في \(1/2\)، فنحصل على
$$\frac{1}{2}B_{n-1}=\frac{1}{2^n}\sum_{k=1}^{n-1}\frac{2^k}{k}.$$
ثم نطرح، فيتبقى
$$B_n-\frac{1}{2}B_{n-1}=\frac{1}{2^n}\cdot\frac{2^n}{n}=\frac{1}{n},$$
ومن ثم
$$\boxed{B_n=\frac{1}{n}+\frac{1}{2}B_{n-1}}$$
مع القيمة الابتدائية \(B_1=1\). هذه العلاقة الرجوعية هي أساس الفحص الدقيق للقيم الصغيرة، وهي أيضًا المدخل إلى صيغة الجمع الكلية.
تستخدم التطبيقات كذلك الهوية
$$J_A(n)=B_n-\frac{H_n}{2^n}.$$
وبدمجها مع \(J_B(n)=B_n\) نحصل على
$$J_A(n)+J_B(n)=2B_n-\frac{H_n}{2^n}.$$
وبالتالي تصبح المسألة كلها
$$S(m)=2\sum_{n=1}^{m}B_n-\sum_{n=1}^{m}\frac{H_n}{2^n}.$$
من هذه اللحظة تختفي البنية الأصلية للمسألة، ولا يبقى إلا حساب كميات تحليلية معروفة.
لنعرّف
$$T_m=\sum_{n=1}^{m}B_n.$$
بجمع العلاقة \(B_n-\frac{1}{2}B_{n-1}=1/n\) من \(n=1\) إلى \(n=m\)، نحصل على
$$\sum_{n=1}^{m}B_n-\frac{1}{2}\sum_{n=1}^{m}B_{n-1}=H_m.$$
وبما أن \(B_0=0\)، فإن
$$\sum_{n=1}^{m}B_{n-1}=B_0+B_1+\cdots+B_{m-1}=T_m-B_m.$$
بالتعويض ينتج
$$T_m-\frac{1}{2}(T_m-B_m)=H_m,$$
ومنها
$$\boxed{T_m=2H_m-B_m.}$$
إذًا يختزل المجموع الكلي إلى
$$\boxed{S(m)=4H_m-2B_m-\sum_{n=1}^{m}\frac{H_n}{2^n}.}$$
للمجموع المتبقي صيغة كلاسيكية عبر الدالة المولدة. عندما يكون \(|x|<1\)، فإن
$$\sum_{n\ge 1}H_nx^n=\sum_{n\ge 1}\sum_{k=1}^{n}\frac{x^n}{k}=\sum_{k\ge 1}\frac{1}{k}\sum_{n\ge k}x^n=\frac{1}{1-x}\sum_{k\ge 1}\frac{x^k}{k}=-\frac{\log(1-x)}{1-x}.$$
وباختيار \(x=\tfrac12\) نحصل على
$$\sum_{n\ge 1}\frac{H_n}{2^n}=2\log 2.$$
وعندئذ يمكن كتابة
$$S(m)=4H_m-2B_m-2\log 2+R_m,$$
حيث الذيل المهمل هو
$$R_m=\sum_{n=m+1}^{\infty}\frac{H_n}{2^n}.$$
ومن إعادة ترتيب هذا الذيل نحصل على التقدير المفيد
$$R_m=\frac{H_m}{2^m}+2\sum_{k=m+1}^{\infty}\frac{1}{k2^k}\le \frac{1}{2^m}\left(H_m+\frac{2}{m+1}\right).$$
وعند \(m=123456789\) يكون هذا الخطأ أصغر بكثير جدًا من \(10^{-8}\)، لذلك لا يتغير التقريب النهائي إلى ثمانية أرقام عشرية إذا استبدلنا المجموع المنتهي بالثابت \(2\log 2\).
يُقرَّب العدد التوافقي بواسطة توسع Euler-Maclaurin:
$$H_m=\log m+\gamma+\frac{1}{2m}-\frac{1}{12m^2}+O\!\left(\frac{1}{m^4}\right),$$
حيث \(\gamma\) هو ثابت Euler-Mascheroni. وعند \(m=123456789\) تكون الحدود المهملة أدنى بكثير من الدقة المطلوبة.
أما \(B_m\)، فتقوم التطبيقات بحساب المجموع المبتور القصير
$$B_m\approx \sum_{j=0}^{200}\frac{2^{-j}}{m-j}.$$
والذيل المتروك يحقق
$$0\le \sum_{j=201}^{m-1}\frac{2^{-j}}{m-j}\le \sum_{j=201}^{\infty}2^{-j}=2^{-200},$$
ولذلك يكون الخطأ هنا مهملًا أيضًا. حساب الحالة الكبيرة يصبح إذًا سريعًا ومستقرًا عدديًا.
بدءًا من \(B_1=1\) واستخدام العلاقة \(B_n=\frac1n+\frac12B_{n-1}\)، نحصل على
$$B_2=1,\qquad B_3=\frac{5}{6},\qquad B_4=\frac{2}{3},\qquad B_5=\frac{8}{15},\qquad B_6=\frac{13}{30}.$$
وكذلك
$$H_6=1+\frac12+\frac13+\frac14+\frac15+\frac16=\frac{49}{20}.$$
إذن
$$J_B(6)=B_6=\frac{13}{30}=0.43333333\ldots$$
و
$$J_A(6)=B_6-\frac{H_6}{2^6}=\frac{13}{30}-\frac{49}{1280}=\frac{1517}{3840}=0.39505208\ldots$$
أما مجموع أول ست قيم من \(J_A(n)+J_B(n)\) فهو
$$S(6)=7.5893229166\ldots,$$
وبالتقريب نحصل على \(7.58932292\)، وهو نفس مقدار التحقق المذكور.
تستخدم التطبيقات في C++ وPython وJava الصيغة النهائية نفسها. فهي تقيم \(H_m\) باستخدام التوسع القصير لـ Euler-Maclaurin، وتحسب \(B_m\) بجمع أول 201 حد فقط من متسلسلة المقلوبات الموزونة بقوى \(2\)، ثم تستبدل المجموع التوافقي اللانهائي بالثابت \(2\log 2\)، وأخيرًا تعيد القيمة
$$4H_m-2B_m-2\log 2$$
بالدقة المطلوبة وهي ثمانية منازل عشرية.
وبذلك لا توجد أي حاجة إلى حلقة تمتد حتى \(m\). تظل العلاقة الرجوعية لـ \(B_n\) مفيدة لفهم البرهان والتحقق من الأمثلة الصغيرة، لكن حساب الإدخال الكبير نفسه يستخدم عددًا ثابتًا من العمليات الحسابية فقط.
مسار التقييم النهائي يحتاج إلى عدد ثابت من عمليات الفاصلة العائمة: بضعة حدود من تقريب العدد التوافقي، و201 حدًا لحساب \(B_m\)، وعددًا ثابتًا من اللوغاريتمات. لذلك يكون الزمن \(O(1)\) والذاكرة \(O(1)\). ولو أردنا حساب الأمثلة الصغيرة مباشرة من العلاقة الرجوعية فسيكون هذا المسار المساعد \(O(m)\)، لكنه ليس جزءًا من الحل النهائي للإدخال الكبير.