Detailed mathematical approach

Problem Summary

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.

Mathematical Approach

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)\).

Step 1: Rewrite \(J_B(n)\) as a Simpler Series

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.

Step 2: Derive the First-Order Recurrence for \(B_n\)

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.

Step 3: Express \(J_A(n)+J_B(n)\) in Terms of \(B_n\) and \(H_n\)

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.

Step 4: Sum the Recurrence to Collapse \(\sum B_n\)

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}.}$

Step 5: Replace the Finite Harmonic Series by an Infinite One

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\).

Step 6: Evaluate \(H_m\) and \(B_m\) for Huge \(m\)

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.

Worked Example: \(n=6\)

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.

How the Code Works

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.

Complexity Analysis

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.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=567
2. Harmonic numbers: Wikipedia - Harmonic number
3. Euler-Maclaurin formula: Wikipedia - Euler-Maclaurin formula
4. Additional background on harmonic-number identities: MathWorld - Harmonic Number
5. Geometric series: Wikipedia - Geometric series