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.
The whole method is built around the observation that significant digits are encoded in the fractional part of a base-10 logarithm.
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.
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.
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.
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\).
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\).
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.$$
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\).
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.
Die Größe aus der Aufgabe lässt sich zu
$$D(n)=\frac{H_n}{2^n}, \qquad H_n=\sum_{k=1}^{n}\frac{1}{k},$$
vereinfachen, und gesucht sind die ersten sieben signifikanten Ziffern von \(D(123456789)\). Die Schwierigkeit ist hier numerisch: \(2^n\) ist riesig, \(D(n)\) extrem klein, und dennoch interessieren nur die führenden Ziffern. Deshalb berechnet die Lösung \(2^n\) nie direkt, sondern arbeitet mit Logarithmen, einer asymptotischen Formel für \(H_n\) und erhöhter Präzision bei der entscheidenden Subtraktion.
Die Kernidee lautet: Führende Ziffern stehen in der Nachkommastelle eines Zehnerlogarithmus.
Setze
$$L=\log_{10} D(n).$$
Schreibe \(L=a+f\) mit \(a=\lfloor L \rfloor\) und
$$f=L-\lfloor L \rfloor \in [0,1).$$
Dann gilt
$$D(n)=10^L=10^a\cdot 10^f.$$
Der Faktor \(10^a\) verschiebt nur das Dezimalkomma, während \(10^f\in[1,10)\) die Mantisse in wissenschaftlicher Schreibweise ist. Also erhält man die ersten sieben signifikanten Ziffern durch
$$\left\lfloor 10^{f+6} \right\rfloor.$$
Das Problem reduziert sich damit auf die präzise Berechnung der Nachkommastelle von \(L\).
Aus der geschlossenen Form folgt
$$L=\log_{10} H_n-n\log_{10} 2.$$
Der zweite Term dominiert numerisch, weil \(n=123456789\) groß ist, während \(\log_{10} H_n\) nur sehr langsam wächst. Die gesuchte Antwort hängt also an den unteren Stellen einer Subtraktion zwischen Größen sehr unterschiedlicher Skala. Genau dort entsteht bei naiver Fließkommarechnung Präzisionsverlust.
Für große \(n\) verwendet man die Euler-Maclaurin-Entwicklung
$$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}),$$
wobei \(\gamma\) die Euler-Mascheroni-Konstante ist. Für den tatsächlichen Eingabewert ist der abgeschnittene Rest so klein, dass er die ersten sieben signifikanten Ziffern nicht mehr verändern kann. Eine Implementierung besitzt zusätzlich einen direkten Summationszweig für kleinere \(n\), doch für die echte Aufgabe liegt man klar im asymptotischen Bereich.
Selbst mit gutem \(H_n\) muss noch
$$\log_{10} H_n-n\log_{10} 2$$
stabil ausgewertet werden. Die C++- und Java-Implementierungen speichern diese Größe als Summe aus Hauptteil und Korrekturteil und verwenden kompensierte Rechenoperationen, damit beim Bilden von \(n\log_{10} 2\) und bei der anschließenden Subtraktion keine wesentliche Information verloren geht. Die Python-Implementierung erreicht denselben Zweck mit hochpräziser Dezimalarithmetik. Danach wird der Nachkommateil wieder in das Intervall \([0,1)\) zurückgeführt, weil die kleine Korrektur ihn geringfügig unter \(0\) oder über \(1\) schieben kann.
Ist \(f\) bekannt, entstehen die führenden Ziffern aus
$$x=10^{f+6}.$$
Mathematisch ist die Antwort \(\lfloor x \rfloor\). Praktisch addieren die Implementierungen davor eine winzige positive Sicherheitsmarge, damit ein Wert wie \(3828124.9999999996\) nicht fälschlich nach unten abgeschnitten wird, wenn der wahre Wert \(3828125\) ist. Zusätzlich wird das Ergebnis bei \(9999999\) gedeckelt, denn \(10^f<10\).
Das Beispiel aus der Aufgabenstellung lässt sich exakt ausrechnen:
$$H_6=1+\frac12+\frac13+\frac14+\frac15+\frac16=\frac{49}{20}.$$
Also
$$D(6)=\frac{49/20}{2^6}=\frac{49}{1280}=0.03828125=3.828125\times 10^{-2}.$$
Die ersten sieben signifikanten Ziffern sind daher
$$3828125.$$
Die Logarithmusmethode liefert dasselbe: Für \(L=\log_{10}(0.03828125)\) ist \(f=L-\lfloor L \rfloor=\log_{10}(3.828125)\), und somit
$$10^{f+6}=3.828125\times 10^6=3828125.$$
Die C++-, Python- und Java-Implementierungen folgen alle derselben Pipeline. Zuerst wird \(D(n)=H_n/2^n\) in die logarithmische Form überführt. Dann wird \(H_n\) berechnet, \(\log_{10} H_n\) bestimmt, \(n\log_{10} 2\) subtrahiert, der Nachkommateil extrahiert und schließlich mit einer Zehnerpotenz in sieben führende Ziffern umgewandelt.
Der Unterschied liegt nur in der Präzisionsstrategie. Python benutzt einen hochpräzisen Dezimalkontext und wertet die asymptotische Reihe direkt aus. C++ und Java halten die empfindliche Differenz als zweikomponentige Fließkommazahl fest, was die relevanten Nachkommastellen besser schützt als ein einzelner double-Wert. Eine Implementierung besitzt außerdem einen direkten Summationspfad für kleinere Eingaben und prüft vor der eigentlichen Ausgabe das Beispiel \(n=6\).
Für den echten Zieleingabewert wird \(H_n\) mit einer festen Anzahl asymptotischer Terme ausgewertet, die Logarithmusarithmetik benötigt nur konstant viele Operationen, und auch die letzte Ziffernextraktion ist konstant. Daher betragen Laufzeit und Speicherverbrauch \(O(1)\). Wird der optionale direkte Summationszweig für kleine \(n\) benutzt, so kostet dieser \(O(n)\) Zeit und weiterhin \(O(1)\) Speicher.
Sorudaki nicelik
$$D(n)=\frac{H_n}{2^n}, \qquad H_n=\sum_{k=1}^{n}\frac{1}{k},$$
biçimine indirgenir ve amaç \(D(123456789)\) ifadesinin ilk yedi anlamlı basamağını bulmaktır. Zorluk kombinatoryal değil, sayısaldır: \(2^n\) olağanüstü büyüktür, \(D(n)\) çok küçüktür ve yine de yalnızca baştaki basamaklar istenir. Bu yüzden çözüm \(2^n\)'yi doğrudan üretmez; logaritmalar, harmonik sayı için keskin bir asimptotik açılım ve hassas çıkarma kullanır.
Yöntemin özü şudur: anlamlı basamaklar, 10 tabanındaki logaritmanın kesir kısmında saklıdır.
Şunu tanımlayalım:
$$L=\log_{10} D(n).$$
\(L=a+f\) olacak şekilde yazalım; burada \(a=\lfloor L \rfloor\) tam kısım ve
$$f=L-\lfloor L \rfloor \in [0,1)$$
kesir kısmıdır. Böylece
$$D(n)=10^L=10^a\cdot 10^f$$
olur. \(10^a\) yalnızca ondalık noktayı kaydırır, \(10^f\in[1,10)\) ise bilimsel gösterimdeki mantistir. Dolayısıyla ilk yedi anlamlı basamak
$$\left\lfloor 10^{f+6} \right\rfloor$$
ile elde edilir. Yani asıl iş, \(L\)'nin kesir kısmını güvenilir biçimde bulmaktır.
Kapalı formdan
$$L=\log_{10} H_n-n\log_{10} 2$$
elde edilir. Burada ikinci terim sayısal olarak baskındır; çünkü \(n=123456789\) çok büyüktür, buna karşılık \(\log_{10} H_n\) çok yavaş artar. Yani sonuç, farklı ölçeklerdeki iki niceliğin farkının en son basamaklarına bağlıdır. Sıradan kayan nokta aritmetiği tam bu noktada hassasiyet kaybedebilir.
Büyük \(n\) için harmonik sayı şu açılımla hesaplanır:
$$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}),$$
burada \(\gamma\) Euler-Mascheroni sabitidir. Hedef girdide kesilip atılan kuyruk o kadar küçüktür ki ilk yedi anlamlı basamağı değiştiremez. Uygulamalardan biri daha küçük \(n\) değerleri için doğrudan toplama dalı da içerir, ama gerçek giriş açıkça asimptotik bölgededir.
\(H_n\) bulunduktan sonra bile
$$\log_{10} H_n-n\log_{10} 2$$
ifadesi dikkatli hesaplanmalıdır. C++ ve Java uygulamaları bu duyarlı niceliği yüksek parça artı düşük düzeltme biçiminde saklar ve telafili toplama, çıkarma, çarpma işlemleriyle \(n\log_{10} 2\) hesaplanırken kritik kesir bilgisinin kaybolmasını önler. Python uygulaması ise aynı amacı yüksek hassasiyetli ondalık aritmetik ile gerçekleştirir. Çıkarmadan sonra kesir kısmı yeniden \([0,1)\) aralığına getirilir; çünkü küçük düzeltme onu biraz eksiye veya bire taşıyabilir.
\(f\) elde edilince baştaki basamaklar
$$x=10^{f+6}$$
ifadesinden gelir. İdeal cevap \(\lfloor x \rfloor\) değeridir. Pratikte uygulamalar, gerçek matematiksel sonuç \(3828125\) iken sayısal yuvarlama nedeniyle \(3828124.9999999996\) gibi bir değer oluşursa yanlışlıkla aşağı yuvarlanmaması için önce çok küçük pozitif bir güvenlik payı ekler. Ayrıca \(10^f<10\) olduğu için sonuç \(9999999\) üst sınırında tutulur.
Sorudaki küçük örnek tam olarak hesaplanabilir:
$$H_6=1+\frac12+\frac13+\frac14+\frac15+\frac16=\frac{49}{20}.$$
Dolayısıyla
$$D(6)=\frac{49/20}{2^6}=\frac{49}{1280}=0.03828125=3.828125\times 10^{-2}.$$
Böylece ilk yedi anlamlı basamak
$$3828125$$
olur. Logaritmalı yöntem de aynı sonuca ulaşır: \(L=\log_{10}(0.03828125)\) için \(f=L-\lfloor L \rfloor=\log_{10}(3.828125)\), dolayısıyla
$$10^{f+6}=3.828125\times 10^6=3828125.$$
C++, Python ve Java uygulamalarının hepsi aynı matematiksel akışı izler. Önce \(D(n)=H_n/2^n\) özdeşliğinden başlanır. Sonra \(H_n\) hesaplanır, \(\log_{10} H_n\) bulunur, bundan \(n\log_{10} 2\) çıkarılır, kesir kısmı alınır ve son olarak tek bir 10 tabanlı üs alma işlemiyle ilk yedi basamak üretilir.
Fark, hassasiyet yönetimindedir. Python uygulaması yüksek hassasiyetli bir ondalık bağlam kullanır ve asimptotik seriyi doğrudan değerlendirir. C++ ve Java uygulamaları ise duyarlı farkı iki bileşenli kayan nokta gösterimiyle tutar; bu yaklaşım tek bir double değerine göre çok daha güvenilir kesir bilgisi korur. Uygulamalardan biri ayrıca daha küçük girdiler için doğrudan harmonik toplam alma seçeneği içerir ve \(n=6\) örneğini kontrol ettikten sonra \(123456789\) sonucunu yazdırır.
Gerçek hedef girdi için harmonik sayı sabit sayıda asimptotik terimle hesaplanır, logaritmik aritmetik sabit sayıda işlem gerektirir ve son basamak çıkarımı da sabittir. Bu yüzden zaman karmaşıklığı \(O(1)\), bellek kullanımı \(O(1)\) olur. Daha küçük \(n\) için kullanılan isteğe bağlı doğrudan toplama yolu devreye girerse o dal \(O(n)\) zamanda çalışır ve yine \(O(1)\) bellek kullanır.
La cantidad de la que parte el problema se reduce a
$$D(n)=\frac{H_n}{2^n}, \qquad H_n=\sum_{k=1}^{n}\frac{1}{k},$$
y hay que obtener las primeras siete cifras significativas de \(D(123456789)\). La dificultad es numérica: \(2^n\) es gigantesco, \(D(n)\) es diminuto y, aun así, solo interesan las cifras iniciales. Por eso la solución no construye \(2^n\) de forma explícita. Trabaja con logaritmos, con una expansión asintótica precisa del número armónico y con un control extra de la precisión en la resta final.
La idea central es que las cifras significativas quedan determinadas por la parte fraccionaria de un logaritmo en base 10.
Definimos
$$L=\log_{10} D(n).$$
Escribimos \(L=a+f\), con \(a=\lfloor L \rfloor\) y
$$f=L-\lfloor L \rfloor \in [0,1).$$
Entonces
$$D(n)=10^L=10^a\cdot 10^f.$$
El factor \(10^a\) solo mueve la coma decimal, mientras que \(10^f\in[1,10)\) es la mantisa en notación científica. Por tanto, las primeras siete cifras significativas vienen dadas por
$$\left\lfloor 10^{f+6} \right\rfloor.$$
El problema queda reducido a calcular con mucha exactitud la parte fraccionaria de \(L\).
A partir de la forma cerrada,
$$L=\log_{10} H_n-n\log_{10} 2.$$
El segundo término domina numéricamente porque \(n=123456789\) es enorme, mientras que \(\log_{10} H_n\) crece muy despacio. Eso significa que la respuesta depende de las cifras bajas de una resta entre cantidades de escalas muy distintas. Si se usa aritmética de coma flotante de manera ingenua, justamente ahí se pierde precisión.
Para \(n\) grande se usa la expansión de Euler-Maclaurin
$$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}),$$
donde \(\gamma\) es la constante de Euler-Mascheroni. Para la entrada objetivo, el resto omitido es tan pequeño que no puede alterar las primeras siete cifras significativas. Una de las implementaciones también conserva una vía de suma directa para valores moderados de \(n\), pero la entrada real del problema está claramente en el régimen asintótico.
Incluso con un buen valor de \(H_n\), todavía hay que evaluar de forma estable
$$\log_{10} H_n-n\log_{10} 2.$$
Las implementaciones en C++ y Java guardan esta cantidad como una parte alta más una corrección baja y aplican operaciones compensadas para que no se pierda la información fraccionaria importante al formar \(n\log_{10} 2\) y restarla. La implementación en Python logra el mismo objetivo usando aritmética decimal de alta precisión. Después de la resta, la parte fraccionaria se normaliza otra vez en \([0,1)\), porque la pequeña corrección puede empujarla ligeramente por debajo de \(0\) o por encima de \(1\).
Una vez obtenido \(f\), las cifras iniciales salen de
$$x=10^{f+6}.$$
En teoría la respuesta es \(\lfloor x \rfloor\). En la práctica, las implementaciones añaden antes un margen positivo diminuto para que un valor como \(3828124.9999999996\) no se redondee hacia abajo por error cuando el resultado matemático verdadero es \(3828125\). Además se impone el tope \(9999999\), porque \(10^f<10\).
El ejemplo del enunciado se puede resolver exactamente:
$$H_6=1+\frac12+\frac13+\frac14+\frac15+\frac16=\frac{49}{20}.$$
Así,
$$D(6)=\frac{49/20}{2^6}=\frac{49}{1280}=0.03828125=3.828125\times 10^{-2}.$$
Por lo tanto, las primeras siete cifras significativas son
$$3828125.$$
El método logarítmico da lo mismo: si \(L=\log_{10}(0.03828125)\), entonces \(f=L-\lfloor L \rfloor=\log_{10}(3.828125)\), y por consiguiente
$$10^{f+6}=3.828125\times 10^6=3828125.$$
Las implementaciones en C++, Python y Java siguen exactamente la misma cadena matemática. Empiezan con \(D(n)=H_n/2^n\), calculan \(H_n\), obtienen \(\log_{10} H_n\), restan \(n\log_{10} 2\), extraen la parte fraccionaria y la convierten en siete cifras iniciales con una sola potencia de 10.
La diferencia está en la estrategia de precisión. Python usa un contexto decimal de alta precisión y evalúa directamente la serie asintótica. C++ y Java representan la resta delicada mediante dos componentes enlazados de coma flotante, lo que protege mucho mejor la información fraccionaria que un único double. Una de las implementaciones también incluye una ruta de suma directa para valores pequeños y comprueba primero el ejemplo \(n=6\) antes de imprimir la respuesta para \(123456789\).
Para la entrada real, el número armónico se evalúa con un número fijo de términos asintóticos, la aritmética logarítmica usa un número fijo de operaciones y la extracción final de cifras también es constante. Por ello, el tiempo total es \(O(1)\) y la memoria es \(O(1)\). Si se activa la ruta opcional de suma directa para valores pequeños de \(n\), esa rama cuesta \(O(n)\) tiempo y sigue usando \(O(1)\) memoria.
题目中的目标量可以化简为
$$D(n)=\frac{H_n}{2^n}, \qquad H_n=\sum_{k=1}^{n}\frac{1}{k},$$
要求返回 \(D(123456789)\) 的前七位有效数字。难点不在组合推导，而在数值处理上：\(2^n\) 极其巨大，\(D(n)\) 极其微小，但我们只关心最前面的几位数字。于是实现不会直接构造 \(2^n\)，而是转到对数域中，用调和数的渐近展开和额外精度来稳定地提取首位数字。
整个方法的核心观察是：一个正数的有效数字由其十进制对数的小数部分决定。
设
$$L=\log_{10} D(n).$$
把 \(L\) 写成 \(L=a+f\)，其中 \(a=\lfloor L \rfloor\) 为整数部分，而
$$f=L-\lfloor L \rfloor \in [0,1)$$
为小数部分。于是
$$D(n)=10^L=10^a\cdot 10^f.$$
\(10^a\) 只负责移动小数点，真正决定科学记数法尾数的是 \(10^f\in[1,10)\)。因此前七位有效数字正是
$$\left\lfloor 10^{f+6} \right\rfloor.$$
这样一来，问题就从“直接求一个极小的数”转成了“精确求出一个对数的小数部分”。
由闭式表达式直接得到
$$L=\log_{10} H_n-n\log_{10} 2.$$
这里第二项在数值上远远占主导，因为 \(n=123456789\) 很大，而 \(\log_{10} H_n\) 的增长速度极慢。也就是说，最终答案依赖于两项相减之后留下的低位信息，而这些低位恰恰最容易在普通浮点计算中丢失。所以这一步必须格外小心。
对于很大的 \(n\)，调和数可以用 Euler-Maclaurin 公式展开为
$$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}),$$
其中 \(\gamma\) 是 Euler-Mascheroni 常数。对于题目的目标输入，截断后的余项小到几乎不可能影响前七位有效数字。某个实现还保留了一个针对较小 \(n\) 的直接求和分支，但对本题的真实输入而言，显然应当使用渐近公式。
即使已经有了足够精确的 \(H_n\)，仍然要稳定地计算
$$\log_{10} H_n-n\log_{10} 2.$$
C++ 和 Java 实现把这个敏感量表示成“高位部分 + 低位修正”的两段形式，并在加法、减法、乘法中使用补偿思想，让 \(n\log_{10} 2\) 的形成过程和最终相减过程尽量保留小数位信息。Python 实现则换了一条路，直接使用高精度十进制算术达到同样目的。完成减法后，还要把小数部分重新规范到 \([0,1)\) 中，因为低位修正可能把它轻微推到 \(0\) 以下或 \(1\) 以上。
得到 \(f\) 之后，只需计算
$$x=10^{f+6}$$
即可。理论上答案就是 \(\lfloor x \rfloor\)。但实现里会在取整前加上一个极小的正安全余量，避免真实结果本应是 \(3828125\)，却因为最后一位舍入噪声变成 \(3828124.9999999996\) 而被错误地下取整。由于 \(10^f<10\)，最后还会把结果限制在 \(9999999\) 以内。
题目给出的小例子可以完全精确地算出：
$$H_6=1+\frac12+\frac13+\frac14+\frac15+\frac16=\frac{49}{20}.$$
于是
$$D(6)=\frac{49/20}{2^6}=\frac{49}{1280}=0.03828125=3.828125\times 10^{-2}.$$
所以前七位有效数字就是
$$3828125.$$
如果用对数方法来做，也完全一致：令 \(L=\log_{10}(0.03828125)\)，则 \(f=L-\lfloor L \rfloor=\log_{10}(3.828125)\)，因此
$$10^{f+6}=3.828125\times 10^6=3828125.$$
C++、Python 和 Java 三个实现走的是同一条数学路线。它们都先利用 \(D(n)=H_n/2^n\) 这个恒等式，把问题转成对 \(H_n\) 的计算以及一个十进制对数差的计算；然后提取小数部分，再通过一次 \(10\) 的幂运算恢复出前七位有效数字。
三种实现的差别主要在精度策略上。Python 版本使用高精度十进制环境，直接评估渐近展开。C++ 和 Java 版本则把最关键的差值存成双分量浮点展开，从而比单个 double 更稳地保存低位信息。其中一个实现还保留了对较小输入的直接调和求和路径，并先检查 \(n=6\) 的样例值，然后再输出 \(123456789\) 的答案。
对题目的实际输入来说，调和数只需要固定个数的渐近项，后续的对数运算和首位提取也都只需固定个数的基本操作，因此总时间复杂度是 \(O(1)\)，空间复杂度也是 \(O(1)\)。如果启用针对较小 \(n\) 的直接求和分支，那么那一支的时间复杂度是 \(O(n)\)，空间仍然是 \(O(1)\)。
Величина из условия сводится к выражению
$$D(n)=\frac{H_n}{2^n}, \qquad H_n=\sum_{k=1}^{n}\frac{1}{k},$$
и требуется найти первые семь значащих цифр числа \(D(123456789)\). Основная трудность здесь численная: \(2^n\) колоссально велико, \(D(n)\) чрезвычайно мало, а нужны только начальные цифры. Поэтому решение не строит \(2^n\) напрямую, а переходит к логарифмам, использует асимптотику для гармонического числа и аккуратно контролирует точность в ключевой разности.
Ключевое наблюдение состоит в том, что значащие цифры задаются дробной частью десятичного логарифма.
Положим
$$L=\log_{10} D(n).$$
Представим \(L\) в виде \(L=a+f\), где \(a=\lfloor L \rfloor\), а
$$f=L-\lfloor L \rfloor \in [0,1).$$
Тогда
$$D(n)=10^L=10^a\cdot 10^f.$$
Множитель \(10^a\) только двигает десятичную точку, а \(10^f\in[1,10)\) есть мантисса в научной записи. Значит, первые семь значащих цифр равны
$$\left\lfloor 10^{f+6} \right\rfloor.$$
Итак, задача сводится к точному вычислению дробной части \(L\).
Из замкнутой формы сразу следует
$$L=\log_{10} H_n-n\log_{10} 2.$$
Второй член численно доминирует, поскольку \(n=123456789\) велико, а \(\log_{10} H_n\) растет очень медленно. Это означает, что ответ определяется низшими разрядами разности двух величин разного масштаба, а именно такие разряды легче всего теряются при наивной работе с плавающей точкой.
Для больших \(n\) используется разложение
$$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}),$$
где \(\gamma\) обозначает постоянную Эйлера-Маскерони. Для целевого входа отброшенный хвост настолько мал, что уже не может изменить первые семь значащих цифр. В одной из реализаций также сохранена прямая сумма для умеренных \(n\), но для реального значения из задачи нужен именно асимптотический путь.
Даже после точного вычисления \(H_n\) необходимо устойчиво найти
$$\log_{10} H_n-n\log_{10} 2.$$
Реализации на C++ и Java хранят эту чувствительную величину как сумму старшей и младшей частей и применяют компенсированные арифметические операции, чтобы при вычислении \(n\log_{10} 2\) и при последующем вычитании не потерять важную дробную информацию. Реализация на Python достигает того же эффекта за счет высокоточной десятичной арифметики. После вычитания дробную часть снова нормализуют в интервал \([0,1)\), потому что малая поправка может слегка вытолкнуть ее ниже нуля или выше единицы.
Когда найдено \(f\), искомые цифры получаются из выражения
$$x=10^{f+6}.$$
В идеале ответ равен \(\lfloor x \rfloor\). На практике реализации добавляют перед взятием пола очень маленький положительный запас, чтобы значение вроде \(3828124.9999999996\) не округлилось вниз ошибочно, если точный математический результат равен \(3828125\). Также вводится ограничение сверху \(9999999\), поскольку всегда \(10^f<10\).
Малый пример из условия легко вычисляется точно:
$$H_6=1+\frac12+\frac13+\frac14+\frac15+\frac16=\frac{49}{20}.$$
Следовательно,
$$D(6)=\frac{49/20}{2^6}=\frac{49}{1280}=0.03828125=3.828125\times 10^{-2}.$$
Первые семь значащих цифр равны
$$3828125.$$
Логарифмический способ дает тот же результат: если \(L=\log_{10}(0.03828125)\), то \(f=L-\lfloor L \rfloor=\log_{10}(3.828125)\), а значит
$$10^{f+6}=3.828125\times 10^6=3828125.$$
Реализации на C++, Python и Java проходят один и тот же математический маршрут. Сначала используется тождество \(D(n)=H_n/2^n\), затем вычисляется \(H_n\), находится \(\log_{10} H_n\), вычитается \(n\log_{10} 2\), выделяется дробная часть и одной степенью десяти восстанавливаются первые семь значащих цифр.
Различие состоит в способе контроля точности. Python использует высокоточную десятичную среду и напрямую вычисляет асимптотический ряд. C++ и Java представляют чувствительную разность в виде двух связанных компонентов с плавающей точкой, что лучше сохраняет низшие разряды, чем одинарное значение типа double. Одна из реализаций также содержит ветку прямого суммирования для небольших входов и сначала проверяет пример \(n=6\), а потом печатает результат для \(123456789\).
Для реального входа гармоническое число вычисляется по фиксированному числу асимптотических членов, логарифмическая арифметика требует фиксированного числа операций, и извлечение цифр тоже постоянно по времени. Поэтому общая сложность равна \(O(1)\), а память также \(O(1)\). Если используется дополнительная ветка прямого суммирования для малых \(n\), то она работает за \(O(n)\) времени и \(O(1)\) памяти.
الكمية المطلوبة في المسألة تختزل إلى
$$D(n)=\frac{H_n}{2^n}, \qquad H_n=\sum_{k=1}^{n}\frac{1}{k},$$
والمطلوب هو استخراج أول سبعة أرقام معنوية من \(D(123456789)\). الصعوبة هنا عددية بالدرجة الأولى: فالقيمة \(2^n\) هائلة جدًا، بينما \(D(n)\) صغيرة جدًا، ومع ذلك لا نهتم إلا بالأرقام الأولى فقط. لذلك لا تقوم الحلول ببناء \(2^n\) مباشرة، بل تعمل في فضاء اللوغاريتمات، وتستخدم تقريبًا تقاربيًا دقيقًا للعدد التوافقي، ثم تعالج الطرح الحساس بدقة إضافية.
الفكرة الأساسية هي أن الأرقام المعنوية لعدد موجب تحددها الكسور العشرية في لوغاريتمه العشري.
لنعرّف
$$L=\log_{10} D(n).$$
ونكتب \(L=a+f\)، حيث \(a=\lfloor L \rfloor\) هو الجزء الصحيح و
$$f=L-\lfloor L \rfloor \in [0,1)$$
هو الجزء الكسري. عندئذ
$$D(n)=10^L=10^a\cdot 10^f.$$
العامل \(10^a\) لا يفعل إلا تحريك الفاصلة العشرية، أما \(10^f\in[1,10)\) فهو المعامل في الصيغة العلمية. لذلك فإن أول سبعة أرقام معنوية تساوي
$$\left\lfloor 10^{f+6} \right\rfloor.$$
وهكذا تصبح المسألة كلها مسألة استخراج الجزء الكسري من \(L\) بدقة عالية.
من الصيغة المغلقة نحصل على
$$L=\log_{10} H_n-n\log_{10} 2.$$
الحد الثاني هو المسيطر عدديًا لأن \(n=123456789\) كبير جدًا، بينما \(\log_{10} H_n\) ينمو ببطء شديد. هذا يعني أن الجواب النهائي يعتمد على الخانات المنخفضة لفرق بين كميتين بمقياسين مختلفين جدًا، وهذه الخانات تحديدًا هي الأكثر عرضة للضياع في الحساب العادي بالفاصلة العائمة.
عندما يكون \(n\) كبيرًا، يستخدم الحل التوسع
$$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}),$$
حيث \(\gamma\) هو ثابت Euler-Mascheroni. وبالنسبة إلى قيمة الإدخال المطلوبة، فإن الحد المتبقي بعد القطع صغير إلى درجة لا يمكن معها أن يغيّر أول سبعة أرقام معنوية. إحدى التطبيقات تحتفظ أيضًا بمسار جمع مباشر للقيم الأصغر من \(n\)، لكن الإدخال الحقيقي في المسألة يقع بوضوح داخل المجال الذي يكفيه هذا التقريب التقاربي.
حتى بعد الحصول على \(H_n\) بدقة جيدة، يبقى علينا تقييم
$$\log_{10} H_n-n\log_{10} 2$$
بطريقة مستقرة. تطبيقا C++ و Java يخزنان هذه الكمية الحساسة على صورة جزء عالٍ مع تصحيح منخفض، ويستخدمان عمليات حسابية معوّضة حتى لا تضيع المعلومات الكسرية المهمة عند تكوين \(n\log_{10} 2\) ثم طرحه. أما تطبيق Python فيصل إلى الغرض نفسه عبر حساب عشري عالي الدقة. وبعد الطرح يعاد ضبط الجزء الكسري إلى المجال \([0,1)\)، لأن التصحيح الصغير قد يدفعه قليلًا تحت الصفر أو فوق الواحد.
بعد الحصول على \(f\)، تأتي الأرقام الأولى من
$$x=10^{f+6}.$$
نظريًا الجواب هو \(\lfloor x \rfloor\). عمليًا تضيف التطبيقات هامشًا موجبًا ضئيلًا قبل أخذ الجزء الصحيح حتى لا تهبط قيمة مثل \(3828124.9999999996\) إلى العدد الخاطئ إذا كانت القيمة الرياضية الصحيحة هي \(3828125\). كما يجري تقييد النتيجة من الأعلى عند \(9999999\)، لأن \(10^f<10\).
مثال البيان صغير بما يكفي للحساب الدقيق:
$$H_6=1+\frac12+\frac13+\frac14+\frac15+\frac16=\frac{49}{20}.$$
ومن ثم
$$D(6)=\frac{49/20}{2^6}=\frac{49}{1280}=0.03828125=3.828125\times 10^{-2}.$$
إذن أول سبعة أرقام معنوية هي
$$3828125.$$
والطريقة اللوغاريتمية تعطي النتيجة نفسها تمامًا: إذا كان \(L=\log_{10}(0.03828125)\)، فإن \(f=L-\lfloor L \rfloor=\log_{10}(3.828125)\)، وبالتالي
$$10^{f+6}=3.828125\times 10^6=3828125.$$
تتبع تطبيقات C++ و Python و Java المسار الرياضي نفسه. تبدأ جميعها من الهوية \(D(n)=H_n/2^n\)، ثم تحسب \(H_n\)، وتجد \(\log_{10} H_n\)، وتطرح \(n\log_{10} 2\)، ثم تستخرج الجزء الكسري، وأخيرًا تحوله إلى أول سبعة أرقام معنوية بواسطة قوة واحدة للعدد \(10\).
الاختلاف بين هذه التطبيقات يكمن في أسلوب التحكم في الدقة. نسخة Python تستخدم حسابًا عشريًا عالي الدقة وتقيّم السلسلة التقاربية مباشرة. أما نسختا C++ و Java فتمثلان الفرق الحساس بتمديد عائم ثنائي المكون، وهو ما يحافظ على الخانات الدنيا أفضل بكثير من قيمة double منفردة. إحدى التطبيقات تحتفظ كذلك بمسار جمع مباشر للمدخلات الأصغر، وتتحقق أولًا من مثال \(n=6\) قبل طباعة جواب \(123456789\).
بالنسبة إلى الإدخال الفعلي في المسألة، يُحسب العدد التوافقي بعدد ثابت من الحدود التقاربية، وتستخدم الحسابات اللوغاريتمية عددًا ثابتًا من العمليات، كما أن استخراج الأرقام في النهاية عمل ثابت أيضًا. لذلك يكون الزمن \(O(1)\) والذاكرة \(O(1)\). وإذا استُخدم المسار الاختياري للجمع المباشر من أجل قيم صغيرة لـ \(n\)، فإن ذلك الفرع يأخذ زمنًا \(O(n)\) مع ذاكرة \(O(1)\) كذلك.