Detailed mathematical approach

Problem Summary

The quantity from the problem can be reduced to

$D(n)=\frac{H_n}{2^n}, \qquad H_n=\sum_{k=1}^{n}\frac{1}{k},$

and the task is to return the first seven significant digits of \(D(123456789)\). The main difficulty is numerical rather than combinatorial: \(2^n\) is unimaginably large, \(D(n)\) is tiny, and only the leading digits matter. So the solution never forms \(2^n\) directly. Instead it works with logarithms, a sharp asymptotic expansion for the harmonic number, and extra precision in the final subtraction.

Mathematical Approach

The whole method is built around the observation that significant digits are encoded in the fractional part of a base-10 logarithm.

Step 1: Turn Leading Digits into a Logarithm Problem

Let

$L=\log_{10} D(n).$

Write \(L=a+f\) where \(a=\lfloor L \rfloor\) is the integer part and

$f=L-\lfloor L \rfloor \in [0,1).$

Then

$D(n)=10^L=10^a\cdot 10^f.$

The factor \(10^a\) only shifts the decimal point, while \(10^f\in[1,10)\) is the significand in scientific notation. Therefore the first seven significant digits are

$\left\lfloor 10^{f+6} \right\rfloor.$

So the problem is reduced to computing the fractional part of \(L\) accurately.

Step 2: Express \(L\) Using the Harmonic Number

From the closed form,

$L=\log_{10} H_n-n\log_{10} 2.$

The second term is easy in principle, but it is numerically dominant because \(n=123456789\) is large. The first term grows only like \(\log \log n\). That means the final answer depends on the low-order digits of a subtraction between quantities of very different scales, so ordinary floating-point arithmetic must be handled carefully.

Step 3: Approximate \(H_n\) with Euler-Maclaurin

For large \(n\), the harmonic number is approximated by the Euler-Maclaurin expansion

$H_n=\ln n+\gamma+\frac{1}{2n}-\frac{1}{12n^2}+\frac{1}{120n^4}-\frac{1}{252n^6}+\frac{1}{240n^8}-\frac{5}{660n^{10}}+O(n^{-12}),$

where \(\gamma\) is the Euler-Mascheroni constant. For the target input, the neglected tail is astronomically small and cannot affect the first seven significant digits. One implementation also keeps a direct summation branch for modest \(n\), but the actual Project Euler input is far into the asymptotic regime.

Step 4: Preserve the Fractional Part During the Critical Subtraction

Once \(H_n\) is known, we still need

$\log_{10} H_n-n\log_{10} 2.$

The C++ and Java implementations store the important quantity as a high part plus a low correction and carry out compensated addition, subtraction, and multiplication so the fractional information is not lost when \(n\log_{10} 2\) is formed. The Python implementation reaches the same goal with high-precision decimal arithmetic. After the subtraction, the fractional part is normalized back into \([0,1)\), because the small correction term can move it slightly below \(0\) or above \(1\).

Step 5: Convert the Fractional Part Back to Digits

After obtaining \(f\), the leading digits come from

$x=10^{f+6}.$

Ideally the answer is \(\lfloor x \rfloor\). In practice, the implementations add a tiny positive safety margin before flooring so that a value such as \(3828124.9999999996\) is not rounded down incorrectly when the true mathematical result is \(3828125\). The result is also capped at \(9999999\), because \(10^f<10\).

Worked Example: \(n=6\)

The statement example is small enough to do exactly:

$H_6=1+\frac12+\frac13+\frac14+\frac15+\frac16=\frac{49}{20}.$

Hence

$D(6)=\frac{49/20}{2^6}=\frac{49}{1280}=0.03828125=3.828125\times 10^{-2}.$

So the first seven significant digits are plainly

$3828125.$

The logarithmic method gives the same result: if \(L=\log_{10}(0.03828125)\), then \(f=L-\lfloor L \rfloor=\log_{10}(3.828125)\), and therefore

$10^{f+6}=3.828125\times 10^6=3828125.$

How the Code Works

The C++, Python, and Java implementations all follow the same mathematical pipeline. They start from \(D(n)=H_n/2^n\), evaluate \(H_n\), compute \(\log_{10} H_n\), subtract \(n\log_{10} 2\), extract the fractional part, and then turn that fraction into seven leading digits with one final power of ten.

The difference is in the precision strategy. The Python implementation uses a high-precision decimal context and evaluates the asymptotic series directly. The C++ and Java implementations treat the critical logarithmic subtraction more carefully by representing the value as two linked floating-point components, which keeps more reliable fractional information than a single double would. One implementation also includes a direct harmonic summation path for smaller inputs and checks the sample \(n=6\) before printing the answer for \(123456789\).

Complexity Analysis

For the actual target input, the harmonic number is evaluated from a fixed number of asymptotic terms, the logarithmic arithmetic uses a fixed number of operations, and the final digit extraction is constant work. So the running time is \(O(1)\) and the memory usage is \(O(1)\). If the optional direct summation path is used for smaller \(n\), that branch takes \(O(n)\) time and still uses \(O(1)\) memory.

Footnotes and References

1. Problem page: Project Euler 568
2. Harmonic numbers: Wikipedia - Harmonic number
3. Euler-Maclaurin formula: Wikipedia - Euler-Maclaurin formula
4. Common logarithm: Wikipedia - Common logarithm
5. Euler-Mascheroni constant: Wikipedia - Euler-Mascheroni constant
6. Double-double arithmetic overview: Wikipedia - Double-double arithmetic