A kangaroo starts at 0, and each hop has an independent length uniformly distributed on \([0,1]\). Let \(H(x)\) denote the expected number of hops needed to reach or pass position \(x\). The task is to determine the first eight digits after the decimal point of \(H(10^6)\) that are not equal to 6.
A direct numerical attack on the defining recurrence is the wrong scale of computation. The important fact is that for large integers \(n\), the fractional part of \(H(n)\) is extraordinarily close to \(0.6666\ldots\), so the real problem is to identify where that long run of sixes first changes and what the first non-6 digits are.
The solution is built from an exact renewal equation, a Laplace transform with a very structured denominator, and a residue calculation at the dominant complex poles.
If \(x \le 0\), no hop is required, so \(H(x)=0\). For \(x>0\), after the first hop of length \(U\sim \mathrm{Unif}[0,1]\), the remaining expected number of hops is \(H(x-U)\). Therefore
$$H(x)=1+\int_0^1 H(x-u)\,du,$$
with the convention \(H(y)=0\) for \(y\le 0\). This is the exact problem-specific object behind all three implementations.
Differentiating the integral equation gives
$$H'(x)=H(x)-H(x-1)\qquad (x>0).$$
On \(0<x<1\), the term \(H(x-1)\) vanishes, so \(H'(x)=H(x)\) and \(H(0^+)=1\). Hence
$$H(x)=e^x\qquad (0\le x\le 1).$$
On \(1<x<2\), this becomes \(H'(x)=H(x)-e^{x-1}\), so
$$H(x)=e^x-(x-1)e^{x-1}\qquad (1\le x\le 2).$$
In particular,
$$H(2)=e^2-e.$$
Repeating the same piecewise argument on the next interval yields
$$H(3)=e^3-2e^2+\frac{e}{2}.$$
These are not ornamental formulas: they are concrete checkpoints for the digit extractor and they show the characteristic exponential-polynomial structure of the exact solution.
Let
$$F(s)=\int_0^\infty H(x)e^{-sx}\,dx.$$
Transforming the renewal equation gives
$$F(s)=\frac1s+\frac{1-e^{-s}}sF(s),$$
hence
$$F(s)=\frac{1}{s-1+e^{-s}}.$$
The denominator has a double zero at \(s=0\), because
$$s-1+e^{-s}=\frac{s^2}{2}-\frac{s^3}{6}+O(s^4).$$
So near the origin,
$$F(s)=\frac{2}{s^2}+\frac{2}{3s}+O(1).$$
After inverting the Laplace transform, this becomes
$$H(x)=2x+\frac23+\text{exponentially small oscillating terms}.$$
For integer \(n\), the term \(2n\) is integral, so the fractional part of \(H(n)\) is governed by \(2/3\) plus a tiny correction.
All remaining terms come from the nonzero roots of
$$s-1+e^{-s}=0.$$
Rewriting it as \((s-1)e^s=-1\) gives
$$s=1+W_k(-e^{-1}),$$
where \(W_k\) is a branch of the Lambert \(W\) function. The nearest nonzero roots form a complex-conjugate pair
$$\lambda=\alpha+i\beta,\qquad \bar{\lambda}=\alpha-i\beta,$$
with
$$\alpha\approx -2.08884301561304,\qquad \beta\approx 7.46148928565425.$$
If \(p\neq 0\) is a root, then the residue of \(F(s)\) at \(p\) is \(1/p\), because the derivative of the denominator is \(1-e^{-p}=p\) at a root. Therefore the dominant correction at integer \(n\) is
$$\varepsilon_n \approx \frac{e^{\lambda n}}{\lambda}+\frac{e^{\bar{\lambda} n}}{\bar{\lambda}}=\frac{2\big(\alpha\cos(\beta n)+\beta\sin(\beta n)\big)}{\alpha^2+\beta^2}e^{\alpha n}.$$
Hence
$$H(n)=2n+\frac23+\varepsilon_n+\text{smaller terms},$$
and the correction decays exponentially because \(\alpha<0\).
The implementations never expand the full decimal prefix. Instead they compute
$$\log_{10}|\varepsilon_n|=\frac{\alpha n}{\ln 10}+\log_{10}\left|\frac{2\big(\alpha\cos(\beta n)+\beta\sin(\beta n)\big)}{\alpha^2+\beta^2}\right|.$$
If
$$-\log_{10}|\varepsilon_n|=m+\theta,\qquad m=\lfloor -\log_{10}|\varepsilon_n|\rfloor,\quad 0\le \theta<1,$$
then
$$\varepsilon_n=\sigma 10^{-m-\theta},\qquad \sigma\in\{-1,1\}.$$
So the first deviation from \(0.6666\ldots\) occurs around the \(m\)-th decimal position. The code sets \(t=\sigma 10^{-\theta}\), writes
$$\frac23+t=q+r,\qquad q=\left\lfloor \frac23+t\right\rfloor,\quad 0\le r<1,$$
uses \(q\) as a carry or borrow into a short artificial tail of sixes, and then reads the next digits from the fractional part \(r\). Any digit equal to 6 is skipped, and the first eight remaining digits are the answer.
The C++, Python, and Java implementations all evaluate the same asymptotic formula at high precision. They store \(\alpha\) and \(\beta\), reduce \(\beta n\) modulo \(2\pi\), and compute the trigonometric envelope that multiplies \(e^{\alpha n}\).
The important numerical trick is that they work with \(\log_{10}|\varepsilon_n|\) rather than with the full tiny number \(\varepsilon_n\). That immediately reveals how far to the right the first non-6 digit appears, without materializing the enormous block of preceding sixes.
After the location step, the implementation creates a short decimal tail initially filled with sixes, applies the possible carry or borrow coming from \(q\), and then continues with the fractional digits of \(r\). Every time a produced digit is 6 it is ignored; every other digit is appended. One implementation also checks the extractor against the exact closed forms for \(H(2)\) and \(H(3)\).
The problem is solved by a constant-size analytic formula, not by iterating up to \(10^6\) in the original recurrence. High-precision transcendental evaluation dominates the setup, but that cost does not grow combinatorially with \(n\).
If \(D\) denotes the number of requested non-6 digits, the extraction phase is \(O(D)\) time and \(O(D)\) space. Here \(D=8\), so the overall computation is effectively constant time and constant memory for practical purposes.
Ein Känguru startet bei 0, und jede Sprunglänge ist unabhängig und gleichverteilt auf \([0,1]\). Sei \(H(x)\) der erwartete Wert der Anzahl von Sprüngen, die nötig sind, um die Position \(x\) zu erreichen oder zu überschreiten. Gesucht sind die ersten acht Nachkommastellen von \(H(10^6)\), die nicht gleich 6 sind.
Die Implementierungen berechnen \(H(10^6)\) nicht aus der ursprünglichen Rekursion heraus. Entscheidend ist, dass der Nachkommateil für große ganze \(n\) extrem nahe bei \(0.6666\ldots\) liegt. Also muss man nicht Millionen Stellen entwickeln, sondern nur bestimmen, an welcher Stelle die lange Kette von Sechsen zuerst abweicht und welche Nicht-6-Ziffern dort erscheinen.
Die Lösung verbindet eine exakte Erneuerungsgleichung, ihre Laplace-Transformierte und den Beitrag des dominanten komplexen Polpaares.
Für \(x\le 0\) gilt \(H(x)=0\), weil kein weiterer Sprung nötig ist. Für \(x>0\) bleibt nach dem ersten Sprung der Länge \(U\sim \mathrm{Unif}[0,1]\) im Mittel noch \(H(x-U)\) Arbeit übrig. Daher
$$H(x)=1+\int_0^1 H(x-u)\,du,$$
wobei \(H(y)=0\) für \(y\le 0\) gesetzt wird. Genau diese Gleichung steckt hinter den numerischen Implementierungen.
Durch Ableiten erhält man
$$H'(x)=H(x)-H(x-1)\qquad (x>0).$$
Auf dem Intervall \(0<x<1\) verschwindet \(H(x-1)\), also ist \(H'(x)=H(x)\) mit \(H(0^+)=1\). Damit
$$H(x)=e^x\qquad (0\le x\le 1).$$
Auf \(1<x<2\) folgt
$$H(x)=e^x-(x-1)e^{x-1}\qquad (1\le x\le 2),$$
und damit insbesondere
$$H(2)=e^2-e.$$
Ein weiterer Schritt über das nächste Intervall liefert
$$H(3)=e^3-2e^2+\frac{e}{2}.$$
Diese Werte sind nützliche Prüfsteine, weil sie exakt mit den kleinen Testfällen des Ziffern-Extraktors übereinstimmen.
Setze
$$F(s)=\int_0^\infty H(x)e^{-sx}\,dx.$$
Die Transformation der Erneuerungsgleichung ergibt
$$F(s)=\frac1s+\frac{1-e^{-s}}sF(s),$$
also
$$F(s)=\frac{1}{s-1+e^{-s}}.$$
Der Nenner besitzt bei \(s=0\) eine doppelte Nullstelle, denn
$$s-1+e^{-s}=\frac{s^2}{2}-\frac{s^3}{6}+O(s^4).$$
Daraus folgt lokal
$$F(s)=\frac{2}{s^2}+\frac{2}{3s}+O(1),$$
und nach Rücktransformation
$$H(x)=2x+\frac23+\text{exponentiell kleine oszillierende Terme}.$$
Für ganzzahliges \(n\) trägt \(2n\) nichts zum Nachkommateil bei, also wird dieser nur von \(2/3\) plus einer winzigen Korrektur bestimmt.
Alle restlichen Beiträge stammen von den von 0 verschiedenen Lösungen von
$$s-1+e^{-s}=0.$$
Umgeformt zu \((s-1)e^s=-1\) erhält man
$$s=1+W_k(-e^{-1}),$$
wobei \(W_k\) ein Ast der Lambert-\(W\)-Funktion ist. Die nächstliegenden nichttrivialen Pole sind ein komplex konjugiertes Paar
$$\lambda=\alpha+i\beta,\qquad \bar{\lambda}=\alpha-i\beta,$$
mit
$$\alpha\approx -2.08884301561304,\qquad \beta\approx 7.46148928565425.$$
Ist \(p\neq 0\) eine Nullstelle, dann ist das Residuum von \(F(s)\) dort gleich \(1/p\), denn die Ableitung des Nenners ist an der Nullstelle \(1-e^{-p}=p\). Somit lautet die dominante Korrektur für ganzzahliges \(n\)
$$\varepsilon_n \approx \frac{e^{\lambda n}}{\lambda}+\frac{e^{\bar{\lambda} n}}{\bar{\lambda}}=\frac{2\big(\alpha\cos(\beta n)+\beta\sin(\beta n)\big)}{\alpha^2+\beta^2}e^{\alpha n}.$$
Daher
$$H(n)=2n+\frac23+\varepsilon_n+\text{kleinere Terme},$$
und wegen \(\alpha<0\) fällt \(\varepsilon_n\) exponentiell ab.
Statt die riesige Dezimalentwicklung auszuschreiben, berechnen die Programme
$$\log_{10}|\varepsilon_n|=\frac{\alpha n}{\ln 10}+\log_{10}\left|\frac{2\big(\alpha\cos(\beta n)+\beta\sin(\beta n)\big)}{\alpha^2+\beta^2}\right|.$$
Wenn
$$-\log_{10}|\varepsilon_n|=m+\theta,\qquad m=\lfloor -\log_{10}|\varepsilon_n|\rfloor,\quad 0\le \theta<1,$$
dann gilt
$$\varepsilon_n=\sigma 10^{-m-\theta},\qquad \sigma\in\{-1,1\}.$$
Die erste Abweichung von \(0.6666\ldots\) liegt also ungefähr an der \(m\)-ten Nachkommastelle. Die Implementierungen setzen \(t=\sigma 10^{-\theta}\), zerlegen
$$\frac23+t=q+r,\qquad q=\left\lfloor \frac23+t\right\rfloor,\quad 0\le r<1,$$
verwenden \(q\) als Übertrag oder Entlehnung auf einen kurzen künstlichen Schwanz aus Sechsen und lesen die folgenden Stellen aus dem Bruchteil \(r\). Jede erzeugte 6 wird übersprungen, bis acht Nicht-6-Ziffern gesammelt sind.
Die C++-, Python- und Java-Implementierungen werten dieselbe asymptotische Formel in hoher Präzision aus. Dazu werden \(\alpha\) und \(\beta\) gespeichert, \(\beta n\) modulo \(2\pi\) reduziert und dann die trigonometrische Hüllfunktion für \(\varepsilon_n\) berechnet.
Der numerisch wichtigste Schritt ist die Arbeit mit \(\log_{10}|\varepsilon_n|\) statt mit \(\varepsilon_n\) selbst. So wird die Position der ersten veränderten Stelle sofort sichtbar, ohne den riesigen Block führender Sechsen explizit darzustellen.
Anschließend baut die Implementierung einen kurzen Dezimalschwanz, der zunächst nur aus Sechsen besteht, wendet den eventuellen Übertrag oder die Entlehnung aus \(q\) an und ergänzt danach Stellen aus dem Bruchteil \(r\). Jede 6 wird verworfen, jede andere Ziffer an die Ausgabe angehängt. Eine der Implementierungen prüft zusätzlich den Extraktor mit den exakten Formeln für \(H(2)\) und \(H(3)\).
Das Problem wird durch eine analytische Formel fester Größe gelöst und nicht durch eine Rekursion bis \(10^6\). Der vorbereitende Aufwand steckt in hochpräzisen trigonometrischen, logarithmischen und exponentiellen Auswertungen, wächst aber nicht kombinatorisch mit \(n\).
Für \(D\) gesuchte Nicht-6-Ziffern kostet die Extraktionsphase \(O(D)\) Zeit und \(O(D)\) Speicher. Hier ist \(D=8\), also ist die Gesamtrechnung praktisch konstant.
Bir kanguru 0 noktasından başlıyor ve her sıçrama uzunluğu \([0,1]\) aralığında bağımsız ve düzgün dağılımlı. \(H(x)\), \(x\) konumuna ulaşmak ya da onu geçmek için gereken beklenen sıçrama sayısı olsun. İstenen şey, \(H(10^6)\) sayısının ondalık kısmında görülen ve 6 olmayan ilk sekiz rakamdır.
Tanımdaki beklenti bağıntısını doğrudan ileri doğru çözmek doğru yaklaşım değildir. Asıl önemli nokta, büyük tam sayılar için \(H(n)\)'in kesir kısmının \(0.6666\ldots\) değerine olağanüstü yakın olmasıdır. Bu yüzden çözüm, bütün o uzun 6 dizisini üretmek yerine ilk sapmanın nerede olduğunu ve ilk 6 olmayan rakamların ne çıktığını bulur.
Çözüm; ilk sıçrama üzerine koşullama, Laplace dönüşümü ve baskın karmaşık kutuplardan gelen artık hesabını birleştirir.
\(x\le 0\) ise artık sıçrama gerekmez, dolayısıyla \(H(x)=0\). \(x>0\) için ilk sıçrama uzunluğu \(U\sim \mathrm{Unif}[0,1]\) olsun. İlk sıçramadan sonra geriye ortalama olarak \(H(x-U)\) kadar iş kalır. Bu yüzden
$$H(x)=1+\int_0^1 H(x-u)\,du,$$
ve burada \(y\le 0\) için \(H(y)=0\) kabul edilir. Üç uygulamanın hepsi bu tam eşitliği sayısal olarak kullanır.
Bu integral denklemin türevi
$$H'(x)=H(x)-H(x-1)\qquad (x>0)$$
olur. \(0<x<1\) aralığında \(H(x-1)=0\) olduğu için \(H'(x)=H(x)\) ve \(H(0^+)=1\), dolayısıyla
$$H(x)=e^x\qquad (0\le x\le 1).$$
\(1<x<2\) aralığında ise
$$H(x)=e^x-(x-1)e^{x-1}\qquad (1\le x\le 2),$$
ve özellikle
$$H(2)=e^2-e.$$
Aynı parçalı çözümü bir kez daha uygularsak
$$H(3)=e^3-2e^2+\frac{e}{2}$$
elde edilir. Bu değerler yalnızca örnek değildir; rakam çıkarıcının küçük durumlarda doğru çalıştığını denetlemek için doğrudan kullanılır.
Şimdi problemi uzun menzilde yöneten ana terimi çıkarmak için Laplace dönüşümüne geçelim. Bunun için
$$F(s)=\int_0^\infty H(x)e^{-sx}\,dx$$
olsun. İntegral denklem Laplace dönüşümünde
$$F(s)=\frac1s+\frac{1-e^{-s}}sF(s)$$
şeklini alır; buradan
$$F(s)=\frac{1}{s-1+e^{-s}}$$
çıkar. Payda \(s=0\) noktasında çift köke sahiptir, çünkü
$$s-1+e^{-s}=\frac{s^2}{2}-\frac{s^3}{6}+O(s^4).$$
Dolayısıyla
$$F(s)=\frac{2}{s^2}+\frac{2}{3s}+O(1)$$
ve ters dönüşümden
$$H(x)=2x+\frac23+\text{üssel olarak küçülen salınımlı terimler}$$
elde edilir. \(n\) tam sayı olduğunda \(2n\) zaten tam sayıdır; bu yüzden kesir kısmını belirleyen şey esasen \(2/3\) ve çok küçük bir düzeltmedir.
Geri kalan bütün terimler
$$s-1+e^{-s}=0$$
denkleminin \(0\) dışındaki köklerinden gelir. Bunu \((s-1)e^s=-1\) biçiminde yazarsak
$$s=1+W_k(-e^{-1})$$
elde ederiz. Burada \(W_k\), Lambert \(W\) fonksiyonunun bir dalıdır. En yakın sıfır-dışı kökler
$$\lambda=\alpha+i\beta,\qquad \bar{\lambda}=\alpha-i\beta$$
karmaşık eşlenik çiftidir ve
$$\alpha\approx -2.08884301561304,\qquad \beta\approx 7.46148928565425.$$
\(p\neq 0\) bir kök ise, paydanın türevi kökte \(1-e^{-p}=p\) olduğundan artık \(1/p\) olur. Bu yüzden büyük tam sayı \(n\) için baskın düzeltme
$$\varepsilon_n \approx \frac{e^{\lambda n}}{\lambda}+\frac{e^{\bar{\lambda} n}}{\bar{\lambda}}=\frac{2\big(\alpha\cos(\beta n)+\beta\sin(\beta n)\big)}{\alpha^2+\beta^2}e^{\alpha n}$$
şeklindedir. Sonuç olarak
$$H(n)=2n+\frac23+\varepsilon_n+\text{daha küçük terimler}$$
ve \(\alpha<0\) olduğu için düzeltme üssel hızla söner.
Uygulamalar tam ondalık açılımı üretmez. Onun yerine
$$\log_{10}|\varepsilon_n|=\frac{\alpha n}{\ln 10}+\log_{10}\left|\frac{2\big(\alpha\cos(\beta n)+\beta\sin(\beta n)\big)}{\alpha^2+\beta^2}\right|$$
hesaplanır. Eğer
$$-\log_{10}|\varepsilon_n|=m+\theta,\qquad m=\lfloor -\log_{10}|\varepsilon_n|\rfloor,\quad 0\le \theta<1$$
ise
$$\varepsilon_n=\sigma 10^{-m-\theta},\qquad \sigma\in\{-1,1\}$$
olur. Bu da ilk sapmanın \(m\). ondalık basamak civarında bulunduğunu söyler. Kod \(t=\sigma 10^{-\theta}\) alır,
$$\frac23+t=q+r,\qquad q=\left\lfloor \frac23+t\right\rfloor,\quad 0\le r<1$$
ayrışımını yapar, \(q\) değerini kısa bir yapay 6 kuyruğuna elde ya da borç olarak uygular ve sonraki rakamları \(r\)'nin ondalık açılımından okur. 6 olan her rakam atlanır; geriye kalan ilk sekiz rakam cevap olur.
C++, Python ve Java uygulamaları aynı asimptotik formülü yüksek duyarlıkla değerlendirir. Bunun için \(\alpha\) ve \(\beta\) sabitlerini kullanır, \(\beta n\) açısını \(2\pi\) modunda küçültür ve düzeltme terimindeki trigonometrik zarfı hesaplar.
Sayısal açıdan kritik fikir, küçücük \(\varepsilon_n\) sayısını doğrudan üretmek yerine \(\log_{10}|\varepsilon_n|\) ile çalışmaktır. Böylece ilk değişen rakamın kaçıncı basamakta olduğu hemen bulunur ve ondan önce gelen devasa 6 bloğunu gerçekten yazmak gerekmez.
Konum belli olduktan sonra uygulama, başlangıçta tamamen 6'lardan oluşan kısa bir kuyruk kurar, \(q\)'dan gelen olası elde ya da borcu uygular ve sonra \(r\)'nin kesir kısmından rakam üretmeye devam eder. Üretilen rakam 6 ise yok sayılır; değilse sonuca eklenir. Uygulamalardan biri ayrıca \(H(2)\) ve \(H(3)\) için tam kapalı ifadelerle doğrulama yapar.
Bu problem, \(10^6\) adım boyunca orijinal beklenti bağıntısını çözerek değil, sabit boyutlu bir analitik formülle çözülür. Hazırlık maliyeti yüksek duyarlıklı trigonometrik, logaritmik ve üstel hesaplardan gelir; fakat bu maliyet \(n\) ile kombinatoryal olarak büyümez.
İstenen 6 olmayan rakam sayısı \(D\) ise, rakam çıkarma aşaması \(O(D)\) zaman ve \(O(D)\) bellek kullanır. Burada \(D=8\) olduğundan toplam çalışma pratikte sabit zamanlıdır.
Un canguro parte de 0 y cada salto tiene longitud independiente con distribución uniforme en \([0,1]\). Sea \(H(x)\) el número esperado de saltos necesarios para alcanzar o sobrepasar la posición \(x\). La tarea consiste en obtener los primeros ocho dígitos después del punto decimal de \(H(10^6)\) que no sean 6.
No conviene resolver la recurrencia original de manera directa. Para enteros grandes \(n\), la parte fraccionaria de \(H(n)\) está extraordinariamente cerca de \(0.6666\ldots\). Por eso el problema real es localizar dónde se rompe esa larga cola de seises y cuáles son los primeros dígitos distintos de 6 que aparecen allí.
La solución combina una ecuación exacta de renovación, su transformada de Laplace y la contribución del par dominante de polos complejos.
Si \(x\le 0\), no hace falta ningún salto adicional, así que \(H(x)=0\). Para \(x>0\), después del primer salto de longitud \(U\sim \mathrm{Unif}[0,1]\), queda en promedio \(H(x-U)\) saltos. Por tanto,
$$H(x)=1+\int_0^1 H(x-u)\,du,$$
tomando \(H(y)=0\) cuando \(y\le 0\). Esta es la ecuación exacta que sustenta la solución.
Al derivar se obtiene
$$H'(x)=H(x)-H(x-1)\qquad (x>0).$$
En \(0<x<1\), el término \(H(x-1)\) desaparece, de modo que \(H'(x)=H(x)\) y \(H(0^+)=1\). Así,
$$H(x)=e^x\qquad (0\le x\le 1).$$
En \(1<x<2\), resulta
$$H(x)=e^x-(x-1)e^{x-1}\qquad (1\le x\le 2),$$
y en particular
$$H(2)=e^2-e.$$
Repitiendo el mismo razonamiento por tramos se obtiene además
$$H(3)=e^3-2e^2+\frac{e}{2}.$$
Estos valores son ejemplos concretos y también puntos de control útiles para verificar la extracción de dígitos.
Definamos
$$F(s)=\int_0^\infty H(x)e^{-sx}\,dx.$$
La transformada de la ecuación de renovación satisface
$$F(s)=\frac1s+\frac{1-e^{-s}}sF(s),$$
por lo que
$$F(s)=\frac{1}{s-1+e^{-s}}.$$
El denominador tiene un cero doble en \(s=0\), ya que
$$s-1+e^{-s}=\frac{s^2}{2}-\frac{s^3}{6}+O(s^4).$$
Entonces
$$F(s)=\frac{2}{s^2}+\frac{2}{3s}+O(1),$$
y al invertir la transformada aparece
$$H(x)=2x+\frac23+\text{términos oscilatorios exponencialmente pequeños}.$$
Cuando \(n\) es entero, \(2n\) no afecta a la parte fraccionaria, así que el comportamiento decimal está gobernado por \(2/3\) más una corrección minúscula.
Los términos restantes proceden de las raíces no nulas de
$$s-1+e^{-s}=0.$$
Al reescribir como \((s-1)e^s=-1\), se obtiene
$$s=1+W_k(-e^{-1}),$$
donde \(W_k\) es una rama de la función \(W\) de Lambert. Las raíces no triviales más cercanas forman el par conjugado
$$\lambda=\alpha+i\beta,\qquad \bar{\lambda}=\alpha-i\beta,$$
con
$$\alpha\approx -2.08884301561304,\qquad \beta\approx 7.46148928565425.$$
Si \(p\neq 0\) es una raíz, el residuo de \(F(s)\) en \(p\) es \(1/p\), porque la derivada del denominador vale \(1-e^{-p}=p\) en una raíz. Por tanto, la corrección dominante para \(n\) entero es
$$\varepsilon_n \approx \frac{e^{\lambda n}}{\lambda}+\frac{e^{\bar{\lambda} n}}{\bar{\lambda}}=\frac{2\big(\alpha\cos(\beta n)+\beta\sin(\beta n)\big)}{\alpha^2+\beta^2}e^{\alpha n}.$$
Así,
$$H(n)=2n+\frac23+\varepsilon_n+\text{términos aún menores},$$
y como \(\alpha<0\), la corrección decae exponencialmente.
La implementación no escribe toda la expansión decimal. En cambio calcula
$$\log_{10}|\varepsilon_n|=\frac{\alpha n}{\ln 10}+\log_{10}\left|\frac{2\big(\alpha\cos(\beta n)+\beta\sin(\beta n)\big)}{\alpha^2+\beta^2}\right|.$$
Si
$$-\log_{10}|\varepsilon_n|=m+\theta,\qquad m=\lfloor -\log_{10}|\varepsilon_n|\rfloor,\quad 0\le \theta<1,$$
entonces
$$\varepsilon_n=\sigma 10^{-m-\theta},\qquad \sigma\in\{-1,1\}.$$
Eso significa que la primera desviación respecto de \(0.6666\ldots\) aparece alrededor de la posición decimal \(m\). Los programas toman \(t=\sigma 10^{-\theta}\), escriben
$$\frac23+t=q+r,\qquad q=\left\lfloor \frac23+t\right\rfloor,\quad 0\le r<1,$$
usan \(q\) como acarreo o préstamo sobre una cola corta de seises y luego generan las cifras siguientes desde la parte fraccionaria \(r\). Toda cifra igual a 6 se descarta; las demás se van acumulando hasta reunir ocho.
Las implementaciones en C++, Python y Java evalúan la misma fórmula asintótica con aritmética de alta precisión. Guardan \(\alpha\) y \(\beta\), reducen \(\beta n\) módulo \(2\pi\) y calculan la envolvente trigonométrica que acompaña a \(e^{\alpha n}\).
El truco numérico decisivo es trabajar con \(\log_{10}|\varepsilon_n|\) en lugar de \(\varepsilon_n\) directamente. Así se sabe cuántos seises aparecen antes de la primera cifra alterada sin materializar ese prefijo inmenso.
Después, el algoritmo construye una pequeña cola decimal inicialmente llena de 6, aplica el posible acarreo o préstamo procedente de \(q\), y continúa con las cifras de la fracción \(r\). Si una cifra producida es 6 se omite; en caso contrario se añade a la respuesta. Una de las implementaciones también comprueba el extractor con las fórmulas exactas de \(H(2)\) y \(H(3)\).
El trabajo matemático duro queda absorbido en una fórmula analítica de tamaño constante. La evaluación de funciones trigonométricas, logarítmicas y exponenciales de alta precisión domina la preparación, pero no crece de forma combinatoria con \(n\).
Si \(D\) es el número de dígitos no-6 pedidos, la fase de extracción cuesta \(O(D)\) tiempo y \(O(D)\) memoria. En este problema \(D=8\), así que el cálculo completo es esencialmente constante.
一只袋鼠从 0 出发，每次跳跃的长度都独立且服从 \([0,1]\) 上的均匀分布。记 \(H(x)\) 为到达或越过位置 \(x\) 所需跳跃次数的期望值。题目要求找出 \(H(10^6)\) 的小数部分中，前八个不等于 6 的数字。
如果沿着原始递推一直算到 \(10^6\)，思路就偏了。真正关键的现象是：对很大的整数 \(n\)，\(H(n)\) 的小数部分极其接近 \(0.6666\ldots\)。因此需要解决的并不是“把所有数字展开”，而是“确定这一长串 6 在哪里第一次发生变化，以及最先出现的非 6 数字是什么”。
这个问题本质上是一个具有均匀跳长的更新过程。解法从精确的期望方程出发，经由 Laplace 变换，最后由最靠近原点的非零复极点控制主导误差项。
当 \(x\le 0\) 时，已经到达目标，不需要再跳，所以 \(H(x)=0\)。当 \(x>0\) 时，第一次跳跃长度记为 \(U\sim \mathrm{Unif}[0,1]\)。跳完之后，还需要的期望跳数就是 \(H(x-U)\)。因此有精确方程
$$H(x)=1+\int_0^1 H(x-u)\,du,$$
并约定当 \(y\le 0\) 时 \(H(y)=0\)。这正是代码背后的核心数学对象。
对上式求导可得
$$H'(x)=H(x)-H(x-1)\qquad (x>0).$$
在区间 \(0<x<1\) 上，\(H(x-1)=0\)，所以 \(H'(x)=H(x)\)，且 \(H(0^+)=1\)。于是
$$H(x)=e^x\qquad (0\le x\le 1).$$
在区间 \(1<x<2\) 上，方程变成 \(H'(x)=H(x)-e^{x-1}\)，从而
$$H(x)=e^x-(x-1)e^{x-1}\qquad (1\le x\le 2).$$
特别地，
$$H(2)=e^2-e.$$
再向前推进一个区间，可以得到
$$H(3)=e^3-2e^2+\frac{e}{2}.$$
这些不是可有可无的例子，而是非常重要的校验点，因为它们能直接验证数字提取步骤是否正确。
定义
$$F(s)=\int_0^\infty H(x)e^{-sx}\,dx.$$
把更新方程做 Laplace 变换，得到
$$F(s)=\frac1s+\frac{1-e^{-s}}sF(s),$$
因此
$$F(s)=\frac{1}{s-1+e^{-s}}.$$
注意分母在 \(s=0\) 处有一个二重零点，因为
$$s-1+e^{-s}=\frac{s^2}{2}-\frac{s^3}{6}+O(s^4).$$
所以在原点附近
$$F(s)=\frac{2}{s^2}+\frac{2}{3s}+O(1).$$
反变换后得到
$$H(x)=2x+\frac23+\text{指数级衰减的振荡项}.$$
当 \(n\) 是整数时，\(2n\) 本身就是整数，不影响小数部分，所以决定小数行为的是 \(2/3\) 加上一个极小的修正项。
其余项来自方程
$$s-1+e^{-s}=0$$
的非零根。把它改写成 \((s-1)e^s=-1\)，就有
$$s=1+W_k(-e^{-1}),$$
其中 \(W_k\) 是 Lambert \(W\) 函数的某个分支。离原点最近的非零根是一对共轭复数
$$\lambda=\alpha+i\beta,\qquad \bar{\lambda}=\alpha-i\beta,$$
满足
$$\alpha\approx -2.08884301561304,\qquad \beta\approx 7.46148928565425.$$
若 \(p\neq 0\) 是一个根，那么 \(F(s)\) 在 \(p\) 处的留数等于 \(1/p\)，因为分母导数在根处正好是 \(1-e^{-p}=p\)。因此对整数 \(n\)，主导修正项为
$$\varepsilon_n \approx \frac{e^{\lambda n}}{\lambda}+\frac{e^{\bar{\lambda} n}}{\bar{\lambda}}=\frac{2\big(\alpha\cos(\beta n)+\beta\sin(\beta n)\big)}{\alpha^2+\beta^2}e^{\alpha n}.$$
于是
$$H(n)=2n+\frac23+\varepsilon_n+\text{更小的项},$$
而 \(\alpha<0\) 保证这个修正项衰减得非常快。
实现并不会真的把前面那一大串 6 写出来，而是先计算
$$\log_{10}|\varepsilon_n|=\frac{\alpha n}{\ln 10}+\log_{10}\left|\frac{2\big(\alpha\cos(\beta n)+\beta\sin(\beta n)\big)}{\alpha^2+\beta^2}\right|.$$
如果
$$-\log_{10}|\varepsilon_n|=m+\theta,\qquad m=\lfloor -\log_{10}|\varepsilon_n|\rfloor,\quad 0\le \theta<1,$$
那么
$$\varepsilon_n=\sigma 10^{-m-\theta},\qquad \sigma\in\{-1,1\}.$$
这说明偏离 \(0.6666\ldots\) 的第一处大约发生在第 \(m\) 位小数附近。代码令 \(t=\sigma 10^{-\theta}\)，再写成
$$\frac23+t=q+r,\qquad q=\left\lfloor \frac23+t\right\rfloor,\quad 0\le r<1.$$
\(q\) 负责处理对一小段“全是 6”的人工尾部的进位或借位，随后再从小数部分 \(r\) 继续逐位生成数字。凡是生成出 6 就跳过，收集到前八个非 6 数字为止。
C++、Python 和 Java 三个实现都在做同一件事：用高精度算术计算上面的渐近公式。它们保存 \(\alpha\) 与 \(\beta\) 的高精度常数，把 \(\beta n\) 按 \(2\pi\) 取模，从而稳定地计算余弦和正弦组合出来的振荡包络。
数值上的关键技巧是：不直接构造极其微小的 \(\varepsilon_n\)，而是先求 \(\log_{10}|\varepsilon_n|\)。这样一来，前面到底有多少个连续的 6 就已经知道了，而不必真的把那个超长前缀展开到内存里。
定位完成后，实现会先造一小段全为 6 的十进制尾部，根据 \(q\) 做可能的进位或借位，再从 \(r\) 的小数展开继续取数字。遇到 6 就忽略，遇到其他数字就加入答案。其中一个实现还用 \(H(2)\) 与 \(H(3)\) 的精确闭式对这一流程做了交叉验证。
真正的计算量不在“做很多步递推”，而在“计算一个固定大小的解析公式”。高精度三角函数、对数函数和指数函数的求值是主要成本，但它们不随 \(n\) 以组合爆炸的方式增长。
如果需要提取的非 6 数字个数为 \(D\)，那么数字提取阶段的时间复杂度是 \(O(D)\)，空间复杂度也是 \(O(D)\)。这里 \(D=8\)，因此整体求解在实践中可以视为常数时间、常数空间。
Кенгуру стартует из точки 0, а длина каждого прыжка независима и равномерно распределена на \([0,1]\). Пусть \(H(x)\) обозначает математическое ожидание числа прыжков, необходимых, чтобы достичь точки \(x\) или перелететь через нее. Нужно найти первые восемь цифр после десятичной точки в числе \(H(10^6)\), которые не равны 6.
Прямое вычисление по исходной рекурсии здесь не подходит. Для больших целых \(n\) дробная часть \(H(n)\) чрезвычайно близка к \(0.6666\ldots\). Значит, задача сводится к тому, чтобы определить, где именно эта длинная цепочка шестерок впервые нарушается и какие первые не-6 цифры там появляются.
Решение опирается на точное уравнение обновления, преобразование Лапласа и вклад доминирующей пары комплексных полюсов.
Если \(x\le 0\), дополнительных прыжков не требуется, поэтому \(H(x)=0\). Для \(x>0\) пусть длина первого прыжка равна \(U\sim \mathrm{Unif}[0,1]\). Тогда в среднем остается \(H(x-U)\) прыжков, и потому
$$H(x)=1+\int_0^1 H(x-u)\,du,$$
где принято \(H(y)=0\) при \(y\le 0\). Именно это уравнение лежит в основе реализованного метода.
Дифференцирование дает
$$H'(x)=H(x)-H(x-1)\qquad (x>0).$$
На интервале \(0<x<1\) член \(H(x-1)\) равен нулю, так что \(H'(x)=H(x)\) и \(H(0^+)=1\). Следовательно,
$$H(x)=e^x\qquad (0\le x\le 1).$$
На интервале \(1<x<2\) получаем
$$H(x)=e^x-(x-1)e^{x-1}\qquad (1\le x\le 2),$$
и, в частности,
$$H(2)=e^2-e.$$
Продолжая тот же поинтервальный расчет, получаем также
$$H(3)=e^3-2e^2+\frac{e}{2}.$$
Эти формулы полезны не только как пример: они служат точными контрольными точками для проверки извлечения цифр.
Положим
$$F(s)=\int_0^\infty H(x)e^{-sx}\,dx.$$
После преобразования Лапласа уравнение обновления принимает вид
$$F(s)=\frac1s+\frac{1-e^{-s}}sF(s),$$
откуда
$$F(s)=\frac{1}{s-1+e^{-s}}.$$
Знаменатель имеет двойной нуль в точке \(s=0\), поскольку
$$s-1+e^{-s}=\frac{s^2}{2}-\frac{s^3}{6}+O(s^4).$$
Значит, в окрестности нуля
$$F(s)=\frac{2}{s^2}+\frac{2}{3s}+O(1),$$
а после обратного преобразования
$$H(x)=2x+\frac23+\text{экспоненциально малые колебательные члены}.$$
Для целого \(n\) слагаемое \(2n\) не влияет на дробную часть, поэтому десятичное поведение определяется числом \(2/3\) и очень маленькой поправкой.
Остальные члены возникают из ненулевых корней уравнения
$$s-1+e^{-s}=0.$$
Переписывая его как \((s-1)e^s=-1\), получаем
$$s=1+W_k(-e^{-1}),$$
где \(W_k\) обозначает ветвь функции Ламберта \(W\). Ближайшие ненулевые корни образуют сопряженную пару
$$\lambda=\alpha+i\beta,\qquad \bar{\lambda}=\alpha-i\beta,$$
причем
$$\alpha\approx -2.08884301561304,\qquad \beta\approx 7.46148928565425.$$
Если \(p\neq 0\) является корнем, то вычет \(F(s)\) в точке \(p\) равен \(1/p\), потому что производная знаменателя в корне равна \(1-e^{-p}=p\). Поэтому доминирующая поправка при целом \(n\) имеет вид
$$\varepsilon_n \approx \frac{e^{\lambda n}}{\lambda}+\frac{e^{\bar{\lambda} n}}{\bar{\lambda}}=\frac{2\big(\alpha\cos(\beta n)+\beta\sin(\beta n)\big)}{\alpha^2+\beta^2}e^{\alpha n}.$$
Итак,
$$H(n)=2n+\frac23+\varepsilon_n+\text{еще меньшие члены},$$
а поскольку \(\alpha<0\), эта поправка затухает экспоненциально быстро.
Реализация не выписывает гигантский десятичный префикс. Вместо этого она вычисляет
$$\log_{10}|\varepsilon_n|=\frac{\alpha n}{\ln 10}+\log_{10}\left|\frac{2\big(\alpha\cos(\beta n)+\beta\sin(\beta n)\big)}{\alpha^2+\beta^2}\right|.$$
Если
$$-\log_{10}|\varepsilon_n|=m+\theta,\qquad m=\lfloor -\log_{10}|\varepsilon_n|\rfloor,\quad 0\le \theta<1,$$
то
$$\varepsilon_n=\sigma 10^{-m-\theta},\qquad \sigma\in\{-1,1\}.$$
Значит, первое отклонение от \(0.6666\ldots\) происходит примерно на \(m\)-й десятичной позиции. Далее программа берет \(t=\sigma 10^{-\theta}\), записывает
$$\frac23+t=q+r,\qquad q=\left\lfloor \frac23+t\right\rfloor,\quad 0\le r<1,$$
использует \(q\) как перенос или заем для короткого искусственного хвоста из шестерок, а затем продолжает считывать цифры из дробной части \(r\). Все цифры, равные 6, пропускаются; остальные добавляются в ответ, пока не наберется восемь штук.
Реализации на C++, Python и Java вычисляют одну и ту же асимптотическую формулу с высокой точностью. Они хранят константы \(\alpha\) и \(\beta\), уменьшают угол \(\beta n\) по модулю \(2\pi\), а затем находят тригонометрическую огибающую, которая умножается на \(e^{\alpha n}\).
Главный численный прием состоит в том, что код работает не с самой микроскопической величиной \(\varepsilon_n\), а с \(\log_{10}|\varepsilon_n|\). Это сразу показывает, сколько шестерок идет перед первой измененной цифрой, не требуя хранения громадного префикса.
После этого строится короткий десятичный хвост, изначально заполненный шестерками, к нему применяется возможный перенос или заем из \(q\), а затем дописываются цифры дробной части \(r\). Если очередная цифра равна 6, она отбрасывается; если нет, добавляется к ответу. В одной из реализаций этот механизм дополнительно проверяется на точных формулах для \(H(2)\) и \(H(3)\).
Здесь нет длинного динамического прохода до \(10^6\): вся трудная математика упакована в аналитическую формулу постоянного размера. Основные затраты связаны с высокоточным вычислением тригонометрических, логарифмических и экспоненциальных функций, но не с ростом \(n\) как параметра перебора.
Если нужно получить \(D\) цифр, отличных от 6, то этап извлечения занимает \(O(D)\) времени и \(O(D)\) памяти. В данной задаче \(D=8\), поэтому практически весь расчет имеет постоянную сложность.
يبدأ الكنغر من الموضع 0، وطول كل قفزة مستقل ويتبع توزيعًا منتظمًا على الفترة \([0,1]\). لتكن \(H(x)\) هي القيمة المتوقعة لعدد القفزات اللازمة للوصول إلى الموضع \(x\) أو تجاوزه. المطلوب هو استخراج أول ثمانية أرقام بعد الفاصلة في \(H(10^6)\) لا تساوي 6.
ليس من العملي حل علاقة التوقع الأصلية مباشرة حتى هذا الحجم. الحقيقة الأساسية هي أن الجزء الكسري من \(H(n)\) عندما يكون \(n\) عددًا صحيحًا كبيرًا يكون قريبًا جدًا من \(0.6666\ldots\). لذلك فجوهر المسألة هو تحديد الموضع الذي تنكسر عنده هذه السلسلة الطويلة من الستات، ثم قراءة أول الأرقام غير 6 التي تظهر هناك.
الحل يجمع بين معادلة تجديد دقيقة، وتحويل لابلاس، ومساهمة زوج القطبين العقديين المسيطرين.
إذا كان \(x\le 0\)، فلا حاجة إلى أي قفزة إضافية، ولذلك \(H(x)=0\). أما إذا كان \(x>0\)، ولتكن القفزة الأولى ذات طول \(U\sim \mathrm{Unif}[0,1]\)، فالمتبقي في المتوسط هو \(H(x-U)\). ومن ثم نحصل على
$$H(x)=1+\int_0^1 H(x-u)\,du,$$
مع الاتفاق على أن \(H(y)=0\) عندما \(y\le 0\). هذه هي البنية الدقيقة التي تعتمد عليها جميع التطبيقات.
باشتقاق المعادلة السابقة نحصل على
$$H'(x)=H(x)-H(x-1)\qquad (x>0).$$
على الفترة \(0<x<1\) يختفي الحد \(H(x-1)\)، فتكون \(H'(x)=H(x)\) ومع الشرط \(H(0^+)=1\) ينتج
$$H(x)=e^x\qquad (0\le x\le 1).$$
وعلى الفترة \(1<x<2\) نحصل على
$$H(x)=e^x-(x-1)e^{x-1}\qquad (1\le x\le 2),$$
ومنها مباشرة
$$H(2)=e^2-e.$$
وبتكرار التحليل على الفترة التالية نحصل أيضًا على
$$H(3)=e^3-2e^2+\frac{e}{2}.$$
هذه القيم ليست مجرد أمثلة توضيحية، بل نقاط تحقق حقيقية لمرحلة استخراج الأرقام.
لنعرّف
$$F(s)=\int_0^\infty H(x)e^{-sx}\,dx.$$
عند تطبيق تحويل لابلاس على معادلة التجديد نجد
$$F(s)=\frac1s+\frac{1-e^{-s}}sF(s),$$
ومن ثم
$$F(s)=\frac{1}{s-1+e^{-s}}.$$
للمقام جذر مزدوج عند \(s=0\)، لأن
$$s-1+e^{-s}=\frac{s^2}{2}-\frac{s^3}{6}+O(s^4).$$
إذن قرب الصفر لدينا
$$F(s)=\frac{2}{s^2}+\frac{2}{3s}+O(1),$$
وبعد التحويل العكسي نحصل على
$$H(x)=2x+\frac23+\delta(x),\qquad \delta(x)=O(e^{cx}),\ c<0.$$
وعندما يكون \(n\) عددًا صحيحًا، فإن الحد \(2n\) لا يؤثر في الجزء الكسري، لذلك يبقى \(2/3\) مع تصحيح صغير جدًا هو الذي يحدد السلوك العشري.
بقية الحدود تأتي من الجذور غير الصفرية للمعادلة
$$s-1+e^{-s}=0.$$
وبإعادة كتابتها على الصورة \((s-1)e^s=-1\) نحصل على
$$s=1+W_k(-e^{-1}),$$
حيث \(W_k\) أحد فروع دالة Lambert \(W\). أقرب الجذور غير الصفرية تشكل زوجًا مترافقًا
$$\lambda=\alpha+i\beta,\qquad \bar{\lambda}=\alpha-i\beta,$$
مع
$$\alpha\approx -2.08884301561304,\qquad \beta\approx 7.46148928565425.$$
إذا كان \(p\neq 0\) جذرًا، فإن بقايا \(F(s)\) عنده تساوي \(1/p\)، لأن مشتقة المقام عند الجذر هي \(1-e^{-p}=p\). لذلك يصبح التصحيح المسيطر عند عدد صحيح \(n\)
$$\varepsilon_n \approx \frac{e^{\lambda n}}{\lambda}+\frac{e^{\bar{\lambda} n}}{\bar{\lambda}}=\frac{2\big(\alpha\cos(\beta n)+\beta\sin(\beta n)\big)}{\alpha^2+\beta^2}e^{\alpha n}.$$
وبالتالي
$$H(n)=2n+\frac23+\varepsilon_n+o(\varepsilon_n),$$
ومادام \(\alpha<0\)، فإن هذا التصحيح يضمحل بسرعة أسية.
بدلًا من كتابة ذلك الذيل العشري الطويل، تحسب التطبيقات القيمة
$$\log_{10}|\varepsilon_n|=\frac{\alpha n}{\ln 10}+\log_{10}\left|\frac{2\big(\alpha\cos(\beta n)+\beta\sin(\beta n)\big)}{\alpha^2+\beta^2}\right|.$$
إذا كان
$$-\log_{10}|\varepsilon_n|=m+\theta,\qquad m=\lfloor -\log_{10}|\varepsilon_n|\rfloor,\quad 0\le \theta<1,$$
فإن
$$\varepsilon_n=\sigma 10^{-m-\theta},\qquad \sigma\in\{-1,1\}.$$
هذا يعني أن أول انحراف عن \(0.6666\ldots\) يحدث تقريبًا عند الخانة العشرية رقم \(m\). بعد ذلك تأخذ الخوارزمية \(t=\sigma 10^{-\theta}\)، وتكتب
$$\frac23+t=q+r,\qquad q=\left\lfloor \frac23+t\right\rfloor,\quad 0\le r<1,$$
ثم تستخدم \(q\) بوصفه حملًا أو استلافًا على ذيل قصير اصطناعي مكوّن من الستات، وبعد ذلك تتابع استخراج الأرقام من الجزء الكسري \(r\). كل رقم يساوي 6 يُتجاهل، وكل رقم آخر يُضاف حتى نصل إلى ثمانية أرقام.
تطبّق نسخ C++ وPython وJava الصيغة التقاربية نفسها باستخدام حسابات عالية الدقة. فهي تخزّن الثابتين \(\alpha\) و\(\beta\)، وتختزل الزاوية \(\beta n\) modulo \(2\pi\)، ثم تحسب الغلاف المثلثي الذي يرافق العامل \(e^{\alpha n}\).
الفكرة العددية الأساسية هي العمل مع \(\log_{10}|\varepsilon_n|\) بدلًا من \(\varepsilon_n\) نفسه. بهذه الطريقة نعرف مباشرة كم عدد الستات التي تسبق أول رقم متغير، من غير أن نولّد ذلك المقطع الطويل فعليًا.
بعد تحديد الموضع، يبني التنفيذ ذيلًا عشريًا قصيرًا مملوءًا بالستات، ويطبّق الحمل أو الاستلاف الناتج عن \(q\)، ثم يواصل القراءة من الأرقام العشرية في \(r\). أي رقم يساوي 6 يُهمل، وأي رقم آخر يُضاف إلى الناتج. كما أن إحدى النسخ تتحقق من صحة هذه الآلية باستخدام الصيغ الدقيقة لـ \(H(2)\) و\(H(3)\).
لا توجد هنا محاكاة طويلة أو تكرار حتى \(10^6\) بالمعنى المباشر؛ بل تُختزل المسألة في صيغة تحليلية ذات حجم ثابت. الجزء الأكبر من الكلفة يأتي من الحسابات عالية الدقة للدوال الأسية واللوغاريتمية والمثلثية، لكنه لا ينمو نموًا تركيبيًا مع \(n\).
إذا كان عدد الأرقام غير 6 المطلوبة هو \(D\)، فإن مرحلة الاستخراج تكلف \(O(D)\) زمنًا و\(O(D)\) ذاكرة. وهنا \(D=8\)، لذا فالحساب كله عمليًا ثابت الكلفة.