We consider successful search in a sorted array of \(n\) distinct keys, where the target key is chosen uniformly from those \(n\) keys. Two search rules are compared:
$$B(n)=\text{expected comparisons when each recursive step probes the midpoint},$$
$$R(n)=\text{expected comparisons when each recursive step chooses its pivot uniformly at random}.$$
The problem asks for the difference \(R(n)-B(n)\) at \(n=10^{10}\). A direct simulation would be pointless, so the solution derives closed forms for both expectations and evaluates them numerically.
Both expectations come from the shape of the search tree induced by the rule used at each step. The midpoint rule produces a nearly complete binary tree, while the random-pivot rule leads to the same average successful-search cost as a random binary search tree.
Let \(h=\lfloor \log_2 n \rfloor\). Then the first \(h\) levels of the induced decision tree contain
$$1+2+\cdots+2^{h-1}=2^h-1$$
keys. Write
$$r=n-(2^h-1),\qquad 1\le r\le 2^h.$$
All levels \(0,1,\dots,h-1\) are full, and the remaining \(r\) keys sit on depth \(h\). A key at depth \(d\) needs \(d+1\) comparisons, so the total number of comparisons over all \(n\) possible targets is
$$S_B(n)=\sum_{d=0}^{h-1}(d+1)2^d+(h+1)r.$$
Using the finite-sum identity
$$\sum_{d=0}^{h-1}(d+1)2^d=(h-1)2^h+1,$$
we obtain
$$S_B(n)=(h+1)n-2^{h+1}+(h+2),$$
hence
$$\boxed{B(n)=\frac{S_B(n)}{n}=(h+1)-\frac{2^{h+1}-(h+2)}{n}.}$$
For the randomized rule, let the current pivot have rank \(k\in\{1,\dots,n\}\), chosen uniformly, and let the target have rank \(t\in\{1,\dots,n\}\), also uniform. One comparison is paid immediately.
If \(t=k\), the search stops. If \(t<k\), the next subproblem has size \(k-1\). If \(t>k\), the next subproblem has size \(n-k\). Averaging over all \(n^2\) pairs \((t,k)\) gives
$$R(n)=1+\frac{1}{n^2}\sum_{k=1}^{n}\left((k-1)R(k-1)+(n-k)R(n-k)\right).$$
Equal subproblem sizes appear symmetrically on the left and on the right, so this simplifies to
$$\boxed{R(n)=1+\frac{2}{n^2}\sum_{i=1}^{n-1} i\,R(i).}$$
This is exactly the same recurrence as the average successful-search cost in a random binary search tree.
Multiply the recurrence by \(n^2\):
$$n^2R(n)=n^2+2\sum_{i=1}^{n-1} i\,R(i).$$
Write the same formula for \(n-1\), subtract, and rearrange:
$$\frac{nR(n)}{n+1}=\frac{(n-1)R(n-1)}{n}+\frac{2n-1}{n(n+1)}.$$
Now define
$$A_n=\frac{nR(n)}{n+1}.$$
Then
$$A_n=A_{n-1}+\frac{2n-1}{n(n+1)}=A_{n-1}-\frac{1}{n}+\frac{3}{n+1}.$$
Since \(R(1)=1\), we have \(A_1=\frac12\). Telescoping from \(2\) to \(n\) yields
$$A_n=\frac12+\sum_{k=2}^{n}\left(-\frac{1}{k}+\frac{3}{k+1}\right)=2H_n+\frac{3}{n+1}-3,$$
where
$$H_n=\sum_{k=1}^{n}\frac1k$$
is the \(n\)-th harmonic number. Substituting back gives the closed form
$$\boxed{R(n)=2\frac{n+1}{n}H_n-3.}$$
For the actual target size, computing \(H_n\) term by term is unnecessary. The implementation uses the Euler-Maclaurin expansion
$$H_n=\log n+\gamma+\frac{1}{2n}-\frac{1}{12n^2}+\frac{1}{120n^4}+O(n^{-6}),$$
where \(\gamma\) is the Euler-Mascheroni constant. At \(n=10^{10}\), the omitted terms are far smaller than the requested eight decimal places, so the approximation is more than sufficient.
The final quantity is therefore
$$\boxed{\Delta(n)=R(n)-B(n)=2\frac{n+1}{n}H_n-3-\left((h+1)-\frac{2^{h+1}-(h+2)}{n}\right),\qquad h=\lfloor\log_2 n\rfloor.}$$
Here \(h=\lfloor\log_2 6\rfloor=2\) and \(r=6-(2^2-1)=3\). The deterministic search tree has one key at depth \(0\), two keys at depth \(1\), and three keys at depth \(2\). Hence
$$S_B(6)=1\cdot1+2\cdot2+3\cdot3=14,\qquad B(6)=\frac{14}{6}=\frac73=2.333333\ldots$$
For the randomized rule,
$$H_6=1+\frac12+\frac13+\frac14+\frac15+\frac16=\frac{49}{20},$$
so
$$R(6)=2\cdot\frac76\cdot\frac{49}{20}-3=\frac{163}{60}=2.716666\ldots$$
Therefore
$$R(6)-B(6)=\frac{163}{60}-\frac73=\frac{23}{60}=0.383333\ldots,$$
which matches the checkpoint used by the implementation.
The C++, Python, and Java implementations follow the same numerical plan. First, they evaluate \(B(n)\) directly from the closed form, obtaining \(\lfloor\log_2 n\rfloor\) with integer bit-length logic instead of recursive simulation.
Next, they evaluate \(H_n\). For \(n\le 10^6\), the harmonic number is summed exactly as \(\sum_{k=1}^{n}1/k\), which is useful for small checkpoints and keeps the formula accurate on small inputs. For larger \(n\), they switch to the asymptotic series above and use the Euler-Mascheroni constant explicitly.
With \(H_n\) available, they compute \(R(n)=2\frac{n+1}{n}H_n-3\), subtract \(B(n)\), and print the result with eight digits after the decimal point. The C++ implementation also verifies the \(n=6\) checkpoint before evaluating the main case.
The implementation is piecewise. On the exact harmonic-sum branch, the running time is \(O(n)\) and the memory usage is \(O(1)\). On the asymptotic branch, which is the one used for the actual input \(n=10^{10}\), both time and memory are \(O(1)\). In practice the Project Euler instance is handled by a constant amount of floating-point arithmetic.
Betrachtet wird die erfolgreiche Suche in einem sortierten Feld mit \(n\) verschiedenen Schlüsseln, wobei das gesuchte Element gleichverteilt aus diesen \(n\) Schlüsseln gewählt wird. Verglichen werden zwei Suchregeln:
$$B(n)=\text{erwartete Anzahl von Vergleichen, wenn immer das mittlere Element geprüft wird},$$
$$R(n)=\text{erwartete Anzahl von Vergleichen, wenn der Pivot in jedem Schritt gleichverteilt zufällig gewählt wird}.$$
Gesucht ist die Differenz \(R(n)-B(n)\) für \(n=10^{10}\). Eine direkte Simulation wäre nutzlos, daher leitet die Lösung für beide Erwartungswerte geschlossene Formeln her und wertet sie numerisch aus.
Beide Erwartungswerte ergeben sich aus der Form des Suchbaums, den die jeweilige Regel erzeugt. Die Mittelpunktsregel liefert einen fast vollständigen Binärbaum, während die Zufallsregel zum gleichen mittleren Aufwand einer erfolgreichen Suche in einem zufälligen binären Suchbaum führt.
Sei \(h=\lfloor \log_2 n \rfloor\). Dann enthalten die ersten \(h\) Ebenen des Entscheidungsbaums
$$1+2+\cdots+2^{h-1}=2^h-1$$
Schlüssel. Schreibe
$$r=n-(2^h-1),\qquad 1\le r\le 2^h.$$
Alle Ebenen \(0,1,\dots,h-1\) sind vollständig, und die restlichen \(r\) Schlüssel liegen in Tiefe \(h\). Ein Schlüssel in Tiefe \(d\) benötigt \(d+1\) Vergleiche, also ist die Gesamtzahl der Vergleiche über alle \(n\) möglichen Suchziele
$$S_B(n)=\sum_{d=0}^{h-1}(d+1)2^d+(h+1)r.$$
Mit der Summenformel
$$\sum_{d=0}^{h-1}(d+1)2^d=(h-1)2^h+1$$
folgt
$$S_B(n)=(h+1)n-2^{h+1}+(h+2),$$
also
$$\boxed{B(n)=\frac{S_B(n)}{n}=(h+1)-\frac{2^{h+1}-(h+2)}{n}.}$$
Bei der Zufallsregel habe der aktuelle Pivot Rang \(k\in\{1,\dots,n\}\), gleichverteilt gewählt, und das Suchziel Rang \(t\in\{1,\dots,n\}\), ebenfalls gleichverteilt. Sofort fällt genau ein Vergleich an.
Ist \(t=k\), endet die Suche. Für \(t<k\) hat das nächste Teilproblem Größe \(k-1\). Für \(t>k\) hat es Größe \(n-k\). Durch Mittelung über alle \(n^2\) Paare \((t,k)\) erhält man
$$R(n)=1+\frac{1}{n^2}\sum_{k=1}^{n}\left((k-1)R(k-1)+(n-k)R(n-k)\right).$$
Gleiche Teilproblemgrößen treten links und rechts symmetrisch auf, daher vereinfacht sich das zu
$$\boxed{R(n)=1+\frac{2}{n^2}\sum_{i=1}^{n-1} i\,R(i).}$$
Das ist genau dieselbe Rekursion wie für die mittleren Kosten einer erfolgreichen Suche in einem zufälligen binären Suchbaum.
Multipliziere die Rekursion mit \(n^2\):
$$n^2R(n)=n^2+2\sum_{i=1}^{n-1} i\,R(i).$$
Schreibt man dieselbe Formel für \(n-1\), subtrahiert und ordnet um, dann folgt
$$\frac{nR(n)}{n+1}=\frac{(n-1)R(n-1)}{n}+\frac{2n-1}{n(n+1)}.$$
Nun definiere
$$A_n=\frac{nR(n)}{n+1}.$$
Dann gilt
$$A_n=A_{n-1}+\frac{2n-1}{n(n+1)}=A_{n-1}-\frac{1}{n}+\frac{3}{n+1}.$$
Wegen \(R(1)=1\) ist \(A_1=\frac12\). Durch Teleskopieren von \(2\) bis \(n\) erhält man
$$A_n=\frac12+\sum_{k=2}^{n}\left(-\frac{1}{k}+\frac{3}{k+1}\right)=2H_n+\frac{3}{n+1}-3,$$
wobei
$$H_n=\sum_{k=1}^{n}\frac1k$$
die \(n\)-te harmonische Zahl ist. Rücksubstitution liefert die geschlossene Form
$$\boxed{R(n)=2\frac{n+1}{n}H_n-3.}$$
Für die eigentliche Zielgröße ist eine direkte Summation von \(H_n\) unnötig. Die Implementierung verwendet die Euler-Maclaurin-Entwicklung
$$H_n=\log n+\gamma+\frac{1}{2n}-\frac{1}{12n^2}+\frac{1}{120n^4}+O(n^{-6}),$$
wobei \(\gamma\) die Euler-Mascheroni-Konstante ist. Für \(n=10^{10}\) liegen die ausgelassenen Terme weit unterhalb der geforderten acht Nachkommastellen, also ist diese Näherung mehr als ausreichend.
Damit ist die Endgröße
$$\boxed{\Delta(n)=R(n)-B(n)=2\frac{n+1}{n}H_n-3-\left((h+1)-\frac{2^{h+1}-(h+2)}{n}\right),\qquad h=\lfloor\log_2 n\rfloor.}$$
Hier ist \(h=\lfloor\log_2 6\rfloor=2\) und \(r=6-(2^2-1)=3\). Der deterministische Suchbaum besitzt einen Schlüssel in Tiefe \(0\), zwei Schlüssel in Tiefe \(1\) und drei Schlüssel in Tiefe \(2\). Also
$$S_B(6)=1\cdot1+2\cdot2+3\cdot3=14,\qquad B(6)=\frac{14}{6}=\frac73=2.333333\ldots$$
Für die Zufallsregel gilt
$$H_6=1+\frac12+\frac13+\frac14+\frac15+\frac16=\frac{49}{20},$$
also
$$R(6)=2\cdot\frac76\cdot\frac{49}{20}-3=\frac{163}{60}=2.716666\ldots$$
Damit
$$R(6)-B(6)=\frac{163}{60}-\frac73=\frac{23}{60}=0.383333\ldots,$$
genau passend zum Kontrollwert der Implementierung.
Die C++-, Python- und Java-Implementierungen folgen demselben numerischen Plan. Zuerst wird \(B(n)\) direkt aus der geschlossenen Formel berechnet; \(\lfloor\log_2 n\rfloor\) wird dabei über Bitlänge beziehungsweise führende Nullbits bestimmt und nicht durch rekursive Simulation.
Danach wird \(H_n\) ausgewertet. Für \(n\le 10^6\) summiert die Implementierung die harmonische Zahl exakt als \(\sum_{k=1}^{n}1/k\). Das ist für kleine Kontrollfälle nützlich und hält die Formel auf kleinen Eingaben exakt. Für größere \(n\) wird auf die asymptotische Reihe mit der Euler-Mascheroni-Konstante umgeschaltet.
Mit \(H_n\) verfügbar berechnet die Implementierung \(R(n)=2\frac{n+1}{n}H_n-3\), zieht \(B(n)\) ab und formatiert das Ergebnis mit acht Nachkommastellen. Die C++-Version prüft zusätzlich vor dem Hauptfall noch den Kontrollwert bei \(n=6\).
Die Implementierung arbeitet stückweise. Im exakten Zweig für die harmonische Summe beträgt die Laufzeit \(O(n)\) und der Speicherbedarf \(O(1)\). Im asymptotischen Zweig, der für die eigentliche Eingabe \(n=10^{10}\) verwendet wird, sind sowohl Laufzeit als auch Speicher \(O(1)\). Praktisch besteht die Project-Euler-Berechnung also nur aus einer konstanten Anzahl von Gleitkommaoperationen.
Birbirinden farklı \(n\) anahtar içeren sıralı bir dizide, aranan anahtarın bu \(n\) anahtar arasından eşit olasılıkla seçildiğini düşünelim. İki arama kuralı karşılaştırılıyor:
$$B(n)=\text{her adımda orta elemanı deneyen deterministik aramanın beklenen karşılaştırma sayısı},$$
$$R(n)=\text{her adımda pivotu eşit olasılıkla rastgele seçen aramanın beklenen karşılaştırma sayısı}.$$
İstenen değer \(n=10^{10}\) için \(R(n)-B(n)\) farkıdır. Doğrudan benzetim verimsiz olacağı için çözüm her iki beklenti için kapalı form çıkarır ve bunları sayısal olarak değerlendirir.
Her iki beklenti de, seçilen kurala göre oluşan arama ağacının biçiminden gelir. Orta eleman kuralı neredeyse tam bir ikili ağaç üretir; rastgele pivot kuralı ise rastgele bir ikili arama ağacındaki başarılı aramanın ortalama maliyetiyle aynı ifadeye ulaşır.
\(h=\lfloor \log_2 n \rfloor\) olsun. O zaman karar ağacının ilk \(h\) seviyesi
$$1+2+\cdots+2^{h-1}=2^h-1$$
adet anahtar içerir. Şimdi
$$r=n-(2^h-1),\qquad 1\le r\le 2^h$$
yazalım. \(0,1,\dots,h-1\) seviyeleri tamamen doludur; kalan \(r\) anahtar derinlik \(h\)'dedir. Derinliği \(d\) olan bir anahtar \(d+1\) karşılaştırma gerektirdiğinden, tüm \(n\) olası hedef için toplam karşılaştırma sayısı
$$S_B(n)=\sum_{d=0}^{h-1}(d+1)2^d+(h+1)r$$
olur. Sonlu toplam özdeşliği
$$\sum_{d=0}^{h-1}(d+1)2^d=(h-1)2^h+1$$
kullanılırsa
$$S_B(n)=(h+1)n-2^{h+1}+(h+2)$$
elde edilir; dolayısıyla
$$\boxed{B(n)=\frac{S_B(n)}{n}=(h+1)-\frac{2^{h+1}-(h+2)}{n}.}$$
Rastgele kuralda mevcut pivotun sırası eşit olasılıkla seçilen \(k\in\{1,\dots,n\}\), hedefin sırası ise yine eşit olasılıkla seçilen \(t\in\{1,\dots,n\}\) olsun. İlk adımda her zaman bir karşılaştırma yapılır.
\(t=k\) ise arama biter. \(t<k\) ise sonraki alt problem boyutu \(k-1\) olur. \(t>k\) ise alt problem boyutu \(n-k\) olur. Tüm \(n^2\) adet \((t,k)\) çifti üzerinde ortalama alırsak
$$R(n)=1+\frac{1}{n^2}\sum_{k=1}^{n}\left((k-1)R(k-1)+(n-k)R(n-k)\right)$$
sonucuna ulaşırız. Eşit boyuttaki alt problemler sağda ve solda simetrik geldiği için bu ifade
$$\boxed{R(n)=1+\frac{2}{n^2}\sum_{i=1}^{n-1} i\,R(i)}$$
şekline sadeleşir. Bu, rastgele bir ikili arama ağacında başarılı aramanın ortalama maliyetiyle aynı yineleme bağıntısıdır.
Bağıntıyı \(n^2\) ile çarpalım:
$$n^2R(n)=n^2+2\sum_{i=1}^{n-1} i\,R(i).$$
Aynı ifadeyi \(n-1\) için de yazıp çıkarınca ve düzenleyince
$$\frac{nR(n)}{n+1}=\frac{(n-1)R(n-1)}{n}+\frac{2n-1}{n(n+1)}$$
elde edilir. Şimdi
$$A_n=\frac{nR(n)}{n+1}$$
tanımını yapalım. O zaman
$$A_n=A_{n-1}+\frac{2n-1}{n(n+1)}=A_{n-1}-\frac{1}{n}+\frac{3}{n+1}.$$
\(R(1)=1\) olduğundan \(A_1=\frac12\) olur. \(2\)'den \(n\)'e kadar teleskopik toplayınca
$$A_n=\frac12+\sum_{k=2}^{n}\left(-\frac{1}{k}+\frac{3}{k+1}\right)=2H_n+\frac{3}{n+1}-3,$$
burada
$$H_n=\sum_{k=1}^{n}\frac1k$$
\(n\). harmonik sayıdır. Geri yerine koyunca kapalı form
$$\boxed{R(n)=2\frac{n+1}{n}H_n-3}$$
çıkar.
Gerçek hedef boyutta \(H_n\)'yi terim terim toplamak gereksizdir. Uygulama Euler-Maclaurin açılımını kullanır:
$$H_n=\log n+\gamma+\frac{1}{2n}-\frac{1}{12n^2}+\frac{1}{120n^4}+O(n^{-6}),$$
burada \(\gamma\) Euler-Mascheroni sabitidir. \(n=10^{10}\) için ihmal edilen terimler istenen sekiz ondalık basamağın çok altındadır; dolayısıyla yaklaşım fazlasıyla yeterlidir.
Sonuçta hesaplanan nicelik
$$\boxed{\Delta(n)=R(n)-B(n)=2\frac{n+1}{n}H_n-3-\left((h+1)-\frac{2^{h+1}-(h+2)}{n}\right),\qquad h=\lfloor\log_2 n\rfloor}$$
olur.
Burada \(h=\lfloor\log_2 6\rfloor=2\) ve \(r=6-(2^2-1)=3\) olur. Deterministik arama ağacında derinlik \(0\)'da bir, derinlik \(1\)'de iki, derinlik \(2\)'de üç anahtar vardır. Bu yüzden
$$S_B(6)=1\cdot1+2\cdot2+3\cdot3=14,\qquad B(6)=\frac{14}{6}=\frac73=2.333333\ldots$$
Rastgele kural için
$$H_6=1+\frac12+\frac13+\frac14+\frac15+\frac16=\frac{49}{20}$$
olduğundan
$$R(6)=2\cdot\frac76\cdot\frac{49}{20}-3=\frac{163}{60}=2.716666\ldots$$
ve dolayısıyla
$$R(6)-B(6)=\frac{163}{60}-\frac73=\frac{23}{60}=0.383333\ldots,$$
ki bu da uygulamadaki kontrol değeriyle aynıdır.
C++, Python ve Java uygulamaları aynı sayısal yolu izler. Önce \(B(n)\) kapalı formdan doğrudan hesaplanır; \(\lfloor\log_2 n\rfloor\) değeri özyinelemeli arama yerine tam sayı bit uzunluğu mantığıyla bulunur.
Ardından \(H_n\) hesaplanır. \(n\le 10^6\) için harmonik sayı tam olarak \(\sum_{k=1}^{n}1/k\) biçiminde toplanır. Bu, küçük kontrol örnekleri için yararlıdır ve küçük girişlerde formülü tam tutar. Daha büyük \(n\) için Euler-Mascheroni sabitini içeren asimptotik seriye geçilir.
\(H_n\) elde edilince uygulama \(R(n)=2\frac{n+1}{n}H_n-3\) hesabını yapar, bundan \(B(n)\)'yi çıkarır ve sonucu virgülden sonra sekiz basamakla yazar. C++ sürümü ana hesaplamadan önce \(n=6\) kontrolünü de doğrular.
Uygulama iki parçalıdır. Harmonik toplamın tam hesaplandığı dalda zaman karmaşıklığı \(O(n)\), bellek kullanımı \(O(1)\)'dir. Asimptotik dalda ise, ki gerçek girdi \(n=10^{10}\) için kullanılan yol budur, hem zaman hem bellek \(O(1)\)'dir. Pratikte Project Euler örneği sabit sayıda kayan nokta işlemiyle çözülür.
Se estudia la búsqueda exitosa en un arreglo ordenado con \(n\) claves distintas, donde la clave buscada se elige uniformemente entre esas \(n\) claves. Se comparan dos reglas:
$$B(n)=\text{número esperado de comparaciones cuando en cada paso se prueba el punto medio},$$
$$R(n)=\text{número esperado de comparaciones cuando en cada paso el pivote se elige al azar de manera uniforme}.$$
La tarea consiste en calcular \(R(n)-B(n)\) para \(n=10^{10}\). Una simulación directa no tiene sentido, así que la solución deduce fórmulas cerradas para ambas esperanzas y luego las evalúa numéricamente.
Ambas esperanzas dependen solo de la forma del árbol de búsqueda inducido por la regla elegida. La regla del punto medio produce un árbol binario casi completo, mientras que la regla aleatoria coincide con el coste medio de una búsqueda exitosa en un árbol binario de búsqueda aleatorio.
Sea \(h=\lfloor \log_2 n \rfloor\). Entonces los primeros \(h\) niveles del árbol de decisión contienen
$$1+2+\cdots+2^{h-1}=2^h-1$$
claves. Escribimos
$$r=n-(2^h-1),\qquad 1\le r\le 2^h.$$
Todos los niveles \(0,1,\dots,h-1\) están completos y las \(r\) claves restantes quedan en la profundidad \(h\). Una clave situada en profundidad \(d\) requiere \(d+1\) comparaciones, así que el total de comparaciones sobre los \(n\) objetivos posibles es
$$S_B(n)=\sum_{d=0}^{h-1}(d+1)2^d+(h+1)r.$$
Usando la identidad
$$\sum_{d=0}^{h-1}(d+1)2^d=(h-1)2^h+1,$$
obtenemos
$$S_B(n)=(h+1)n-2^{h+1}+(h+2),$$
y por tanto
$$\boxed{B(n)=\frac{S_B(n)}{n}=(h+1)-\frac{2^{h+1}-(h+2)}{n}.}$$
En la regla aleatoria, sea \(k\in\{1,\dots,n\}\) el rango del pivote actual, elegido uniformemente, y \(t\in\{1,\dots,n\}\) el rango del objetivo, también uniforme. Se paga una comparación de inmediato.
Si \(t=k\), la búsqueda termina. Si \(t<k\), el siguiente subproblema tiene tamaño \(k-1\). Si \(t>k\), el siguiente subproblema tiene tamaño \(n-k\). Promediando sobre todos los \(n^2\) pares \((t,k)\) se obtiene
$$R(n)=1+\frac{1}{n^2}\sum_{k=1}^{n}\left((k-1)R(k-1)+(n-k)R(n-k)\right).$$
Como los tamaños iguales aparecen simétricamente a izquierda y derecha, esto se simplifica a
$$\boxed{R(n)=1+\frac{2}{n^2}\sum_{i=1}^{n-1} i\,R(i).}$$
Es exactamente la misma recurrencia que aparece en el coste medio de una búsqueda exitosa en un árbol binario de búsqueda aleatorio.
Multiplicamos la recurrencia por \(n^2\):
$$n^2R(n)=n^2+2\sum_{i=1}^{n-1} i\,R(i).$$
Escribiendo la misma fórmula para \(n-1\), restando y reordenando, resulta
$$\frac{nR(n)}{n+1}=\frac{(n-1)R(n-1)}{n}+\frac{2n-1}{n(n+1)}.$$
Definimos ahora
$$A_n=\frac{nR(n)}{n+1}.$$
Entonces
$$A_n=A_{n-1}+\frac{2n-1}{n(n+1)}=A_{n-1}-\frac{1}{n}+\frac{3}{n+1}.$$
Como \(R(1)=1\), se tiene \(A_1=\frac12\). Al telescopar desde \(2\) hasta \(n\) se llega a
$$A_n=\frac12+\sum_{k=2}^{n}\left(-\frac{1}{k}+\frac{3}{k+1}\right)=2H_n+\frac{3}{n+1}-3,$$
donde
$$H_n=\sum_{k=1}^{n}\frac1k$$
es el \(n\)-ésimo número armónico. Sustituyendo de nuevo se obtiene la forma cerrada
$$\boxed{R(n)=2\frac{n+1}{n}H_n-3.}$$
Para el tamaño objetivo no hace falta sumar \(H_n\) término a término. La implementación usa la expansión de Euler-Maclaurin
$$H_n=\log n+\gamma+\frac{1}{2n}-\frac{1}{12n^2}+\frac{1}{120n^4}+O(n^{-6}),$$
donde \(\gamma\) es la constante de Euler-Mascheroni. Cuando \(n=10^{10}\), los términos omitidos quedan muy por debajo de las ocho cifras decimales pedidas, así que la aproximación es más que suficiente.
La cantidad final es por tanto
$$\boxed{\Delta(n)=R(n)-B(n)=2\frac{n+1}{n}H_n-3-\left((h+1)-\frac{2^{h+1}-(h+2)}{n}\right),\qquad h=\lfloor\log_2 n\rfloor.}$$
Aquí \(h=\lfloor\log_2 6\rfloor=2\) y \(r=6-(2^2-1)=3\). El árbol determinista tiene una clave en profundidad \(0\), dos claves en profundidad \(1\) y tres claves en profundidad \(2\). Así,
$$S_B(6)=1\cdot1+2\cdot2+3\cdot3=14,\qquad B(6)=\frac{14}{6}=\frac73=2.333333\ldots$$
Para la regla aleatoria,
$$H_6=1+\frac12+\frac13+\frac14+\frac15+\frac16=\frac{49}{20},$$
de modo que
$$R(6)=2\cdot\frac76\cdot\frac{49}{20}-3=\frac{163}{60}=2.716666\ldots$$
Por consiguiente
$$R(6)-B(6)=\frac{163}{60}-\frac73=\frac{23}{60}=0.383333\ldots,$$
que coincide con el valor de comprobación usado por la implementación.
Las implementaciones en C++, Python y Java siguen el mismo plan numérico. Primero evalúan \(B(n)\) directamente a partir de la fórmula cerrada, obteniendo \(\lfloor\log_2 n\rfloor\) mediante lógica de longitud en bits en lugar de simular la búsqueda de forma recursiva.
Después evalúan \(H_n\). Para \(n\le 10^6\), el número armónico se suma exactamente como \(\sum_{k=1}^{n}1/k\), lo que sirve para ejemplos pequeños y mantiene la fórmula exacta en entradas pequeñas. Para valores mayores, cambian a la serie asintótica anterior e incorporan explícitamente la constante de Euler-Mascheroni.
Con \(H_n\) ya disponible, calculan \(R(n)=2\frac{n+1}{n}H_n-3\), restan \(B(n)\) y muestran el resultado con ocho cifras decimales. La implementación en C++ además comprueba el caso de control \(n=6\) antes de evaluar la entrada principal.
La implementación es por tramos. En la rama que suma exactamente el número armónico, el tiempo es \(O(n)\) y la memoria es \(O(1)\). En la rama asintótica, que es la usada para la entrada real \(n=10^{10}\), tanto el tiempo como la memoria son \(O(1)\). En la práctica, la instancia de Project Euler se resuelve con una cantidad constante de aritmética en coma flotante.
我们研究的是在一个含有 \(n\) 个互不相同元素的有序表中进行成功查找，并且目标元素在这 \(n\) 个元素中等概率选取。题目比较两种策略：
$$B(n)=\text{每一步都检查当前区间中点时的期望比较次数},$$
$$R(n)=\text{每一步都在当前区间内均匀随机选择枢轴时的期望比较次数}.$$
要求计算的是 \(n=10^{10}\) 时的差值 \(R(n)-B(n)\)。直接做蒙特卡洛模拟没有意义，因为输入规模太大；真正可行的方法是把两种期望都化成闭式，再做数值求值。
这两个期望都可以从对应搜索树的形状来理解。固定取中点会得到一棵“尽量完全”的二叉决策树；而每一步随机选枢轴，则会导向与随机二叉搜索树中成功查找平均代价相同的递推关系。
设 \(h=\lfloor \log_2 n \rfloor\)。那么决策树前 \(h\) 层一共容纳
$$1+2+\cdots+2^{h-1}=2^h-1$$
个元素。记
$$r=n-(2^h-1),\qquad 1\le r\le 2^h.$$
这表示深度 \(0,1,\dots,h-1\) 的各层全部填满，剩下的 \(r\) 个元素位于深度 \(h\)。若某个元素位于深度 \(d\)，那么查找到它需要 \(d+1\) 次比较，因此对全部 \(n\) 个可能目标的比较总数为
$$S_B(n)=\sum_{d=0}^{h-1}(d+1)2^d+(h+1)r.$$
再利用有限和恒等式
$$\sum_{d=0}^{h-1}(d+1)2^d=(h-1)2^h+1,$$
便得到
$$S_B(n)=(h+1)n-2^{h+1}+(h+2),$$
于是
$$\boxed{B(n)=\frac{S_B(n)}{n}=(h+1)-\frac{2^{h+1}-(h+2)}{n}.}$$
这一步完全不需要递归模拟，只要知道树的层结构即可。
对随机策略，设当前枢轴的秩为 \(k\in\{1,\dots,n\}\)，它在当前区间内均匀选取；目标元素的秩为 \(t\in\{1,\dots,n\}\)，也同样均匀。无论如何，当前这一步都会先做一次比较。
如果 \(t=k\)，搜索立刻结束；如果 \(t<k\)，下一步转到左侧大小为 \(k-1\) 的子问题；如果 \(t>k\)，下一步转到右侧大小为 \(n-k\) 的子问题。对所有 \(n^2\) 个 \((t,k)\) 组合求平均，得到
$$R(n)=1+\frac{1}{n^2}\sum_{k=1}^{n}\left((k-1)R(k-1)+(n-k)R(n-k)\right).$$
由于相同规模的子问题会在左边和右边对称出现，这个式子可以整理成
$$\boxed{R(n)=1+\frac{2}{n^2}\sum_{i=1}^{n-1} i\,R(i).}$$
这个递推恰好就是随机二叉搜索树中“成功查找平均代价”所满足的递推，因此两者完全一致。
先把上式乘上 \(n^2\)：
$$n^2R(n)=n^2+2\sum_{i=1}^{n-1} i\,R(i).$$
再把同样的公式写给 \(n-1\)，两式相减并整理，可得
$$\frac{nR(n)}{n+1}=\frac{(n-1)R(n-1)}{n}+\frac{2n-1}{n(n+1)}.$$
现在引入一个辅助量
$$A_n=\frac{nR(n)}{n+1}.$$
那么递推就变成
$$A_n=A_{n-1}+\frac{2n-1}{n(n+1)}=A_{n-1}-\frac{1}{n}+\frac{3}{n+1}.$$
因为 \(R(1)=1\)，所以 \(A_1=\frac12\)。从 \(2\) 累加到 \(n\) 后发生望远镜消去，得到
$$A_n=\frac12+\sum_{k=2}^{n}\left(-\frac{1}{k}+\frac{3}{k+1}\right)=2H_n+\frac{3}{n+1}-3,$$
其中
$$H_n=\sum_{k=1}^{n}\frac1k$$
是第 \(n\) 个调和数。把 \(A_n\) 换回 \(R(n)\) 之后，就得到闭式
$$\boxed{R(n)=2\frac{n+1}{n}H_n-3.}$$
这正是实现中使用的核心公式。
当 \(n=10^{10}\) 时，没必要真的把 \(1+\frac12+\cdots+\frac1n\) 全部累加。实现采用 Euler-Maclaurin 渐近展开：
$$H_n=\log n+\gamma+\frac{1}{2n}-\frac{1}{12n^2}+\frac{1}{120n^4}+O(n^{-6}),$$
这里 \(\gamma\) 是 Euler-Mascheroni 常数。对于 \(10^{10}\) 这样的大输入，忽略的后续项远远小于题目要求的八位小数精度，因此这个近似已经绰绰有余。
于是最终要计算的量可以写成
$$\boxed{\Delta(n)=R(n)-B(n)=2\frac{n+1}{n}H_n-3-\left((h+1)-\frac{2^{h+1}-(h+2)}{n}\right),\qquad h=\lfloor\log_2 n\rfloor.}$$
这个例子既小到可以手算，又足以检验两条公式。此时 \(h=\lfloor\log_2 6\rfloor=2\)，并且 \(r=6-(2^2-1)=3\)。确定性搜索树在深度 \(0\) 有 \(1\) 个元素，在深度 \(1\) 有 \(2\) 个元素，在深度 \(2\) 有 \(3\) 个元素，因此
$$S_B(6)=1\cdot1+2\cdot2+3\cdot3=14,\qquad B(6)=\frac{14}{6}=\frac73=2.333333\ldots$$
另一方面，
$$H_6=1+\frac12+\frac13+\frac14+\frac15+\frac16=\frac{49}{20},$$
所以
$$R(6)=2\cdot\frac76\cdot\frac{49}{20}-3=\frac{163}{60}=2.716666\ldots$$
最终差值为
$$R(6)-B(6)=\frac{163}{60}-\frac73=\frac{23}{60}=0.383333\ldots,$$
这与实现里用来做自检的数值完全一致。
C++、Python 和 Java 实现采用同一条数值路线。第一步，它们直接用闭式计算 \(B(n)\)，而 \(\lfloor\log_2 n\rfloor\) 不是通过递归模拟得到，而是借助整数的位长信息或前导零计数得到。
第二步，它们计算 \(H_n\)。当 \(n\le 10^6\) 时，调和数按 \(\sum_{k=1}^{n}1/k\) 逐项精确累加，这对小规模检查值很方便，也保证小输入时公式是精确的。超过这个阈值后，程序改用上面的渐近展开，并显式带入 Euler-Mascheroni 常数。
得到 \(H_n\) 以后，程序计算 \(R(n)=2\frac{n+1}{n}H_n-3\)，再减去 \(B(n)\)，最后以八位小数输出结果。C++ 版本在求主答案之前还会先验证 \(n=6\) 的检查值。
实现是分支式的。在精确累加调和数的分支上，时间复杂度为 \(O(n)\)，空间复杂度为 \(O(1)\)。在渐近分支上，也就是处理真实目标输入 \(n=10^{10}\) 时所走的路径，时间和空间都为 \(O(1)\)。就本题而言，真正执行的只是一小组常数次浮点运算。
Рассматривается успешный поиск в отсортированном массиве из \(n\) различных ключей, где искомый ключ выбирается равновероятно среди этих \(n\) элементов. Сравниваются два правила:
$$B(n)=\text{математическое ожидание числа сравнений, если каждый раз брать середину},$$
$$R(n)=\text{математическое ожидание числа сравнений, если на каждом шаге выбирать опорный индекс равномерно случайно}.$$
Нужно вычислить \(R(n)-B(n)\) при \(n=10^{10}\). Прямое моделирование здесь бессмысленно, поэтому решение выводит закрытые формулы для обоих ожиданий и затем численно их подставляет.
Обе величины определяются формой дерева поиска, которое создаёт соответствующее правило. Выбор середины даёт почти полный бинарный дерево поиска, а случайный опорный элемент приводит к той же средней стоимости успешного поиска, что и в случайном бинарном дереве поиска.
Пусть \(h=\lfloor \log_2 n \rfloor\). Тогда первые \(h\) уровней дерева решений содержат
$$1+2+\cdots+2^{h-1}=2^h-1$$
ключей. Обозначим
$$r=n-(2^h-1),\qquad 1\le r\le 2^h.$$
Уровни \(0,1,\dots,h-1\) полностью заполнены, а оставшиеся \(r\) ключей лежат на глубине \(h\). Ключ на глубине \(d\) требует \(d+1\) сравнений, поэтому суммарное число сравнений по всем \(n\) возможным целям равно
$$S_B(n)=\sum_{d=0}^{h-1}(d+1)2^d+(h+1)r.$$
Используя тождество
$$\sum_{d=0}^{h-1}(d+1)2^d=(h-1)2^h+1,$$
получаем
$$S_B(n)=(h+1)n-2^{h+1}+(h+2),$$
а значит
$$\boxed{B(n)=\frac{S_B(n)}{n}=(h+1)-\frac{2^{h+1}-(h+2)}{n}.}$$
Пусть текущий опорный элемент имеет ранг \(k\in\{1,\dots,n\}\) и выбирается равномерно, а искомый элемент имеет ранг \(t\in\{1,\dots,n\}\) и тоже равномерно распределён. На текущем шаге всегда выполняется одно сравнение.
Если \(t=k\), поиск завершается. Если \(t<k\), следующий подзадача имеет размер \(k-1\). Если \(t>k\), следующий подзадача имеет размер \(n-k\). Усреднение по всем \(n^2\) парам \((t,k)\) даёт
$$R(n)=1+\frac{1}{n^2}\sum_{k=1}^{n}\left((k-1)R(k-1)+(n-k)R(n-k)\right).$$
Подзадачи одинакового размера возникают симметрично слева и справа, поэтому выражение упрощается до
$$\boxed{R(n)=1+\frac{2}{n^2}\sum_{i=1}^{n-1} i\,R(i).}$$
Это ровно та же рекурсия, что и для средней стоимости успешного поиска в случайном бинарном дереве поиска.
Умножим рекурсию на \(n^2\):
$$n^2R(n)=n^2+2\sum_{i=1}^{n-1} i\,R(i).$$
Запишем ту же формулу для \(n-1\), вычтем и перегруппируем:
$$\frac{nR(n)}{n+1}=\frac{(n-1)R(n-1)}{n}+\frac{2n-1}{n(n+1)}.$$
Теперь введём
$$A_n=\frac{nR(n)}{n+1}.$$
Тогда
$$A_n=A_{n-1}+\frac{2n-1}{n(n+1)}=A_{n-1}-\frac{1}{n}+\frac{3}{n+1}.$$
Так как \(R(1)=1\), имеем \(A_1=\frac12\). Телескопируя сумму от \(2\) до \(n\), получаем
$$A_n=\frac12+\sum_{k=2}^{n}\left(-\frac{1}{k}+\frac{3}{k+1}\right)=2H_n+\frac{3}{n+1}-3,$$
где
$$H_n=\sum_{k=1}^{n}\frac1k$$
есть \(n\)-е гармоническое число. Подставляя обратно, приходим к закрытой формуле
$$\boxed{R(n)=2\frac{n+1}{n}H_n-3.}$$
Для целевого размера входа нет смысла суммировать \(H_n\) по определению. Реализация использует разложение Эйлера-Маклорена
$$H_n=\log n+\gamma+\frac{1}{2n}-\frac{1}{12n^2}+\frac{1}{120n^4}+O(n^{-6}),$$
где \(\gamma\) — постоянная Эйлера-Маскерони. При \(n=10^{10}\) отброшенные члены намного меньше требуемой точности в восемь знаков после запятой, поэтому такого приближения более чем достаточно.
Итоговая величина равна
$$\boxed{\Delta(n)=R(n)-B(n)=2\frac{n+1}{n}H_n-3-\left((h+1)-\frac{2^{h+1}-(h+2)}{n}\right),\qquad h=\lfloor\log_2 n\rfloor.}$$
Здесь \(h=\lfloor\log_2 6\rfloor=2\) и \(r=6-(2^2-1)=3\). В детерминированном дереве поиска один ключ лежит на глубине \(0\), два ключа на глубине \(1\) и три ключа на глубине \(2\). Поэтому
$$S_B(6)=1\cdot1+2\cdot2+3\cdot3=14,\qquad B(6)=\frac{14}{6}=\frac73=2.333333\ldots$$
Для случайного правила
$$H_6=1+\frac12+\frac13+\frac14+\frac15+\frac16=\frac{49}{20},$$
откуда
$$R(6)=2\cdot\frac76\cdot\frac{49}{20}-3=\frac{163}{60}=2.716666\ldots$$
Следовательно,
$$R(6)-B(6)=\frac{163}{60}-\frac73=\frac{23}{60}=0.383333\ldots,$$
что в точности совпадает с контрольным значением из реализации.
Реализации на C++, Python и Java используют один и тот же численный план. Сначала они напрямую вычисляют \(B(n)\) по закрытой формуле, получая \(\lfloor\log_2 n\rfloor\) через битовую длину числа или подсчёт ведущих нулей, а не через рекурсивное моделирование.
Затем вычисляется \(H_n\). Для \(n\le 10^6\) гармоническое число суммируется точно как \(\sum_{k=1}^{n}1/k\), что полезно для небольших контрольных примеров и обеспечивает точность на малых входах. Для больших \(n\) используется приведённое выше асимптотическое разложение с явным значением постоянной Эйлера-Маскерони.
После этого программа вычисляет \(R(n)=2\frac{n+1}{n}H_n-3\), вычитает \(B(n)\) и печатает результат с восемью знаками после запятой. Версия на C++ дополнительно проверяет контрольный случай \(n=6\) перед основным вычислением.
Реализация работает по двум ветвям. В ветви с точным суммированием гармонического числа время равно \(O(n)\), память — \(O(1)\). В асимптотической ветви, которая используется для реального входа \(n=10^{10}\), и время, и память равны \(O(1)\). На практике задача Project Euler решается постоянным числом операций с плавающей точкой.
ندرس البحث الناجح في مصفوفة مرتبة تحتوي على \(n\) مفاتيح متميزة، مع افتراض أن المفتاح المطلوب يُختار بالتساوي من بين هذه المفاتيح \(n\). تتم المقارنة بين قاعدتين:
\(B(n)\) هو القيمة المتوقعة لعدد المقارنات عندما نفحص العنصر الأوسط في كل خطوة.
\(R(n)\) هو القيمة المتوقعة لعدد المقارنات عندما نختار المحور عشوائيًا وبانتظام في كل خطوة.
المطلوب هو حساب الفرق \(R(n)-B(n)\) عند \(n=10^{10}\). المحاكاة المباشرة غير مجدية هنا، لذلك يعتمد الحل على اشتقاق صيغ مغلقة ثم تقييمها عدديًا.
كل من القيمتين يعتمد على شكل شجرة البحث الناتجة عن القاعدة المختارة. اختيار المنتصف يولد شجرة ثنائية شبه مكتملة، أما اختيار محور عشوائي فيقود إلى نفس متوسط كلفة البحث الناجح في شجرة بحث ثنائية عشوائية.
لتكن \(h=\lfloor \log_2 n \rfloor\). عندئذٍ فإن أول \(h\) مستويات من شجرة القرار تحتوي
$$1+2+\cdots+2^{h-1}=2^h-1$$
مفتاحًا. نكتب
$$r=n-(2^h-1),\qquad 1\le r\le 2^h.$$
جميع المستويات \(0,1,\dots,h-1\) ممتلئة، أما المفاتيح \(r\) الباقية فتقع على العمق \(h\). وإذا كان مفتاح ما في العمق \(d\)، فإنه يحتاج إلى \(d+1\) مقارنة. لذلك يكون مجموع المقارنات على جميع الأهداف الممكنة هو
$$S_B(n)=\sum_{d=0}^{h-1}(d+1)2^d+(h+1)r.$$
وباستخدام الهوية
$$\sum_{d=0}^{h-1}(d+1)2^d=(h-1)2^h+1,$$
نحصل على
$$S_B(n)=(h+1)n-2^{h+1}+(h+2),$$
ومن ثم
$$\boxed{B(n)=\frac{S_B(n)}{n}=(h+1)-\frac{2^{h+1}-(h+2)}{n}.}$$
في القاعدة العشوائية، ليكن رتبة المحور الحالي \(k\in\{1,\dots,n\}\) وتُختار بانتظام، ولتكن رتبة الهدف \(t\in\{1,\dots,n\}\) وهي أيضًا منتظمة. هناك مقارنة واحدة تُدفع دائمًا في الخطوة الحالية.
إذا كان \(t=k\) ينتهي البحث. وإذا كان \(t<k\) فإن حجم المسألة الفرعية التالية هو \(k-1\). وإذا كان \(t>k\) فإن الحجم التالي هو \(n-k\). بأخذ المتوسط على جميع الأزواج \((t,k)\) وعددها \(n^2\) نحصل على
$$R(n)=1+\frac{1}{n^2}\sum_{k=1}^{n}\left((k-1)R(k-1)+(n-k)R(n-k)\right).$$
وبما أن الأحجام المتساوية تظهر بشكل متناظر في الجهتين، فإن هذا يتبسط إلى
$$\boxed{R(n)=1+\frac{2}{n^2}\sum_{i=1}^{n-1} i\,R(i).}$$
وهذه هي بالضبط العلاقة نفسها الخاصة بمتوسط كلفة البحث الناجح في شجرة بحث ثنائية عشوائية.
نضرب العلاقة في \(n^2\):
$$n^2R(n)=n^2+2\sum_{i=1}^{n-1} i\,R(i).$$
ثم نكتب الصيغة نفسها لـ \(n-1\)، ونطرح، ونعيد الترتيب فنحصل على
$$\frac{nR(n)}{n+1}=\frac{(n-1)R(n-1)}{n}+\frac{2n-1}{n(n+1)}.$$
الآن نعرّف
$$A_n=\frac{nR(n)}{n+1}.$$
فتصبح العلاقة
$$A_n=A_{n-1}+\frac{2n-1}{n(n+1)}=A_{n-1}-\frac{1}{n}+\frac{3}{n+1}.$$
وبما أن \(R(1)=1\)، فإن \(A_1=\frac12\). وعند جمع الحدود من \(2\) حتى \(n\) نحصل على تلسكوب يعطي
$$A_n=\frac12+\sum_{k=2}^{n}\left(-\frac{1}{k}+\frac{3}{k+1}\right)=2H_n+\frac{3}{n+1}-3,$$
حيث
$$H_n=\sum_{k=1}^{n}\frac1k$$
هو العدد التوافقي \(n\)-ي. وبالرجوع إلى \(R(n)\) نجد الصيغة المغلقة
$$\boxed{R(n)=2\frac{n+1}{n}H_n-3.}$$
عند الحجم المستهدف لا حاجة إلى جمع \(H_n\) حدًا حدًا. تستخدم الشيفرة توسع أويلر-ماكلوران
$$H_n=\log n+\gamma+\frac{1}{2n}-\frac{1}{12n^2}+\frac{1}{120n^4}+O(n^{-6}),$$
حيث \(\gamma\) هو ثابت أويلر-ماسكيروني. وعند \(n=10^{10}\) تكون الحدود المهملة أصغر بكثير من الدقة المطلوبة وهي ثماني خانات عشرية، لذا فهذا التقريب كافٍ تمامًا.
إذن الكمية النهائية هي
$$\boxed{\Delta(n)=R(n)-B(n)=2\frac{n+1}{n}H_n-3-\left((h+1)-\frac{2^{h+1}-(h+2)}{n}\right),\qquad h=\lfloor\log_2 n\rfloor.}$$
لدينا هنا \(h=\lfloor\log_2 6\rfloor=2\) و \(r=6-(2^2-1)=3\). شجرة البحث الحتمية تحتوي على مفتاح واحد في العمق \(0\)، ومفتاحين في العمق \(1\)، وثلاثة مفاتيح في العمق \(2\). لذلك
$$S_B(6)=1\cdot1+2\cdot2+3\cdot3=14,\qquad B(6)=\frac{14}{6}=\frac73=2.333333\ldots$$
أما في القاعدة العشوائية فلدينا
$$H_6=1+\frac12+\frac13+\frac14+\frac15+\frac16=\frac{49}{20},$$
ومن ثم
$$R(6)=2\cdot\frac76\cdot\frac{49}{20}-3=\frac{163}{60}=2.716666\ldots$$
وبالتالي
$$R(6)-B(6)=\frac{163}{60}-\frac73=\frac{23}{60}=0.383333\ldots,$$
وهو بالضبط مقدار التحقق الذي تستخدمه الشيفرة.
تتبع تطبيقات C++ وPython وJava الخطة العددية نفسها. أولًا تُحسب \(B(n)\) مباشرة من الصيغة المغلقة، ويُستخرج \(\lfloor\log_2 n\rfloor\) عبر منطق طول البتات أو عدّ الأصفار البادئة بدلًا من محاكاة الاستدعاء التعاودي.
بعد ذلك تُحسب \(H_n\). عندما يكون \(n\le 10^6\)، تجمع الشيفرة العدد التوافقي بدقة على صورة \(\sum_{k=1}^{n}1/k\)، وهذا مفيد للتحقق من الحالات الصغيرة ويحافظ على الدقة هناك. أما للقيم الأكبر فتتحول إلى المتسلسلة الأسيمبتوطية السابقة مع استخدام ثابت أويلر-ماسكيروني صراحةً.
وبعد توفر \(H_n\)، تُحسب \(R(n)=2\frac{n+1}{n}H_n-3\)، ثم يُطرح منها \(B(n)\)، وأخيرًا يُطبع الناتج بثماني خانات بعد الفاصلة. كما أن نسخة C++ تتحقق أيضًا من حالة \(n=6\) قبل حساب الحالة الرئيسية.
التنفيذ هنا ذو مسارين. في مسار الجمع الدقيق للعدد التوافقي يكون الزمن \(O(n)\) والذاكرة \(O(1)\). وفي المسار الأسيمبتوطي، وهو المسار المستخدم فعليًا للمدخل \(n=10^{10}\)، يكون كل من الزمن والذاكرة \(O(1)\). عمليًا، مسألة Project Euler هذه تُحل بعدد ثابت من العمليات ذات الفاصلة العائمة.