There are \(n\) chairs arranged in a circle. People sit down one after another, and each step chooses uniformly among the chairs that are still legal: a legal chair is unoccupied and not adjacent to an occupied chair. The process stops when no legal chair remains. The quantity of interest is the expected fraction of chairs that stay empty at the end.
The implementations verify the small checkpoints
$$E(4)=\frac12,\qquad E(6)=\frac59,$$
and then evaluate the actual target \(n=10^{18}\). A direct state-space analysis is hopeless, so the solution rewrites the process in terms of an expectation on a path and then solves that expectation in closed form.
Let \(C(n)\) be the expected number of occupied chairs when the process runs on a cycle of length \(n\), and let \(E(n)\) be the expected empty-chair fraction:
$$E(n)=1-\frac{C(n)}{n}.$$
The core idea is that after the first occupied chair is chosen on the cycle, the remaining legal chairs form a simple path. That reduces the random process to a one-dimensional recurrence.
Define \(P(m)\) as the expected number of occupied chairs produced by the same seating rule on a path of \(m\) chairs.
On a cycle of length \(n\), the first occupied chair contributes \(1\). Its two neighbors can never be occupied, so the remaining legal region is a path of length \(n-3\). Therefore, for \(n\ge 3\),
$$C(n)=1+P(n-3).$$
Hence the desired empty fraction is
$$E(n)=1-\frac{1+P(n-3)}{n}.$$
The small cases are consistent with this picture: \(E(1)=0\), \(E(2)=\frac12\), and \(E(3)=\frac23\).
Now consider a path of \(m\) chairs. Suppose the first occupied chair is the \(j\)-th chair, where \(1\le j\le m\). Then chairs \(j-1\), \(j\), and \(j+1\) are no longer usable, so the process splits into two independent smaller paths:
$$j-2,\qquad m-j-1.$$
Taking expectations and averaging uniformly over the first choice gives
$$P(m)=1+\frac{1}{m}\sum_{j=1}^{m}\bigl(P(j-2)+P(m-j-1)\bigr).$$
Using symmetry, both sums are the same, so this simplifies to
$$P(m)=1+\frac{2}{m}\sum_{r=0}^{m-2}P(r),\qquad P(0)=0.$$
This is the main recurrence behind the exact formula.
Introduce the ordinary generating function
$$F(x)=\sum_{m\ge 0}P(m)x^m.$$
Multiply the recurrence by \(m x^{m-1}\) and sum over \(m\ge 1\). The left side becomes \(F'(x)\). The right side becomes
$$\sum_{m\ge 1}m x^{m-1}=\frac{1}{(1-x)^2},$$
and
$$\sum_{m\ge 1}\sum_{r=0}^{m-2}P(r)x^{m-1}=\frac{xF(x)}{1-x}.$$
Therefore \(F\) satisfies the linear differential equation
$$F'(x)=\frac{1}{(1-x)^2}+\frac{2x}{1-x}F(x),\qquad F(0)=0.$$
Solving it gives the exact generating function
$$F(x)=\frac{1-e^{-2x}}{2(1-x)^2}.$$
Write
$$e^{-2x}=\sum_{k\ge 0}\frac{(-2)^k}{k!}x^k,$$
and define the alternating partial sums
$$S_m=\sum_{k=0}^{m}\frac{(-2)^k}{k!}.$$
From
$$F(x)=\frac{1}{2(1-x)^2}-\frac{e^{-2x}}{2(1-x)^2},$$
the coefficient of \(x^m\) is
$$P(m)=\frac{m+1}{2}-\frac12\sum_{k=0}^{m}(m-k+1)\frac{(-2)^k}{k!}.$$
Using
$$\sum_{k=0}^{m}k\frac{(-2)^k}{k!}=-2\sum_{k=0}^{m-1}\frac{(-2)^k}{k!}=-2S_{m-1},$$
this becomes
$$\boxed{P(m)=\frac{m+1}{2}-\frac{m+1}{2}S_m-S_{m-1}.}$$
This is exactly the finite-\(n\) formula used by the exact implementation.
Substituting \(m=n-3\) into the cycle relation yields, for \(n\ge 4\),
$$E(n)=1-\frac{1+P(n-3)}{n}.$$
Because \(S_m\to e^{-2}\) as \(m\to\infty\), we obtain
$$P(m)=\frac{m+1}{2}\bigl(1-e^{-2}\bigr)-e^{-2}+o(1).$$
Hence
$$\lim_{n\to\infty}E(n)=1-\frac{1}{2}\bigl(1-e^{-2}\bigr)=\boxed{\frac{1+e^{-2}}{2}}.$$
This limit is the value needed for the huge target \(n=10^{18}\).
For a cycle of length \(6\), the first occupied chair leaves a path of length \(3\). We compute \(P(3)\) from the recurrence.
First, \(P(0)=0\), \(P(1)=1\), and \(P(2)=1\). Then
$$P(3)=1+\frac{2}{3}\bigl(P(0)+P(1)\bigr)=1+\frac{2}{3}=\frac{5}{3}.$$
So the expected number of occupied chairs on the cycle is
$$C(6)=1+P(3)=1+\frac{5}{3}=\frac{8}{3}.$$
Therefore the expected empty fraction is
$$E(6)=1-\frac{C(6)}{6}=1-\frac{8/3}{6}=1-\frac49=\frac59,$$
which matches the checkpoint used by the implementation.
The C++, Python, and Java implementations are built around the closed form above. The exact evaluation only needs the alternating partial sums \(S_m\), so the terms are generated iteratively by
$$t_0=1,\qquad t_k=t_{k-1}\cdot\frac{-2}{k},\qquad S_m=\sum_{k=0}^{m}t_k.$$
This avoids factorial overflow and keeps the computation in constant memory.
The C++ implementation handles the small cases explicitly, evaluates the exact finite-\(n\) formula for moderate \(n\), checks the known values \(E(4)=\frac12\) and \(E(6)=\frac59\), and then switches to the limit \(\frac{1+e^{-2}}{2}\) once \(n\) is large enough that the truncated-tail error is far below the printed precision.
The Python and Java implementations target the actual Euler input directly. Since that input is enormous, they compute the limiting constant immediately and print it to 14 decimal places.
For the exact finite-\(n\) evaluation, computing \(S_m\) up to \(m=n-3\) takes \(O(n)\) time and \(O(1)\) memory, because only the current series term and running sum are stored. For the huge target value, the asymptotic formula is used directly, so the runtime is \(O(1)\) and the memory usage remains \(O(1)\).
Es gibt \(n\) Stühle auf einem Kreis. Personen setzen sich nacheinander, und in jedem Schritt wird gleichverteilt unter den noch zulässigen Stühlen gewählt. Zulässig ist ein Stuhl genau dann, wenn er frei ist und nicht neben einem bereits besetzten Stuhl liegt. Der Prozess endet, sobald kein zulässiger Stuhl mehr existiert. Gesucht ist der erwartete Anteil der am Ende leeren Stühle.
Die Implementierungen prüfen dabei die Kontrollwerte
$$E(4)=\frac12,\qquad E(6)=\frac59,$$
und berechnen dann den eigentlichen Zielwert für \(n=10^{18}\). Eine direkte Zustandsanalyse wäre viel zu groß, deshalb formt die Lösung das Kreisproblem in eine Erwartung auf einem Pfad um und löst diese Erwartung exakt.
Sei \(C(n)\) die erwartete Anzahl besetzter Stühle bei einem Kreis der Länge \(n\). Der gesuchte Leerstuhl-Anteil ist dann
$$E(n)=1-\frac{C(n)}{n}.$$
Die Schlüsselerkenntnis lautet: Nach der ersten Besetzung auf dem Kreis bleibt als zulässiger Rest kein neuer Kreis, sondern ein einfacher Pfad übrig.
Definiere \(P(m)\) als die erwartete Anzahl besetzter Stühle beim gleichen Zufallsprozess auf einem Pfad mit \(m\) Stühlen.
Wird auf dem Kreis der erste Stuhl besetzt, so zählt das bereits \(1\). Seine beiden Nachbarn können anschließend nie mehr besetzt werden. Übrig bleibt deshalb ein zusammenhängender Pfad der Länge \(n-3\). Also gilt für \(n\ge 3\)
$$C(n)=1+P(n-3).$$
Damit folgt sofort
$$E(n)=1-\frac{1+P(n-3)}{n}.$$
Die kleinen Fälle passen dazu: \(E(1)=0\), \(E(2)=\frac12\) und \(E(3)=\frac23\).
Betrachte nun einen Pfad mit \(m\) Stühlen. Sei der zuerst besetzte Stuhl die Position \(j\) mit \(1\le j\le m\). Dann sind \(j-1\), \(j\) und \(j+1\) nicht mehr verwendbar. Der Rest zerfällt in zwei unabhängige kleinere Pfade mit Längen
$$j-2,\qquad m-j-1.$$
Nimmt man darüber den Erwartungswert und mittelt gleichverteilt über alle möglichen ersten Positionen, erhält man
$$P(m)=1+\frac{1}{m}\sum_{j=1}^{m}\bigl(P(j-2)+P(m-j-1)\bigr).$$
Wegen Symmetrie sind beide Summen identisch, also
$$P(m)=1+\frac{2}{m}\sum_{r=0}^{m-2}P(r),\qquad P(0)=0.$$
Diese Rekurrenz ist der Ausgangspunkt der exakten geschlossenen Formel.
Wir führen die gewöhnliche erzeugende Funktion
$$F(x)=\sum_{m\ge 0}P(m)x^m$$
ein. Multipliziert man die Rekurrenz mit \(m x^{m-1}\) und summiert über \(m\ge 1\), so wird die linke Seite zu \(F'(x)\). Auf der rechten Seite entsteht
$$\sum_{m\ge 1}m x^{m-1}=\frac{1}{(1-x)^2}$$
sowie
$$\sum_{m\ge 1}\sum_{r=0}^{m-2}P(r)x^{m-1}=\frac{xF(x)}{1-x}.$$
Daher erfüllt \(F\) die lineare Differentialgleichung
$$F'(x)=\frac{1}{(1-x)^2}+\frac{2x}{1-x}F(x),\qquad F(0)=0.$$
Die Lösung lautet
$$F(x)=\frac{1-e^{-2x}}{2(1-x)^2}.$$
Schreibe
$$e^{-2x}=\sum_{k\ge 0}\frac{(-2)^k}{k!}x^k$$
und definiere die alternierenden Partialsummen
$$S_m=\sum_{k=0}^{m}\frac{(-2)^k}{k!}.$$
Aus
$$F(x)=\frac{1}{2(1-x)^2}-\frac{e^{-2x}}{2(1-x)^2}$$
folgt für den Koeffizienten von \(x^m\)
$$P(m)=\frac{m+1}{2}-\frac12\sum_{k=0}^{m}(m-k+1)\frac{(-2)^k}{k!}.$$
Mit der Identität
$$\sum_{k=0}^{m}k\frac{(-2)^k}{k!}=-2\sum_{k=0}^{m-1}\frac{(-2)^k}{k!}=-2S_{m-1}$$
wird daraus
$$\boxed{P(m)=\frac{m+1}{2}-\frac{m+1}{2}S_m-S_{m-1}.}$$
Genau diese Formel steckt in der exakten Berechnung.
Setzt man \(m=n-3\) ein, so erhält man für \(n\ge 4\)
$$E(n)=1-\frac{1+P(n-3)}{n}.$$
Da \(S_m\to e^{-2}\) für \(m\to\infty\), folgt asymptotisch
$$P(m)=\frac{m+1}{2}\bigl(1-e^{-2}\bigr)-e^{-2}+o(1).$$
Somit ergibt sich der Grenzwert
$$\lim_{n\to\infty}E(n)=1-\frac{1}{2}\bigl(1-e^{-2}\bigr)=\boxed{\frac{1+e^{-2}}{2}}.$$
Dieser Ausdruck ist genau der benötigte Wert für das riesige Ziel-\(n\).
Bei einem Kreis mit \(6\) Stühlen bleibt nach der ersten Besetzung ein Pfad der Länge \(3\). Also benötigen wir \(P(3)\).
Zunächst gilt \(P(0)=0\), \(P(1)=1\) und \(P(2)=1\). Dann liefert die Rekurrenz
$$P(3)=1+\frac{2}{3}\bigl(P(0)+P(1)\bigr)=1+\frac{2}{3}=\frac{5}{3}.$$
Die erwartete Zahl besetzter Stühle auf dem Kreis ist damit
$$C(6)=1+P(3)=\frac{8}{3}.$$
Folglich ist der erwartete Leerstuhl-Anteil
$$E(6)=1-\frac{8/3}{6}=1-\frac49=\frac59,$$
also genau der Kontrollwert der Implementierung.
Die C++, Python- und Java-Implementierungen basieren alle auf der obigen geschlossenen Formel. Für die exakte Auswertung werden nur die alternierenden Partialsummen \(S_m\) benötigt. Deshalb werden die Reihenterme iterativ über
$$t_0=1,\qquad t_k=t_{k-1}\cdot\frac{-2}{k},\qquad S_m=\sum_{k=0}^{m}t_k$$
erzeugt. Dadurch vermeidet die Berechnung Fakultätsüberläufe und benötigt nur konstanten Speicher.
Die C++-Implementierung behandelt die kleinsten Fälle separat, verwendet für moderate \(n\) die exakte Endlichkeitsformel, prüft die bekannten Werte \(E(4)=\frac12\) und \(E(6)=\frac59\), und schaltet für große \(n\) auf den Grenzwert \(\frac{1+e^{-2}}{2}\) um, weil der Restfehler dann deutlich unter der ausgegebenen Genauigkeit liegt.
Die Python- und Java-Implementierungen zielen direkt auf die eigentliche Euler-Eingabe. Da diese extrem groß ist, geben sie sofort die Grenzwertkonstante mit 14 Nachkommastellen aus.
Die exakte Endlichkeitsauswertung braucht \(O(n)\) Zeit, weil die Reihe bis \(m=n-3\) einmal durchlaufen wird. Der Speicherbedarf bleibt \(O(1)\), da nur der aktuelle Term und die laufende Summe gehalten werden. Für den riesigen Zielwert wird stattdessen direkt der Grenzwert verwendet; dann sind Laufzeit und Speicher jeweils \(O(1)\).
Bir çember üzerine yerleştirilmiş \(n\) sandalye vardır. İnsanlar sırayla oturur ve her adımda hâlâ yasal olan sandalyeler arasından eşit olasılıkla seçim yapılır. Bir sandalyenin yasal olması için hem boş olması hem de dolu bir sandalyeye komşu olmaması gerekir. Hiç yasal sandalye kalmadığında süreç durur. Aranan büyüklük, sonunda boş kalan sandalyelerin beklenen oranıdır.
Uygulamalar şu küçük doğrulamaları kullanır:
$$E(4)=\frac12,\qquad E(6)=\frac59,$$
ve sonra gerçek hedef olan \(n=10^{18}\) için değeri üretir. Doğrudan durum uzayını saymak mümkün olmadığı için çözüm, çemberi bir yol problemine indirger ve bu yeni beklentiyi kapalı formda çözer.
\(n\) uzunluklu çember üzerinde süreç bittiğinde dolu sandalye sayısının beklenen değerini \(C(n)\) ile gösterelim. O zaman boş sandalye oranı
$$E(n)=1-\frac{C(n)}{n}$$
olur. Temel fikir şudur: Çemberde ilk sandalye seçildikten sonra geriye kalan kullanılabilir bölge yine çember değil, tek parça bir yol olur.
Aynı oturma kuralı altında uzunluğu \(m\) olan bir yol üzerindeki beklenen dolu sandalye sayısını \(P(m)\) ile tanımlayalım.
Çemberde ilk seçilen sandalye doğrudan \(1\) katkı yapar. Bu sandalyenin iki komşusu artık sonsuza kadar kullanılamaz. Böylece geriye uzunluğu \(n-3\) olan bir yol kalır. Dolayısıyla \(n\ge 3\) için
$$C(n)=1+P(n-3).$$
Bundan hemen
$$E(n)=1-\frac{1+P(n-3)}{n}$$
elde edilir. Küçük örnekler de tutarlıdır: \(E(1)=0\), \(E(2)=\frac12\), \(E(3)=\frac23\).
Şimdi \(m\) sandalyeli bir yol düşünelim. İlk dolan sandalye \(j\)-inci konum olsun; burada \(1\le j\le m\). Bu durumda \(j-1\), \(j\) ve \(j+1\) konumları artık kullanılamaz ve süreç iki bağımsız alt yola ayrılır:
$$j-2,\qquad m-j-1.$$
Beklenti alıp ilk seçim üzerinde ortalama alınca
$$P(m)=1+\frac{1}{m}\sum_{j=1}^{m}\bigl(P(j-2)+P(m-j-1)\bigr)$$
çıkar. Simetri nedeniyle iki toplam aynıdır; böylece
$$P(m)=1+\frac{2}{m}\sum_{r=0}^{m-2}P(r),\qquad P(0)=0$$
biçimine ulaşırız. Kapalı formun çıkış noktası tam olarak bu özyinelemedir.
Şimdi sıradan üreteç fonksiyonunu tanımlayalım:
$$F(x)=\sum_{m\ge 0}P(m)x^m.$$
Özyinelemeyi \(m x^{m-1}\) ile çarpıp \(m\ge 1\) için toplarsak sol taraf \(F'(x)\) olur. Sağ tarafta ise
$$\sum_{m\ge 1}m x^{m-1}=\frac{1}{(1-x)^2}$$
ve
$$\sum_{m\ge 1}\sum_{r=0}^{m-2}P(r)x^{m-1}=\frac{xF(x)}{1-x}$$
elde edilir. Sonuç olarak \(F\) şu lineer diferansiyel denklemi sağlar:
$$F'(x)=\frac{1}{(1-x)^2}+\frac{2x}{1-x}F(x),\qquad F(0)=0.$$
Bunun çözümü
$$F(x)=\frac{1-e^{-2x}}{2(1-x)^2}$$
şeklindedir.
Şunu yazalım:
$$e^{-2x}=\sum_{k\ge 0}\frac{(-2)^k}{k!}x^k,$$
ve alternanslı kısmi toplamları
$$S_m=\sum_{k=0}^{m}\frac{(-2)^k}{k!}$$
olarak tanımlayalım. Çünkü
$$F(x)=\frac{1}{2(1-x)^2}-\frac{e^{-2x}}{2(1-x)^2},$$
\(x^m\) katsayısı
$$P(m)=\frac{m+1}{2}-\frac12\sum_{k=0}^{m}(m-k+1)\frac{(-2)^k}{k!}$$
olur. Ayrıca
$$\sum_{k=0}^{m}k\frac{(-2)^k}{k!}=-2\sum_{k=0}^{m-1}\frac{(-2)^k}{k!}=-2S_{m-1}$$
kimliği kullanılırsa
$$\boxed{P(m)=\frac{m+1}{2}-\frac{m+1}{2}S_m-S_{m-1}}$$
sonucuna ulaşırız. Tam hesap yapan uygulama doğrudan bu formülü kullanır.
\(m=n-3\) yazarak \(n\ge 4\) için
$$E(n)=1-\frac{1+P(n-3)}{n}$$
elde edilir. \(m\to\infty\) iken \(S_m\to e^{-2}\) olduğundan
$$P(m)=\frac{m+1}{2}\bigl(1-e^{-2}\bigr)-e^{-2}+o(1)$$
ve dolayısıyla
$$\lim_{n\to\infty}E(n)=1-\frac{1}{2}\bigl(1-e^{-2}\bigr)=\boxed{\frac{1+e^{-2}}{2}}$$
bulunur. Çok büyük hedef \(n\) için gereken değer budur.
\(6\) sandalyeli çemberde ilk seçimden sonra uzunluğu \(3\) olan bir yol kalır. Bu yüzden \(P(3)\) gerekir.
Başlangıç değerleri \(P(0)=0\), \(P(1)=1\), \(P(2)=1\) olur. Özyineleme:
$$P(3)=1+\frac{2}{3}\bigl(P(0)+P(1)\bigr)=1+\frac{2}{3}=\frac{5}{3}.$$
Böylece çember üzerindeki beklenen dolu sandalye sayısı
$$C(6)=1+P(3)=\frac{8}{3}$$
olur. Beklenen boş oran ise
$$E(6)=1-\frac{8/3}{6}=1-\frac49=\frac59,$$
yani doğrulama değeriyle tam uyumludur.
C++, Python ve Java uygulamaları yukarıdaki kapalı formu temel alır. Tam sonlu-\(n\) hesabı için yalnızca \(S_m\) kısmi toplamları gerekir. Bu nedenle seri terimleri
$$t_0=1,\qquad t_k=t_{k-1}\cdot\frac{-2}{k},\qquad S_m=\sum_{k=0}^{m}t_k$$
özyinelemesiyle üretilir. Bu yaklaşım, faktöriyel taşmasını önler ve sabit bellek kullanır.
C++ uygulaması en küçük durumları ayrı ele alır, orta büyüklükteki \(n\) için tam formülü hesaplar, \(E(4)=\frac12\) ve \(E(6)=\frac59\) kontrollerini yapar, sonra \(n\) yeterince büyüdüğünde \(\frac{1+e^{-2}}{2}\) limitine geçer. Bunun nedeni, kesilmiş kuyruktan gelen hatanın yazdırılan hassasiyetin çok altında kalmasıdır.
Python ve Java uygulamaları doğrudan gerçek Euler girdisini hedefler. Bu giriş çok büyük olduğundan, onlar limit sabitini hemen hesaplayıp 14 ondalık basamakla yazdırır.
Sonlu-\(n\) için tam değerlendirme, seri \(m=n-3\) değerine kadar toplandığı için \(O(n)\) zaman alır. Bellek kullanımı \(O(1)\)'dir; yalnızca güncel terim ve kümülatif toplam tutulur. Devasa hedef değer için limit doğrudan kullanıldığından, hem zaman hem bellek \(O(1)\) olur.
Hay \(n\) sillas colocadas en un círculo. Las personas se sientan una tras otra, y en cada paso se elige uniformemente entre las sillas que siguen siendo válidas. Una silla es válida si está vacía y además no es adyacente a una silla ya ocupada. El proceso termina cuando ya no queda ninguna silla válida. La cantidad buscada es la fracción esperada de sillas que permanecen vacías al final.
Las implementaciones verifican primero
$$E(4)=\frac12,\qquad E(6)=\frac59,$$
y después evalúan el caso real \(n=10^{18}\). Un análisis directo de todos los estados es inviable, así que la solución transforma el problema circular en una expectativa sobre un camino y luego la resuelve en forma cerrada.
Sea \(C(n)\) el número esperado de sillas ocupadas cuando el proceso se ejecuta sobre un ciclo de longitud \(n\). Entonces la fracción esperada de sillas vacías es
$$E(n)=1-\frac{C(n)}{n}.$$
La idea central es que, después de elegir la primera silla ocupada en el círculo, la región restante de sillas utilizables deja de ser circular y se convierte en un camino lineal.
Definamos \(P(m)\) como el número esperado de sillas ocupadas bajo la misma regla cuando trabajamos sobre un camino de \(m\) sillas.
En un ciclo de longitud \(n\), la primera silla ocupada aporta \(1\). Sus dos vecinas quedan bloqueadas para siempre, de modo que la parte restante es un camino de longitud \(n-3\). Por tanto, para \(n\ge 3\),
$$C(n)=1+P(n-3).$$
De aquí se obtiene
$$E(n)=1-\frac{1+P(n-3)}{n}.$$
Los casos pequeños encajan con la misma idea: \(E(1)=0\), \(E(2)=\frac12\) y \(E(3)=\frac23\).
Consideremos ahora un camino de \(m\) sillas. Si la primera silla ocupada es la posición \(j\), con \(1\le j\le m\), entonces \(j-1\), \(j\) y \(j+1\) dejan de ser utilizables. El proceso se separa en dos caminos más pequeños e independientes de longitudes
$$j-2,\qquad m-j-1.$$
Promediando sobre la primera elección uniforme se obtiene
$$P(m)=1+\frac{1}{m}\sum_{j=1}^{m}\bigl(P(j-2)+P(m-j-1)\bigr).$$
Por simetría, ambas sumas coinciden, y por ello
$$P(m)=1+\frac{2}{m}\sum_{r=0}^{m-2}P(r),\qquad P(0)=0.$$
Esta es la recurrencia fundamental que luego se resuelve exactamente.
Introducimos la función generadora ordinaria
$$F(x)=\sum_{m\ge 0}P(m)x^m.$$
Multiplicamos la recurrencia por \(m x^{m-1}\) y sumamos para \(m\ge 1\). El lado izquierdo se convierte en \(F'(x)\). En el lado derecho aparecen
$$\sum_{m\ge 1}m x^{m-1}=\frac{1}{(1-x)^2}$$
y
$$\sum_{m\ge 1}\sum_{r=0}^{m-2}P(r)x^{m-1}=\frac{xF(x)}{1-x}.$$
Así, \(F\) satisface la ecuación diferencial lineal
$$F'(x)=\frac{1}{(1-x)^2}+\frac{2x}{1-x}F(x),\qquad F(0)=0.$$
Su solución exacta es
$$F(x)=\frac{1-e^{-2x}}{2(1-x)^2}.$$
Escribimos
$$e^{-2x}=\sum_{k\ge 0}\frac{(-2)^k}{k!}x^k,$$
y definimos las sumas parciales alternantes
$$S_m=\sum_{k=0}^{m}\frac{(-2)^k}{k!}.$$
Como
$$F(x)=\frac{1}{2(1-x)^2}-\frac{e^{-2x}}{2(1-x)^2},$$
el coeficiente de \(x^m\) vale
$$P(m)=\frac{m+1}{2}-\frac12\sum_{k=0}^{m}(m-k+1)\frac{(-2)^k}{k!}.$$
Usando la identidad
$$\sum_{k=0}^{m}k\frac{(-2)^k}{k!}=-2\sum_{k=0}^{m-1}\frac{(-2)^k}{k!}=-2S_{m-1},$$
llegamos a la fórmula cerrada
$$\boxed{P(m)=\frac{m+1}{2}-\frac{m+1}{2}S_m-S_{m-1}.}$$
Esta es precisamente la expresión finita que usa la evaluación exacta.
Sustituyendo \(m=n-3\), para \(n\ge 4\) obtenemos
$$E(n)=1-\frac{1+P(n-3)}{n}.$$
Como \(S_m\to e^{-2}\) cuando \(m\to\infty\), se tiene
$$P(m)=\frac{m+1}{2}\bigl(1-e^{-2}\bigr)-e^{-2}+o(1).$$
Por tanto,
$$\lim_{n\to\infty}E(n)=1-\frac{1}{2}\bigl(1-e^{-2}\bigr)=\boxed{\frac{1+e^{-2}}{2}}.$$
Ese es el valor que se necesita para el tamaño gigantesco del problema.
Para un ciclo de longitud \(6\), la primera silla ocupada deja un camino de longitud \(3\). Por ello necesitamos \(P(3)\).
Primero, \(P(0)=0\), \(P(1)=1\) y \(P(2)=1\). Luego la recurrencia da
$$P(3)=1+\frac{2}{3}\bigl(P(0)+P(1)\bigr)=1+\frac{2}{3}=\frac{5}{3}.$$
Así, el número esperado de sillas ocupadas en el ciclo es
$$C(6)=1+P(3)=\frac{8}{3}.$$
La fracción esperada de sillas vacías resulta
$$E(6)=1-\frac{8/3}{6}=1-\frac49=\frac59,$$
en perfecto acuerdo con el valor de comprobación.
Las implementaciones en C++, Python y Java se apoyan en la fórmula cerrada anterior. Para la evaluación exacta solo se necesitan las sumas parciales alternantes \(S_m\), así que los términos se generan de forma iterativa mediante
$$t_0=1,\qquad t_k=t_{k-1}\cdot\frac{-2}{k},\qquad S_m=\sum_{k=0}^{m}t_k.$$
Esto evita desbordamientos por factoriales y mantiene el uso de memoria constante.
La implementación en C++ trata por separado los casos más pequeños, evalúa la fórmula exacta para valores moderados de \(n\), verifica \(E(4)=\frac12\) y \(E(6)=\frac59\), y cuando \(n\) ya es suficientemente grande cambia a la constante límite \(\frac{1+e^{-2}}{2}\), porque el error restante queda muy por debajo de la precisión impresa.
Las implementaciones en Python y Java apuntan directamente al valor Euler real. Como ese \(n\) es enorme, calculan de inmediato la constante límite y la muestran con 14 cifras decimales.
La evaluación exacta para \(n\) finito requiere \(O(n)\) tiempo, ya que la serie se acumula hasta \(m=n-3\). La memoria es \(O(1)\), porque solo se guardan el término actual y la suma acumulada. Para el objetivo gigantesco se usa directamente la fórmula asintótica, de modo que tanto el tiempo como la memoria son \(O(1)\).
有 \(n\) 把椅子围成一个圆。人们依次入座，每一步都在当前仍然合法的椅子中等概率选择一把。所谓合法，指该椅子尚未被占用，并且不与任何已占用椅子相邻。当不存在合法椅子时，过程结束。题目要求的是最终空椅子所占比例的期望值。
实现中先验证两个已知检查点：
$$E(4)=\frac12,\qquad E(6)=\frac59,$$
随后再计算真正目标 \(n=10^{18}\)。如果直接按状态枚举或做大规模概率转移，规模会迅速爆炸，因此解法必须把随机过程压缩成一个更容易处理的一维期望问题。
记 \(C(n)\) 为圆形排列中最终被占用椅子数量的期望值，那么要求的空椅比例就是
$$E(n)=1-\frac{C(n)}{n}.$$
关键观察是：在圆上第一次选定一把椅子之后，剩余仍可能被继续选择的位置不再形成圆，而是形成一条直线段。这一点使得问题可以转化为“路径”上的同类随机过程。
定义 \(P(m)\) 为在长度为 \(m\) 的直线路径上，按照同样规则执行过程后，最终被占用椅子数量的期望值。
对于长度为 \(n\) 的圆，第一次入座的那把椅子显然贡献 \(1\)。它左右两侧的相邻椅子此后都不可能再被占用，因此被“切开”后剩下的是一段长度为 \(n-3\) 的路径。于是当 \(n\ge 3\) 时有
$$C(n)=1+P(n-3).$$
从而
$$E(n)=1-\frac{1+P(n-3)}{n}.$$
小规模边界也与这一图景一致：\(E(1)=0\)，\(E(2)=\frac12\)，\(E(3)=\frac23\)。
现在考虑一条有 \(m\) 把椅子的路径。若第一次被选中的位置是第 \(j\) 把椅子，其中 \(1\le j\le m\)，那么 \(j-1\)、\(j\)、\(j+1\) 三个位置都不再可用，剩余部分会裂成两个互不干扰的子路径，其长度分别为
$$j-2,\qquad m-j-1.$$
对首次选择做均匀平均，并利用期望的可加性，就得到
$$P(m)=1+\frac{1}{m}\sum_{j=1}^{m}\bigl(P(j-2)+P(m-j-1)\bigr).$$
由于左右两部分在求和后完全对称，上式可以简化为
$$P(m)=1+\frac{2}{m}\sum_{r=0}^{m-2}P(r),\qquad P(0)=0.$$
这就是整个精确解法的核心递推。
引入普通生成函数
$$F(x)=\sum_{m\ge 0}P(m)x^m.$$
将递推式两边同乘 \(m x^{m-1}\)，再对所有 \(m\ge 1\) 求和。左边正好变成 \(F'(x)\)。右边第一项给出
$$\sum_{m\ge 1}m x^{m-1}=\frac{1}{(1-x)^2},$$
而双重求和部分化为
$$\sum_{m\ge 1}\sum_{r=0}^{m-2}P(r)x^{m-1}=\frac{xF(x)}{1-x}.$$
因此 \(F(x)\) 满足一阶线性微分方程
$$F'(x)=\frac{1}{(1-x)^2}+\frac{2x}{1-x}F(x),\qquad F(0)=0.$$
求解后得到
$$F(x)=\frac{1-e^{-2x}}{2(1-x)^2}.$$
这一步把随机递推彻底转化成了一个可直接取系数的解析表达式。
把指数项展开为
$$e^{-2x}=\sum_{k\ge 0}\frac{(-2)^k}{k!}x^k,$$
并定义交错部分和
$$S_m=\sum_{k=0}^{m}\frac{(-2)^k}{k!}.$$
由
$$F(x)=\frac{1}{2(1-x)^2}-\frac{e^{-2x}}{2(1-x)^2}$$
可知 \(x^m\) 的系数为
$$P(m)=\frac{m+1}{2}-\frac12\sum_{k=0}^{m}(m-k+1)\frac{(-2)^k}{k!}.$$
再利用恒等式
$$\sum_{k=0}^{m}k\frac{(-2)^k}{k!}=-2\sum_{k=0}^{m-1}\frac{(-2)^k}{k!}=-2S_{m-1},$$
就能把它整理成实现中真正使用的有限公式：
$$\boxed{P(m)=\frac{m+1}{2}-\frac{m+1}{2}S_m-S_{m-1}.}$$
也就是说，只要能高效算出这些交错部分和，就能得到任意有限 \(n\) 的精确期望。
将 \(m=n-3\) 代回，就得到 \(n\ge 4\) 时的表达式
$$E(n)=1-\frac{1+P(n-3)}{n}.$$
另一方面，当 \(m\to\infty\) 时，交错部分和 \(S_m\) 收敛到 \(e^{-2}\)。因此
$$P(m)=\frac{m+1}{2}\bigl(1-e^{-2}\bigr)-e^{-2}+o(1).$$
把它代入空椅比例公式后，得到极限
$$\lim_{n\to\infty}E(n)=1-\frac{1}{2}\bigl(1-e^{-2}\bigr)=\boxed{\frac{1+e^{-2}}{2}}.$$
由于题目的目标 \(n\) 极大，这个极限值正是最终答案所依赖的常数。
当 \(n=6\) 时，圆上第一次入座以后，剩余可继续处理的是一条长度为 \(3\) 的路径，因此只需求 \(P(3)\)。
先有基本值 \(P(0)=0\)、\(P(1)=1\)、\(P(2)=1\)。于是递推给出
$$P(3)=1+\frac{2}{3}\bigl(P(0)+P(1)\bigr)=1+\frac{2}{3}=\frac{5}{3}.$$
所以圆上的期望占用数为
$$C(6)=1+P(3)=\frac{8}{3}.$$
最终空椅比例就是
$$E(6)=1-\frac{8/3}{6}=1-\frac49=\frac59,$$
与检查点完全一致。这个例子也清楚说明了“先切成路径，再算路径期望”的思路为什么有效。
C++、Python 和 Java 实现都围绕上述闭式展开。对于有限 \(n\) 的精确计算，真正需要的只是交错部分和 \(S_m\)。因此实现不会显式计算阶乘，而是按如下递推逐项更新：
$$t_0=1,\qquad t_k=t_{k-1}\cdot\frac{-2}{k},\qquad S_m=\sum_{k=0}^{m}t_k.$$
这种做法只保留当前项和累计和，所以空间是常数级，同时还能避免大阶乘带来的溢出问题。
C++ 实现覆盖了完整流程：先单独处理很小的 \(n\)，再对中等规模 \(n\) 使用精确有限公式，并用 \(E(4)=\frac12\) 与 \(E(6)=\frac59\) 做自检。当 \(n\) 足够大时，它直接改用极限常数 \(\frac{1+e^{-2}}{2}\)，因为此时由截断尾项带来的误差已经远低于最终输出的 14 位小数精度。
Python 和 Java 实现则更直接。由于它们面向的就是极大的实际目标 \(n=10^{18}\)，所以无需再走完整的有限 \(n\) 公式，而是直接计算并输出极限值。
若按有限 \(n\) 的精确公式计算，需要把级数累加到 \(m=n-3\)，因此时间复杂度为 \(O(n)\)。整个过程中只维护当前项与前缀和，所以空间复杂度为 \(O(1)\)。对于题目真正需要的超大 \(n\)，实现直接使用极限常数，时间复杂度降为 \(O(1)\)，空间复杂度仍为 \(O(1)\)。
Есть \(n\) стульев, расположенных по кругу. Люди садятся по одному, и на каждом шаге равновероятно выбирается один из еще допустимых стульев. Стул допустим, если он свободен и не соседствует с уже занятым стулом. Процесс заканчивается, когда допустимых мест больше не остается. Требуется найти математическое ожидание доли пустых стульев в конечной конфигурации.
Реализации проверяют контрольные значения
$$E(4)=\frac12,\qquad E(6)=\frac59,$$
а затем вычисляют величину для реального входа \(n=10^{18}\). Прямой перебор состояний невозможен, поэтому решение сводит задачу на цикле к задаче на пути и затем получает точную формулу.
Обозначим через \(C(n)\) ожидаемое число занятых стульев в цикле длины \(n\). Тогда искомая доля пустых стульев равна
$$E(n)=1-\frac{C(n)}{n}.$$
Главное наблюдение состоит в том, что после первого выбора на цикле оставшаяся разрешенная область имеет структуру не цикла, а обычного пути.
Пусть \(P(m)\) обозначает ожидаемое число занятых стульев при том же процессе, но уже на пути из \(m\) стульев.
На цикле первый занятый стул дает вклад \(1\). Его два соседа навсегда становятся недоступными, поэтому все, что остается, представляет собой путь длины \(n-3\). Значит, при \(n\ge 3\)
$$C(n)=1+P(n-3).$$
Отсюда сразу следует
$$E(n)=1-\frac{1+P(n-3)}{n}.$$
Малые случаи согласуются с этой формулой: \(E(1)=0\), \(E(2)=\frac12\), \(E(3)=\frac23\).
Рассмотрим путь из \(m\) стульев. Если первым выбран \(j\)-й стул, где \(1\le j\le m\), то позиции \(j-1\), \(j\) и \(j+1\) уже нельзя использовать. Процесс распадается на два независимых подотрезка длины
$$j-2,\qquad m-j-1.$$
Усредняя по равномерному выбору первого места, получаем
$$P(m)=1+\frac{1}{m}\sum_{j=1}^{m}\bigl(P(j-2)+P(m-j-1)\bigr).$$
Из симметрии двух сумм следует более компактная форма
$$P(m)=1+\frac{2}{m}\sum_{r=0}^{m-2}P(r),\qquad P(0)=0.$$
Это и есть базовая рекурсия, из которой выводится точная формула.
Введем обычную производящую функцию
$$F(x)=\sum_{m\ge 0}P(m)x^m.$$
Умножим рекурсию на \(m x^{m-1}\) и просуммируем по всем \(m\ge 1\). Левая часть станет \(F'(x)\). Правая часть даст
$$\sum_{m\ge 1}m x^{m-1}=\frac{1}{(1-x)^2}$$
и
$$\sum_{m\ge 1}\sum_{r=0}^{m-2}P(r)x^{m-1}=\frac{xF(x)}{1-x}.$$
Следовательно, \(F(x)\) удовлетворяет линейному дифференциальному уравнению
$$F'(x)=\frac{1}{(1-x)^2}+\frac{2x}{1-x}F(x),\qquad F(0)=0.$$
Его точное решение имеет вид
$$F(x)=\frac{1-e^{-2x}}{2(1-x)^2}.$$
Разложим экспоненту:
$$e^{-2x}=\sum_{k\ge 0}\frac{(-2)^k}{k!}x^k,$$
и введем частичные суммы
$$S_m=\sum_{k=0}^{m}\frac{(-2)^k}{k!}.$$
Из представления
$$F(x)=\frac{1}{2(1-x)^2}-\frac{e^{-2x}}{2(1-x)^2}$$
получаем коэффициент при \(x^m\):
$$P(m)=\frac{m+1}{2}-\frac12\sum_{k=0}^{m}(m-k+1)\frac{(-2)^k}{k!}.$$
Используя тождество
$$\sum_{k=0}^{m}k\frac{(-2)^k}{k!}=-2\sum_{k=0}^{m-1}\frac{(-2)^k}{k!}=-2S_{m-1},$$
приходим к формуле
$$\boxed{P(m)=\frac{m+1}{2}-\frac{m+1}{2}S_m-S_{m-1}.}$$
Именно это выражение используется в точном вычислении для конечного \(n\).
Подставляя \(m=n-3\), для \(n\ge 4\) получаем
$$E(n)=1-\frac{1+P(n-3)}{n}.$$
Так как \(S_m\to e^{-2}\) при \(m\to\infty\), имеем асимптотику
$$P(m)=\frac{m+1}{2}\bigl(1-e^{-2}\bigr)-e^{-2}+o(1).$$
Следовательно,
$$\lim_{n\to\infty}E(n)=1-\frac{1}{2}\bigl(1-e^{-2}\bigr)=\boxed{\frac{1+e^{-2}}{2}}.$$
Именно этот предел нужен для очень большого значения \(n\) в задаче.
Для цикла длины \(6\) после первого занятого стула остается путь длины \(3\). Значит, нужно вычислить \(P(3)\).
Базовые значения: \(P(0)=0\), \(P(1)=1\), \(P(2)=1\). Тогда рекурсия дает
$$P(3)=1+\frac{2}{3}\bigl(P(0)+P(1)\bigr)=1+\frac{2}{3}=\frac{5}{3}.$$
Ожидаемое число занятых стульев на цикле равно
$$C(6)=1+P(3)=\frac{8}{3}.$$
Поэтому доля пустых стульев составляет
$$E(6)=1-\frac{8/3}{6}=1-\frac49=\frac59,$$
что совпадает с контрольным значением.
Реализации на C++, Python и Java опираются на приведенную выше закрытую формулу. Для точного вычисления конечного случая нужны только частичные суммы \(S_m\), поэтому члены ряда строятся итеративно:
$$t_0=1,\qquad t_k=t_{k-1}\cdot\frac{-2}{k},\qquad S_m=\sum_{k=0}^{m}t_k.$$
Это избавляет от явного вычисления факториалов, предотвращает переполнение и требует лишь постоянной памяти.
Реализация на C++ отдельно обрабатывает совсем малые \(n\), затем использует точную конечную формулу для умеренных значений, проверяет \(E(4)=\frac12\) и \(E(6)=\frac59\), а при достаточно больших \(n\) переходит непосредственно к пределу \(\frac{1+e^{-2}}{2}\), потому что вклад отброшенного хвоста уже намного меньше печатаемой точности.
Реализации на Python и Java ориентированы сразу на реальный вход задачи. Поскольку он чрезвычайно велик, они просто вычисляют предельную константу и выводят ее с 14 знаками после запятой.
Точное вычисление для конечного \(n\) требует \(O(n)\) времени, так как нужно просуммировать ряд до \(m=n-3\). Память равна \(O(1)\), поскольку хранятся только текущий член и накопленная сумма. Для гигантского целевого значения используется сразу предельная формула, и тогда и время, и память становятся \(O(1)\).
لدينا \(n\) من الكراسي مرتبة على دائرة. يجلس الناس واحدًا بعد واحد، وفي كل خطوة يُختار كرسي بصورة منتظمة من بين الكراسي التي ما زالت قانونية. يكون الكرسي قانونيًا إذا كان فارغًا وغير مجاور لأي كرسي مشغول. تتوقف العملية عندما لا يبقى أي كرسي قانوني. المطلوب هو القيمة المتوقعة لنسبة الكراسي التي تبقى فارغة في النهاية.
تتحقق التطبيقات أولًا من القيمتين
$$E(4)=\frac12,\qquad E(6)=\frac59,$$
ثم تحسب القيمة للحالة الحقيقية \(n=10^{18}\). التحليل المباشر لجميع الحالات غير عملي إطلاقًا، ولذلك تعيد الحلول صياغة المسألة على دائرة إلى مسألة توقع على مسار خطي، ثم تستخرج صيغة مغلقة لذلك التوقع.
لنرمز بـ \(C(n)\) إلى العدد المتوقع للكراسي المشغولة في الترتيب الدائري ذي الطول \(n\). عندئذ تكون نسبة الكراسي الفارغة المتوقعة
$$E(n)=1-\frac{C(n)}{n}.$$
الفكرة الأساسية هي أن أول كرسي يُشغَل على الدائرة يقطع البنية الدائرية، لأن الكرسيين المجاورين له يصبحان غير قابلين للاستخدام، فيتبقى جزء خطي يمكن تحليله بتكرار أبسط.
نعرّف \(P(m)\) على أنه العدد المتوقع للكراسي المشغولة عندما نطبّق القاعدة نفسها على مسار طوله \(m\).
في دائرة طولها \(n\)، يضيف أول كرسي مشغول قيمة \(1\). بعد ذلك يصبح الجاران المباشران محجوبين نهائيًا، وما يبقى هو مسار طوله \(n-3\). لذلك، عندما \(n\ge 3\)، نحصل على
$$C(n)=1+P(n-3).$$
ومن ثم
$$E(n)=1-\frac{1+P(n-3)}{n}.$$
والحالات الصغيرة تنسجم مع ذلك: \(E(1)=0\)، و\(E(2)=\frac12\)، و\(E(3)=\frac23\).
الآن ننظر إلى مسار مكوّن من \(m\) كراسي. إذا كان أول كرسي يُشغَل هو الموضع \(j\)، حيث \(1\le j\le m\)، فإن المواضع \(j-1\) و\(j\) و\(j+1\) تصبح غير متاحة. وهكذا تنقسم العملية إلى مسارين مستقلين بطولين
$$j-2,\qquad m-j-1.$$
بأخذ التوقع ثم المتوسط على جميع الاختيارات الأولى الممكنة نحصل على
$$P(m)=1+\frac{1}{m}\sum_{j=1}^{m}\bigl(P(j-2)+P(m-j-1)\bigr).$$
وبسبب التناظر بين الجهتين تتبسط هذه الصيغة إلى
$$P(m)=1+\frac{2}{m}\sum_{r=0}^{m-2}P(r),\qquad P(0)=0.$$
هذه العلاقة الرجعية هي الأساس الذي تُشتق منه الصيغة الدقيقة.
نقدّم الدالة المولدة العادية
$$F(x)=\sum_{m\ge 0}P(m)x^m.$$
إذا ضربنا العلاقة السابقة في \(m x^{m-1}\) ثم جمعنا على جميع \(m\ge 1\)، فإن الطرف الأيسر يصبح \(F'(x)\). أما الطرف الأيمن فيعطي
$$\sum_{m\ge 1}m x^{m-1}=\frac{1}{(1-x)^2}$$
وكذلك
$$\sum_{m\ge 1}\sum_{r=0}^{m-2}P(r)x^{m-1}=\frac{xF(x)}{1-x}.$$
إذن تحقق \(F(x)\) المعادلة التفاضلية الخطية
$$F'(x)=\frac{1}{(1-x)^2}+\frac{2x}{1-x}F(x),\qquad F(0)=0.$$
وحلها هو
$$F(x)=\frac{1-e^{-2x}}{2(1-x)^2}.$$
نكتب
$$e^{-2x}=\sum_{k\ge 0}\frac{(-2)^k}{k!}x^k,$$
ونعرّف المجاميع الجزئية المتناوبة
$$S_m=\sum_{k=0}^{m}\frac{(-2)^k}{k!}.$$
ومن التمثيل
$$F(x)=\frac{1}{2(1-x)^2}-\frac{e^{-2x}}{2(1-x)^2}$$
يكون معامل \(x^m\) مساويًا لـ
$$P(m)=\frac{m+1}{2}-\frac12\sum_{k=0}^{m}(m-k+1)\frac{(-2)^k}{k!}.$$
وباستخدام الهوية
$$\sum_{k=0}^{m}k\frac{(-2)^k}{k!}=-2\sum_{k=0}^{m-1}\frac{(-2)^k}{k!}=-2S_{m-1},$$
نصل إلى الصيغة المغلقة
$$\boxed{P(m)=\frac{m+1}{2}-\frac{m+1}{2}S_m-S_{m-1}.}$$
وهذه هي الصيغة الدقيقة التي تعتمد عليها عملية الحساب في الحالة المنتهية.
بالتعويض \(m=n-3\) نحصل، عندما \(n\ge 4\)، على
$$E(n)=1-\frac{1+P(n-3)}{n}.$$
ولأن \(S_m\to e^{-2}\) عندما \(m\to\infty\)، فإن
$$P(m)=\frac{m+1}{2}\bigl(1-e^{-2}\bigr)-e^{-2}+o(1).$$
ومن ثم تكون النهاية
$$\lim_{n\to\infty}E(n)=1-\frac{1}{2}\bigl(1-e^{-2}\bigr)=\boxed{\frac{1+e^{-2}}{2}}.$$
وهذه القيمة الحدية هي التي نحتاجها عندما يكون \(n\) هائلًا كما في المسألة الأصلية.
عندما \(n=6\)، فإن أول كرسي يُشغَل يترك بعده مسارًا بطول \(3\). لذلك يكفي أن نحسب \(P(3)\).
لدينا أولًا \(P(0)=0\)، و\(P(1)=1\)، و\(P(2)=1\). ومن العلاقة الرجعية نحصل على
$$P(3)=1+\frac{2}{3}\bigl(P(0)+P(1)\bigr)=1+\frac{2}{3}=\frac{5}{3}.$$
إذن العدد المتوقع للكراسي المشغولة على الدائرة هو
$$C(6)=1+P(3)=\frac{8}{3}.$$
وعليه تكون نسبة الكراسي الفارغة
$$E(6)=1-\frac{8/3}{6}=1-\frac49=\frac59,$$
وهو بالضبط مقدار التحقق المعروف.
تعتمد تطبيقات C++ وPython وJava جميعًا على الصيغة المغلقة السابقة. في الحساب الدقيق للحالة المنتهية لا نحتاج إلا إلى المجاميع الجزئية \(S_m\)، ولهذا تُولَّد حدود السلسلة تكراريًا وفقًا للعلاقة
$$t_0=1,\qquad t_k=t_{k-1}\cdot\frac{-2}{k},\qquad S_m=\sum_{k=0}^{m}t_k.$$
وهذا يتجنب حساب المضروب صراحة، ويمنع تجاوز السعة، ويحافظ على استعمال ثابت للذاكرة.
تتعامل نسخة C++ مع القيم الصغيرة جدًا بصورة منفصلة، ثم تستخدم الصيغة الدقيقة للقيم المتوسطة من \(n\)، وتتحقق من \(E(4)=\frac12\) و\(E(6)=\frac59\)، وبعد ذلك تنتقل إلى الثابت الحدي \(\frac{1+e^{-2}}{2}\) عندما يصبح \(n\) كبيرًا بما يكفي، لأن خطأ ذيل السلسلة عندئذ يصبح أصغر بكثير من الدقة المطبوعة.
أما نسختا Python وJava فتستهدفان مباشرة قيمة أويلر الفعلية. وبما أن \(n=10^{18}\) ضخم جدًا، فهما تحسبان الثابت الحدي فورًا وتطبعانه مع 14 منزلة عشرية.
في التقييم الدقيق للحالة المنتهية نحتاج إلى جمع السلسلة حتى \(m=n-3\)، ولذلك يكون الزمن \(O(n)\). أما الذاكرة فتبقى \(O(1)\)، لأننا نحتفظ فقط بالحد الحالي والمجموع الجاري. وبالنسبة إلى قيمة الهدف العملاقة تُستخدم الصيغة الحدية مباشرة، فيصبح كل من الزمن والذاكرة \(O(1)\).