Let \(P_N\) be the set of primes not exceeding \(N\), with \(N=10^8\). One prime is chosen uniformly at random. We then try to guess its binary expansion one bit at a time, starting from the least significant bit.
After each guess, the true next bit is effectively revealed because the candidate set is restricted to primes sharing the observed suffix. A correct guess scores one point. The goal is to maximize the expected total score, so the problem is really about making the best local decision at every partially revealed binary suffix.
The natural state space is a binary trie built from reversed binary representations. Each node corresponds to a suffix of already revealed low bits, so every decision can be expressed in terms of how many remaining primes continue with bit \(0\) and how many continue with bit \(1\).
Write a prime \(p\) in binary as
$$p=\sum_{d=0}^{\ell(p)-1} b_d(p)\,2^d,\qquad b_d(p)\in\{0,1\},\qquad b_{\ell(p)-1}(p)=1.$$
The game reveals bits in the order \(b_0(p),b_1(p),b_2(p),\dots\), so a state is determined by an already known suffix \(s\) of low bits. A trie over these reversed bit strings stores exactly the primes compatible with each suffix.
If \(S(s)\) denotes the set of primes whose reversed binary expansion begins with \(s\), then reaching node \(s\) means that the hidden prime is known to lie in \(S(s)\).
At a trie node \(s\), let \(c(s)=|S(s)|\). Some primes end exactly at that node because their entire binary expansion has already been consumed. Let \(t(s)\) be that terminal count, and define
$$q(s)=c(s)-t(s).$$
Only those \(q(s)\) primes require another guess. If \(q(s)=0\), then the game is already over for every prime in that state, so the remaining expected score is \(0\).
Now look at the two child states \(s^{(0)}\) and \(s^{(1)}\), obtained by appending the next revealed bit. Let \(c_0(s)\) and \(c_1(s)\) be the numbers of compatible primes in those two children. Because every continuing prime must go to exactly one child, we have
$$c_0(s)+c_1(s)=q(s).$$
Suppose we are at state \(s\) and must guess the next bit. Choosing \(0\) or \(1\) changes only the score of the current round. It does not change which child state is reached, because that depends on the hidden prime, not on our guess.
Therefore the optimal policy at node \(s\) is simply to guess the more common next bit among the continuing primes. The best immediate success probability is
$$\frac{\max(c_0(s),c_1(s))}{q(s)}.$$
This greedy choice is globally optimal because the future subproblem is the same regardless of which bit we guessed; only the current point is affected by the choice.
Let \(E(s)\) be the maximum expected additional score once suffix \(s\) is known. For each child, some primes may stop immediately after that next bit. Let \(q_0(s)\) and \(q_1(s)\) be the numbers of primes that still continue beyond \(s^{(0)}\) and \(s^{(1)}\), respectively.
If \(q(s)=0\), then
$$E(s)=0.$$
If \(q(s)>0\), then
$$E(s)=\frac{\max(c_0(s),c_1(s))}{q(s)}+\frac{q_0(s)}{q(s)}E\!\left(s^{(0)}\right)+\frac{q_1(s)}{q(s)}E\!\left(s^{(1)}\right).$$
The first term is the expected point earned on the current guess. The remaining terms are weighted by the probabilities that the game continues into the two child states.
The required value for the problem is simply
$$E(\varnothing),$$
where \(\varnothing\) denotes the root, meaning that no bits have been revealed yet.
The primes are \(2,3,5,7\). Their reversed binary strings are
$$2\to 01,\qquad 3\to 11,\qquad 5\to 101,\qquad 7\to 111.$$
At the root, the next-bit counts are \(c_0=1\) and \(c_1=3\), so the optimal first guess is \(1\), worth \(3/4\) in expectation.
At the node reached after observing suffix \(1\), the next-bit counts are \(c_0=1\) and \(c_1=2\), so the optimal local score there is \(2/3\). From both of its relevant children, the continuation contributes exactly one more expected point.
Thus
$$E(1)=\frac{2}{3}+\frac{1}{3}\cdot 1+\frac{1}{3}\cdot 1=\frac{4}{3},$$
and the root value is
$$E(\varnothing)=\frac{3}{4}+\frac{1}{4}\cdot 1+\frac{3}{4}\cdot \frac{4}{3}=2.$$
This matches the small checkpoint used by the implementation. A second checkpoint in the implementations is \(N=30\), for which the same recurrence gives \(2.9\).
The C++, Python, and Java implementations all follow the same two-phase plan. First they generate every prime up to \(10^8\) using an odd-only sieve, inserting \(2\) separately and then scanning only odd candidates.
Each prime is inserted into a binary trie from least significant bit to most significant bit. Every node records how many primes pass through it, whether a prime ends exactly there, and where the \(0\)-child and \(1\)-child are located.
Once the trie has been built, a depth-first traversal evaluates the recurrence bottom-up. At each node, the implementation reads the child counts, chooses the heavier child for the immediate guess, subtracts terminal primes when computing continuation probabilities, and combines those pieces into the expected score for that node.
Finally the root value is printed with fixed decimal precision. The three language versions differ only in storage details; mathematically they all compute the same trie dynamic program.
Let \(N=10^8\). The sieve phase runs in \(O(N\log\log N)\) time. Inserting the primes into the trie costs
$$O\!\left(\sum_{p\in P_N} \ell(p)\right)=O\!\bigl(\pi(N)\log N\bigr),$$
because each prime contributes one trie step per binary digit. The final depth-first pass is linear in the number of trie nodes, so it is also \(O\!\bigl(\pi(N)\log N\bigr)\).
Memory usage is dominated by the odd-only sieve array together with the trie itself. In asymptotic form, the method uses \(O(N)\) sieve storage plus \(O\!\bigl(\pi(N)\log N\bigr)\) trie storage.
Sei \(P_N\) die Menge aller Primzahlen bis \(N\), wobei hier \(N=10^8\) ist. Eine dieser Primzahlen wird gleichverteilt ausgewählt. Anschließend sollen ihre Binärziffern Bit für Bit geraten werden, und zwar beginnend mit dem niederwertigsten Bit.
Nach jedem Tipp ist das tatsächlich beobachtete nächste Bit bestimmt, weil die Kandidatenmenge auf genau die Primzahlen mit diesem bereits bekannten Suffix schrumpft. Für jeden richtigen Tipp gibt es einen Punkt. Gesucht ist also die maximal mögliche erwartete Gesamtpunktzahl.
Der passende Zustandsraum ist ein binärer Trie über umgekehrte Binärdarstellungen. Jeder Knoten steht für ein bereits bekanntes Suffix niedriger Bits. Deshalb lässt sich jede Entscheidung allein über die Anzahl der verbleibenden Primzahlen mit nächstem Bit \(0\) bzw. \(1\) formulieren.
Schreibe eine Primzahl \(p\) als
$$p=\sum_{d=0}^{\ell(p)-1} b_d(p)\,2^d,\qquad b_d(p)\in\{0,1\},\qquad b_{\ell(p)-1}(p)=1.$$
Im Spiel werden die Bits in der Reihenfolge \(b_0(p),b_1(p),b_2(p),\dots\) sichtbar. Ein Zustand ist daher durch ein bereits bekanntes Suffix \(s\) der niederwertigen Bits beschrieben. Ein Trie über diese umgekehrten Bitfolgen speichert genau die Primzahlen, die zu diesem Suffix passen.
Bezeichne mit \(S(s)\) die Menge aller Primzahlen, deren umgekehrte Binärdarstellung mit \(s\) beginnt. Das Erreichen des Knotens \(s\) bedeutet genau: Die versteckte Primzahl liegt in \(S(s)\).
Für einen Trie-Knoten \(s\) sei \(c(s)=|S(s)|\). Ein Teil dieser Primzahlen endet aber genau in diesem Knoten, weil ihre vollständige Binärdarstellung bereits verbraucht ist. Deren Anzahl sei \(t(s)\). Definiere
$$q(s)=c(s)-t(s).$$
Nur diese \(q(s)\) Primzahlen benötigen noch einen weiteren Tipp. Gilt \(q(s)=0\), dann ist das Spiel in diesem Zustand sicher beendet und der verbleibende Erwartungswert ist \(0\).
Betrachte nun die beiden Kindzustände \(s^{(0)}\) und \(s^{(1)}\), die durch Anhängen des nächsten beobachteten Bits entstehen. Sei \(c_0(s)\) beziehungsweise \(c_1(s)\) die Anzahl kompatibler Primzahlen in diesen beiden Kindern. Dann gilt
$$c_0(s)+c_1(s)=q(s),$$
denn jede fortsetzende Primzahl wandert genau in eines der beiden Kinder.
Angenommen, wir stehen im Zustand \(s\) und müssen das nächste Bit raten. Die Wahl zwischen \(0\) und \(1\) beeinflusst nur den Punkt in der aktuellen Runde. Welcher Kindzustand danach erreicht wird, hängt ausschließlich von der verborgenen Primzahl ab, nicht vom abgegebenen Tipp.
Darum ist die optimale Strategie lokal ganz einfach: Man rät das Bit, das unter den fortsetzenden Primzahlen häufiger vorkommt. Die bestmögliche unmittelbare Trefferwahrscheinlichkeit ist also
$$\frac{\max(c_0(s),c_1(s))}{q(s)}.$$
Diese gierige Wahl ist global optimal, weil der zukünftige Teil des Problems unabhängig davon ist, welches Bit geraten wurde.
Sei \(E(s)\) der maximale erwartete zusätzliche Score, sobald das Suffix \(s\) bekannt ist. In jedem Kind können einige Primzahlen direkt nach dem nächsten Bit enden. Bezeichne mit \(q_0(s)\) und \(q_1(s)\) die Anzahlen der Primzahlen, die über \(s^{(0)}\) bzw. \(s^{(1)}\) hinaus noch weitergehen.
Gilt \(q(s)=0\), dann ist
$$E(s)=0.$$
Für \(q(s)>0\) gilt
$$E(s)=\frac{\max(c_0(s),c_1(s))}{q(s)}+\frac{q_0(s)}{q(s)}E\!\left(s^{(0)}\right)+\frac{q_1(s)}{q(s)}E\!\left(s^{(1)}\right).$$
Der erste Term ist der Erwartungswert des aktuellen Tipps. Die beiden anderen Terme gewichten die Folgezustände mit den Wahrscheinlichkeiten, dass das Spiel dort überhaupt weiterläuft.
Gesucht ist damit schlicht
$$E(\varnothing),$$
wobei \(\varnothing\) den Wurzelknoten ohne bisher bekannte Bits bezeichnet.
Die Primzahlen sind \(2,3,5,7\). Ihre umgekehrten Binärfolgen lauten
$$2\to 01,\qquad 3\to 11,\qquad 5\to 101,\qquad 7\to 111.$$
An der Wurzel hat man \(c_0=1\) und \(c_1=3\), also ist \(1\) der optimale erste Tipp und liefert \(3/4\) Erwartungswert.
Am Knoten mit beobachtetem Suffix \(1\) sind die nächsten Häufigkeiten \(c_0=1\) und \(c_1=2\), also ergibt der beste lokale Tipp dort \(2/3\). Von beiden relevanten Kindern kommt anschließend jeweils genau ein weiterer Erwartungspunkt.
Somit
$$E(1)=\frac{2}{3}+\frac{1}{3}\cdot 1+\frac{1}{3}\cdot 1=\frac{4}{3},$$
und an der Wurzel
$$E(\varnothing)=\frac{3}{4}+\frac{1}{4}\cdot 1+\frac{3}{4}\cdot \frac{4}{3}=2.$$
Genau dieser Wert wird als kleiner Testfall in der Implementierung überprüft. Ein zweiter Kontrollwert ist \(N=30\), wofür die Rekurrenz \(2{,}9\) ergibt.
Die Implementierungen in C++, Python und Java folgen alle demselben zweistufigen Schema. Zuerst werden mit einem ungeradenoptimierten Sieb alle Primzahlen bis \(10^8\) erzeugt; die \(2\) wird separat behandelt und danach werden nur ungerade Kandidaten betrachtet.
Jede Primzahl wird dann Bit für Bit von unten nach oben in einen binären Trie eingefügt. Jeder Knoten speichert, wie viele Primzahlen ihn durchlaufen, ob dort eine Primzahl endet und wo die beiden Kinder für Bit \(0\) und Bit \(1\) liegen.
Nach dem Aufbau des Tries wertet ein Tiefensuchlauf die obige Rekurrenz von unten nach oben aus. Dazu liest die Implementierung die Kindanzahlen, wählt das schwerere Kind für den sofortigen Tipp, zieht terminale Primzahlen bei den Fortsetzungswahrscheinlichkeiten ab und kombiniert alles zu einem Erwartungswert für den aktuellen Knoten.
Am Ende wird der Wert an der Wurzel mit fester Dezimalpräzision ausgegeben. Die drei Sprachversionen unterscheiden sich nur bei der Speicherung; mathematisch berechnen sie exakt dasselbe DP auf dem Trie.
Für \(N=10^8\) benötigt das Sieb \(O(N\log\log N)\) Zeit. Das Einfügen aller Primzahlen in den Trie kostet
$$O\!\left(\sum_{p\in P_N} \ell(p)\right)=O\!\bigl(\pi(N)\log N\bigr),$$
weil jede Primzahl pro Binärziffer genau einen Trie-Schritt erzeugt. Der anschließende DFS-Durchlauf ist linear in der Zahl der Trie-Knoten und damit ebenfalls \(O\!\bigl(\pi(N)\log N\bigr)\).
Der Speicherbedarf wird vom ungeradenoptimierten Sieb und vom Trie dominiert. Asymptotisch sind das \(O(N)\) Siebspeicher plus \(O\!\bigl(\pi(N)\log N\bigr)\) Speicher für die Trie-Knoten.
\(P_N\), \(N=10^8\) olmak üzere \(N\)'i aşmayan asal sayıların kümesi olsun. Bu kümeden bir asal sayı eşit olasılıkla seçiliyor. Ardından bu sayının ikili yazımı en düşük anlamlı bitten başlayarak bit bit tahmin ediliyor.
Her tahminden sonra görülen gerçek bit, aday kümesini o soneki paylaşan asallarla sınırlar. Doğru tahmin bir puan kazandırır. Dolayısıyla amaç, toplam beklenen puanı en büyük yapan yerel karar kuralını bulmaktır.
Bu durum uzayı için en doğal yapı, ters çevrilmiş ikili gösterimler üzerinde kurulan ikili bir trie'dır. Her düğüm, artık bilinen düşük bit soneğini temsil eder. Böylece her karar, sıradaki biti \(0\) olan ve \(1\) olan kalan asal sayıların sayılarıyla ifade edilir.
Bir asal sayı \(p\) için
$$p=\sum_{d=0}^{\ell(p)-1} b_d(p)\,2^d,\qquad b_d(p)\in\{0,1\},\qquad b_{\ell(p)-1}(p)=1$$
yazalım. Oyunda görülen sıra \(b_0(p),b_1(p),b_2(p),\dots\) olduğundan, durum bilgisi zaten açığa çıkmış düşük bit soneği \(s\) ile belirlenir. Ters bit dizileri üzerine kurulan trie, tam olarak bu sonek ile uyumlu asalları tutar.
\(S(s)\), ters ikili gösterimi \(s\) ile başlayan asalların kümesi olsun. O halde trie'da \(s\) düğümüne ulaşmak, gizli asalın \(S(s)\) içinde olduğunu bilmekle aynıdır.
Bir trie düğümü \(s\) için \(c(s)=|S(s)|\) olsun. Bu asalların bir kısmı tam o düğümde biter; yani ikili gösterimlerinin tamamı zaten okunmuştur. Bu terminal sayıyı \(t(s)\) ile gösterip
$$q(s)=c(s)-t(s)$$
tanımını yapalım. Yalnızca bu \(q(s)\) asal için yeni bir bit tahmini gerekir. Eğer \(q(s)=0\) ise bu durumda oyun kesin olarak bitmiştir ve kalan beklenen puan \(0\)'dır.
Şimdi sıradaki gerçek bitin \(0\) ya da \(1\) olduğu iki çocuk duruma, yani \(s^{(0)}\) ve \(s^{(1)}\)'e bakalım. Bu çocuklardaki uyumlu asal sayıları \(c_0(s)\) ve \(c_1(s)\) olsun. Her devam eden asal tam bir çocuğa gittiği için
$$c_0(s)+c_1(s)=q(s)$$
eşitliği elde edilir.
Durum \(s\)'deyken sıradaki biti tahmin ettiğimizi düşünelim. \(0\) ya da \(1\) demek yalnızca o turun puanını etkiler. Sonrasında hangi çocuk düğüme gidileceği, bizim tahminimizle değil gizli asalın gerçek bitiyle belirlenir.
Bu yüzden en iyi strateji tamamen yereldir: Devam eden asallar arasında daha sık görülen biti tahmin etmek gerekir. Böylece o turdaki en iyi başarı olasılığı
$$\frac{\max(c_0(s),c_1(s))}{q(s)}$$
olur. Gelecekteki alt problem tahminden bağımsız olduğu için bu açgözlü seçim aynı zamanda küresel olarak da optimaldir.
\(E(s)\), sonek \(s\) bilinirken bundan sonra kazanılabilecek maksimum ek beklenen puan olsun. Her çocukta bazı asallar tam bir sonraki bitten sonra sona erebilir. \(s^{(0)}\) ve \(s^{(1)}\) sonrasında hâlâ devam eden asal sayılarını sırasıyla \(q_0(s)\) ve \(q_1(s)\) ile gösterelim.
\(q(s)=0\) ise
$$E(s)=0.$$
\(q(s)>0\) olduğunda ise
$$E(s)=\frac{\max(c_0(s),c_1(s))}{q(s)}+\frac{q_0(s)}{q(s)}E\!\left(s^{(0)}\right)+\frac{q_1(s)}{q(s)}E\!\left(s^{(1)}\right).$$
İlk terim mevcut turdaki beklenen puandır. Diğer iki terim ise oyunun iki çocuk durumda devam etme olasılıklarıyla ağırlıklandırılmış gelecek katkılarıdır.
Dolayısıyla aranan değer
$$E(\varnothing)$$
olur; burada \(\varnothing\), henüz hiçbir bitin açığa çıkmadığı kökü gösterir.
Asallar \(2,3,5,7\)'dir. Bunların ters ikili dizileri
$$2\to 01,\qquad 3\to 11,\qquad 5\to 101,\qquad 7\to 111$$
şeklindedir. Kökte \(c_0=1\) ve \(c_1=3\) olduğundan ilk optimal tahmin \(1\)'dir ve bunun beklenen katkısı \(3/4\) olur.
Gözlenen sonek \(1\) olduğunda \(c_0=1\) ve \(c_1=2\) elde edilir; burada en iyi yerel katkı \(2/3\)'tür. Bu düğümün iki ilgili çocuğundan da devam kısmı tam birer puan daha getirir.
Böylece
$$E(1)=\frac{2}{3}+\frac{1}{3}\cdot 1+\frac{1}{3}\cdot 1=\frac{4}{3},$$
ve kökte
$$E(\varnothing)=\frac{3}{4}+\frac{1}{4}\cdot 1+\frac{3}{4}\cdot \frac{4}{3}=2.$$
Bu değer uygulamanın küçük doğrulama örneğiyle aynıdır. Uygulamalardaki ikinci kontrol noktası \(N=30\) olup aynı rekürans bu durumda \(2.9\) verir.
C++, Python ve Java uygulamaları aynı iki aşamalı planı izler. Önce tek sayılara odaklanan bir elek ile \(10^8\)'e kadar bütün asallar üretilir; \(2\) ayrı eklenir ve sonra yalnızca tek adaylar taranır.
Her asal, en düşük bitten en yüksek bite doğru ikili trie'a yerleştirilir. Her düğüm, içinden kaç asal geçtiğini, tam o noktada bir asalın bitip bitmediğini ve \(0\) ile \(1\) çocuklarının konumlarını tutar.
Trie kurulduktan sonra derinlik öncelikli bir dolaşım, yukarıdaki reküransı yapraklardan köke doğru hesaplar. Her düğümde çocuk sayıları okunur, anlık tahmin için daha ağır çocuk seçilir, devam olasılıklarında terminal asallar çıkarılır ve bunlar birleştirilerek o düğümün beklenen puanı bulunur.
Son adımda kök değeri sabit ondalık hassasiyetle yazdırılır. Üç dildeki uygulamalar depolama ayrıntılarında farklı görünse de matematiksel olarak aynı trie tabanlı dinamik programı hesaplar.
\(N=10^8\) için elek aşaması \(O(N\log\log N)\) zamanda çalışır. Asalları trie'a ekleme maliyeti
$$O\!\left(\sum_{p\in P_N} \ell(p)\right)=O\!\bigl(\pi(N)\log N\bigr)$$
kadardır; çünkü her asal ikili uzunluğu kadar trie adımı üretir. Son derinlik öncelikli geçiş de düğüm sayısında lineerdir ve yine \(O\!\bigl(\pi(N)\log N\bigr)\) düzeyindedir.
Bellek kullanımı, tek sayılı elek dizisi ile trie tarafından belirlenir. Asimptotik olarak yöntem \(O(N)\) elek belleği ve \(O\!\bigl(\pi(N)\log N\bigr)\) trie belleği kullanır.
Sea \(P_N\) el conjunto de los números primos no mayores que \(N\), con \(N=10^8\). Se elige uno de esos primos de manera uniforme. Después debemos adivinar su expansión binaria bit a bit, empezando por el bit menos significativo.
Tras cada intento, el bit real queda determinado porque el conjunto de candidatos se reduce a los primos que comparten el sufijo ya observado. Cada acierto vale un punto. Por tanto, el problema consiste en maximizar la puntuación esperada total.
El espacio de estados natural es un trie binario construido con las representaciones binarias invertidas. Cada nodo representa un sufijo ya conocido de bits bajos. Así, cada decisión depende solo de cuántos primos restantes continúan con bit \(0\) y cuántos continúan con bit \(1\).
Escribimos un primo \(p\) como
$$p=\sum_{d=0}^{\ell(p)-1} b_d(p)\,2^d,\qquad b_d(p)\in\{0,1\},\qquad b_{\ell(p)-1}(p)=1.$$
El juego revela los bits en el orden \(b_0(p),b_1(p),b_2(p),\dots\). Por eso un estado queda descrito por un sufijo \(s\) de bits bajos ya conocido. Un trie sobre esas cadenas invertidas almacena exactamente los primos compatibles con dicho sufijo.
Si \(S(s)\) es el conjunto de primos cuya representación binaria invertida empieza con \(s\), entonces llegar al nodo \(s\) significa que el primo oculto pertenece a \(S(s)\).
En un nodo \(s\) del trie, sea \(c(s)=|S(s)|\). Algunos de esos primos terminan exactamente en ese nodo, porque su expansión binaria completa ya fue consumida. Sea \(t(s)\) ese número terminal y definimos
$$q(s)=c(s)-t(s).$$
Solo esos \(q(s)\) primos necesitan un nuevo intento. Si \(q(s)=0\), entonces la partida ya terminó para todos los candidatos compatibles y la puntuación esperada restante es \(0\).
Consideremos ahora los dos estados hijos \(s^{(0)}\) y \(s^{(1)}\), obtenidos al añadir el siguiente bit observado. Sean \(c_0(s)\) y \(c_1(s)\) las cantidades de primos compatibles en esos dos hijos. Como cada primo que continúa debe ir exactamente a un hijo, se cumple
$$c_0(s)+c_1(s)=q(s).$$
Supongamos que estamos en el estado \(s\) y debemos adivinar el siguiente bit. Elegir \(0\) o \(1\) solo cambia el punto de la ronda actual. El estado hijo alcanzado después depende del primo oculto, no de nuestra respuesta.
Por eso la política óptima en un nodo es puramente local: conviene adivinar el bit más frecuente entre los primos que continúan. La mejor probabilidad de acierto inmediato es
$$\frac{\max(c_0(s),c_1(s))}{q(s)}.$$
Esta decisión codiciosa es globalmente óptima porque el subproblema futuro es el mismo sin importar cuál haya sido la conjetura; solo cambia el punto actual.
Sea \(E(s)\) la puntuación esperada adicional máxima una vez conocido el sufijo \(s\). En cada hijo, algunos primos pueden terminar justo después del siguiente bit. Denotemos por \(q_0(s)\) y \(q_1(s)\) la cantidad de primos que siguen más allá de \(s^{(0)}\) y \(s^{(1)}\), respectivamente.
Si \(q(s)=0\), entonces
$$E(s)=0.$$
Si \(q(s)>0\), entonces
$$E(s)=\frac{\max(c_0(s),c_1(s))}{q(s)}+\frac{q_0(s)}{q(s)}E\!\left(s^{(0)}\right)+\frac{q_1(s)}{q(s)}E\!\left(s^{(1)}\right).$$
El primer término representa el punto esperado de la ronda actual. Los otros dos términos añaden la contribución futura ponderada por la probabilidad de que la partida continúe en cada hijo.
La respuesta pedida por el problema es simplemente
$$E(\varnothing),$$
donde \(\varnothing\) es la raíz, es decir, el estado en el que todavía no se ha revelado ningún bit.
Los primos son \(2,3,5,7\). Sus cadenas binarias invertidas son
$$2\to 01,\qquad 3\to 11,\qquad 5\to 101,\qquad 7\to 111.$$
En la raíz tenemos \(c_0=1\) y \(c_1=3\), de modo que la mejor primera conjetura es \(1\), con contribución esperada \(3/4\).
En el nodo con sufijo observado \(1\), los siguientes conteos son \(c_0=1\) y \(c_1=2\), así que la mejor ganancia local allí es \(2/3\). Desde sus dos hijos relevantes, la continuación aporta exactamente un punto esperado adicional.
Por tanto,
$$E(1)=\frac{2}{3}+\frac{1}{3}\cdot 1+\frac{1}{3}\cdot 1=\frac{4}{3},$$
y en la raíz
$$E(\varnothing)=\frac{3}{4}+\frac{1}{4}\cdot 1+\frac{3}{4}\cdot \frac{4}{3}=2.$$
Ese valor coincide con la pequeña comprobación interna de la implementación. Otra comprobación usada por las implementaciones es \(N=30\), donde la misma recurrencia produce \(2.9\).
Las implementaciones en C++, Python y Java siguen el mismo plan en dos fases. Primero generan todos los primos hasta \(10^8\) mediante una criba que solo recorre impares; el \(2\) se inserta por separado y luego se examinan únicamente candidatos impares.
Cada primo se inserta en un trie binario desde el bit menos significativo hasta el más significativo. Cada nodo registra cuántos primos pasan por él, si un primo termina exactamente allí y dónde se encuentran los hijos correspondientes a \(0\) y \(1\).
Una vez construido el trie, un recorrido en profundidad evalúa la recurrencia desde las hojas hacia arriba. En cada nodo, la implementación lee los conteos de los hijos, elige el hijo más pesado para la conjetura inmediata, descuenta los primos terminales al calcular las probabilidades de continuación y combina todo ello en el valor esperado del nodo.
Al final se imprime el valor de la raíz con precisión decimal fija. Las tres versiones difieren solo en detalles de almacenamiento; matemáticamente calculan exactamente el mismo programa dinámico sobre el trie.
Para \(N=10^8\), la fase de criba cuesta \(O(N\log\log N)\) tiempo. Insertar los primos en el trie cuesta
$$O\!\left(\sum_{p\in P_N} \ell(p)\right)=O\!\bigl(\pi(N)\log N\bigr),$$
porque cada primo aporta un paso por cada dígito binario. El recorrido final en profundidad es lineal en el número de nodos del trie, así que también queda en \(O\!\bigl(\pi(N)\log N\bigr)\).
La memoria está dominada por el arreglo de la criba sobre impares y por el propio trie. En forma asintótica, el método usa \(O(N)\) memoria para la criba y \(O\!\bigl(\pi(N)\log N\bigr)\) memoria para el trie.
设 \(P_N\) 为不超过 \(N\) 的全部质数集合，这里 \(N=10^8\)。题目从这些质数中等概率选出一个隐藏质数。接下来我们要从最低位开始，一位一位去猜它的二进制表示。
每猜一次，真实的下一位都会把候选集合缩小到与当前已知低位后缀一致的那一部分质数。猜对这一位就得一分。于是问题的本质不是暴力枚举所有质数，而是在每个“已知后缀”状态下，怎样做出能使总期望得分最大的决策。
最合适的状态表示是把所有质数的二进制表示倒过来，也就是按“从低位到高位”的顺序插入一棵二叉 trie。这样每个节点都对应一个已经确认的低位后缀，节点上的计数信息正好告诉我们下一位猜 \(0\) 还是猜 \(1\) 更有利。
把质数 \(p\) 写成
$$p=\sum_{d=0}^{\ell(p)-1} b_d(p)\,2^d,\qquad b_d(p)\in\{0,1\},\qquad b_{\ell(p)-1}(p)=1.$$
游戏中被依次“揭示”的是 \(b_0(p),b_1(p),b_2(p),\dots\)。因此，一个状态可以用已经知道的低位后缀 \(s\) 来描述。把所有质数按这种反向位串插入 trie 之后，某个节点对应的正是“所有与后缀 \(s\) 兼容的质数”。
记 \(S(s)\) 为反向二进制表示以 \(s\) 开头的所有质数集合。那么到达节点 \(s\) 就意味着：隐藏质数一定属于 \(S(s)\)。
对 trie 中的一个节点 \(s\)，令 \(c(s)=|S(s)|\)。其中有一部分质数会恰好在这个节点结束，因为它们的完整二进制表示已经全部用完。把这部分终止数量记为 \(t(s)\)，再定义
$$q(s)=c(s)-t(s).$$
只有这 \(q(s)\) 个质数还需要继续猜下一位。如果 \(q(s)=0\)，说明对于这个状态中的所有候选质数，游戏都已经结束，因此从这里开始的额外期望得分就是 \(0\)。
再看两个子状态 \(s^{(0)}\) 和 \(s^{(1)}\)，它们分别表示下一位真实比特是 \(0\) 或 \(1\) 时进入的节点。记这两个子节点中的兼容质数数量为 \(c_0(s)\) 和 \(c_1(s)\)。由于每个还能继续的质数下一位只能是 \(0\) 或 \(1\) 之一，所以有
$$c_0(s)+c_1(s)=q(s).$$
假设当前处在状态 \(s\)，现在必须猜下一位。此时猜 \(0\) 还是猜 \(1\)，只会影响这一轮能不能得分；它不会改变之后进入哪个子节点，因为后续状态完全由隐藏质数的真实下一位决定，而不是由我们的猜测决定。
这意味着最优决策可以在每个节点局部独立完成：只要比较继续向下的质数中，下一位是 \(0\) 的多还是 \(1\) 的多，猜数量较大的一边即可。于是这一轮能够达到的最大即时成功概率为
$$\frac{\max(c_0(s),c_1(s))}{q(s)}.$$
之所以这个看似贪心的选择也是全局最优，是因为“未来会进入哪个子问题”不取决于猜测本身，猜测只影响当前这一分。
设 \(E(s)\) 表示在已知后缀 \(s\) 的前提下，还能获得的最大额外期望得分。到达某个子节点后，又有一些质数会恰好在那里结束，因此还要区分“进入子节点的质数数目”和“进入子节点后还能继续往下的质数数目”。记 \(q_0(s)\) 与 \(q_1(s)\) 分别为经过 \(s^{(0)}\) 与 \(s^{(1)}\) 后仍会继续的质数数量。
当 \(q(s)=0\) 时，
$$E(s)=0.$$
当 \(q(s)>0\) 时，
$$E(s)=\frac{\max(c_0(s),c_1(s))}{q(s)}+\frac{q_0(s)}{q(s)}E\!\left(s^{(0)}\right)+\frac{q_1(s)}{q(s)}E\!\left(s^{(1)}\right).$$
第一项表示当前这一轮的期望得分。后两项表示游戏继续进入两个子状态时的未来贡献，并按对应概率加权。
因此题目的目标值就是根节点对应的
$$E(\varnothing),$$
其中 \(\varnothing\) 表示尚未揭示任何比特的初始状态。
当 \(N=10\) 时，质数为 \(2,3,5,7\)。把它们写成从低位到高位的反向位串，可得
$$2\to 01,\qquad 3\to 11,\qquad 5\to 101,\qquad 7\to 111.$$
在根节点，下一位是 \(0\) 的只有 \(2\)，所以 \(c_0=1\)；下一位是 \(1\) 的有 \(3,5,7\)，所以 \(c_1=3\)。最优第一猜显然是 \(1\)，这一轮的期望得分为 \(3/4\)。
如果真实下一位是 \(1\)，就来到后缀为 \(1\) 的节点。此时三枚候选质数中，下一位为 \(0\) 的只有 \(5\)，而下一位为 \(1\) 的是 \(3\) 与 \(7\)，所以局部最优贡献为 \(2/3\)。从这个节点继续往下分析，会发现两个相关子节点各自都还能再贡献恰好 \(1\) 分的期望。
于是
$$E(1)=\frac{2}{3}+\frac{1}{3}\cdot 1+\frac{1}{3}\cdot 1=\frac{4}{3},$$
而根节点的值为
$$E(\varnothing)=\frac{3}{4}+\frac{1}{4}\cdot 1+\frac{3}{4}\cdot \frac{4}{3}=2.$$
这正好对应实现中使用的小规模校验值。实现里还有第二个校验点：当 \(N=30\) 时，同样的递推会得到 \(2.9\)。
C++、Python 和 Java 实现都采用相同的两阶段流程。第一阶段先用只处理奇数的筛法生成不超过 \(10^8\) 的全部质数，其中 \(2\) 单独加入，随后只扫描奇数候选。
第二阶段把每个质数按“从最低位到最高位”的顺序插入二叉 trie。每个节点保存三类核心信息：有多少个质数经过这个节点、是否有某个质数恰好在这里结束，以及两个子节点分别对应比特 \(0\) 和比特 \(1\)。
Trie 建好之后，再做一次深度优先遍历，自底向上计算上面的递推式。对每个节点，程序读取两个孩子的计数，先取较大的那个作为当前轮的最优猜测，再在继续概率里扣掉那些在子节点处已经结束的质数，最后把即时得分和未来得分组合成该节点的期望值。
最终输出根节点的结果，并保留固定小数位。三种语言版本在存储形式上略有不同，但它们计算的数学对象完全相同，都是这棵 trie 上的动态规划。
当 \(N=10^8\) 时，筛法阶段的时间复杂度为 \(O(N\log\log N)\)。把所有质数插入 trie 的代价为
$$O\!\left(\sum_{p\in P_N} \ell(p)\right)=O\!\bigl(\pi(N)\log N\bigr),$$
因为每个质数都会按其二进制长度走过相应数量的 trie 边。最后的深度优先遍历对每个节点只访问常数次，因此也是 \(O\!\bigl(\pi(N)\log N\bigr)\)。
空间方面，主要消耗来自奇数筛数组和 trie 本身。渐近地看，方法需要 \(O(N)\) 的筛空间以及 \(O\!\bigl(\pi(N)\log N\bigr)\) 的 trie 空间。
Пусть \(P_N\) обозначает множество всех простых чисел, не превосходящих \(N\), где \(N=10^8\). Одно из этих простых выбирается равновероятно. Затем нужно угадывать его двоичную запись по одному биту, начиная с младшего бита.
После каждого хода фактически становится известен настоящий следующий бит, потому что множество кандидатов сужается до простых, имеющих уже раскрытый суффикс. За каждое правильное предположение начисляется один балл. Значит, нужно максимизировать ожидаемую суммарную оценку.
Естественное описание состояний здесь дает двоичный trie, построенный по перевернутым двоичным записям простых. Каждый узел соответствует уже известному суффиксу младших битов. Поэтому решение в каждом состоянии определяется только тем, сколько оставшихся простых продолжаются битом \(0\), а сколько битом \(1\).
Представим простое \(p\) в виде
$$p=\sum_{d=0}^{\ell(p)-1} b_d(p)\,2^d,\qquad b_d(p)\in\{0,1\},\qquad b_{\ell(p)-1}(p)=1.$$
В игре биты раскрываются в порядке \(b_0(p),b_1(p),b_2(p),\dots\). Поэтому состояние задается уже известным суффиксом низших битов \(s\). Trie по этим перевернутым битовым строкам хранит в каждом узле ровно те простые, которые совместимы с данным суффиксом.
Если \(S(s)\) обозначает множество простых, чья перевернутая двоичная запись начинается с \(s\), то попадание в узел \(s\) означает, что скрытое простое принадлежит \(S(s)\).
Для узла \(s\) положим \(c(s)=|S(s)|\). Часть этих простых заканчивается ровно в этом узле, потому что их полная двоичная запись уже целиком прочитана. Обозначим число таких терминальных простых через \(t(s)\) и введем
$$q(s)=c(s)-t(s).$$
Только эти \(q(s)\) простых требуют следующего угадывания. Если \(q(s)=0\), то игра в этом состоянии уже закончена для всех совместимых кандидатов, и оставшееся матожидание равно нулю.
Теперь рассмотрим два дочерних состояния \(s^{(0)}\) и \(s^{(1)}\), которые возникают после раскрытия следующего бита \(0\) или \(1\). Пусть \(c_0(s)\) и \(c_1(s)\) обозначают числа совместимых простых в этих дочерних узлах. Тогда
$$c_0(s)+c_1(s)=q(s),$$
потому что каждое продолжающееся простое обязано перейти ровно в одного из двух потомков.
Пусть мы находимся в состоянии \(s\) и должны угадать следующий бит. Выбор между \(0\) и \(1\) влияет только на очко текущего хода. То, в какого потомка перейдет игра дальше, определяется скрытым простым, а не нашим ответом.
Следовательно, оптимальная стратегия в узле локальна: нужно угадывать тот бит, который чаще встречается среди продолжающихся простых. Лучшая вероятность немедленного успеха равна
$$\frac{\max(c_0(s),c_1(s))}{q(s)}.$$
Такой жадный выбор является и глобально оптимальным, потому что будущая подзадача не зависит от сделанной догадки; от нее зависит только текущее очко.
Пусть \(E(s)\) - максимальное ожидаемое дополнительное число очков после того, как суффикс \(s\) уже известен. В каждом дочернем узле часть простых может закончиться сразу после следующего бита. Обозначим через \(q_0(s)\) и \(q_1(s)\) количества простых, которые продолжаются дальше за пределы \(s^{(0)}\) и \(s^{(1)}\).
Если \(q(s)=0\), то
$$E(s)=0.$$
Если \(q(s)>0\), то
$$E(s)=\frac{\max(c_0(s),c_1(s))}{q(s)}+\frac{q_0(s)}{q(s)}E\!\left(s^{(0)}\right)+\frac{q_1(s)}{q(s)}E\!\left(s^{(1)}\right).$$
Первый член отвечает за ожидаемый балл на текущем шаге. Два остальных члена добавляют будущий вклад, взвешенный вероятностями продолжения игры в каждом из дочерних состояний.
Искомое значение задачи равно
$$E(\varnothing),$$
где \(\varnothing\) обозначает корень trie, то есть состояние, в котором еще не раскрыт ни один бит.
При \(N=10\) простые числа равны \(2,3,5,7\). Их перевернутые двоичные строки таковы:
$$2\to 01,\qquad 3\to 11,\qquad 5\to 101,\qquad 7\to 111.$$
В корне имеем \(c_0=1\) и \(c_1=3\), поэтому первая оптимальная догадка - \(1\), и ее ожидаемый вклад равен \(3/4\).
В узле с наблюденным суффиксом \(1\) следующие частоты равны \(c_0=1\) и \(c_1=2\), так что локальный оптимум дает \(2/3\). Из обоих существенных потомков дальнейшее продолжение дает еще ровно по одному ожидаемому очку.
Следовательно,
$$E(1)=\frac{2}{3}+\frac{1}{3}\cdot 1+\frac{1}{3}\cdot 1=\frac{4}{3},$$
а в корне
$$E(\varnothing)=\frac{3}{4}+\frac{1}{4}\cdot 1+\frac{3}{4}\cdot \frac{4}{3}=2.$$
Это совпадает с малой проверкой, встроенной в реализацию. Еще одна контрольная точка в реализациях - \(N=30\), где та же рекурсия дает \(2.9\).
Реализации на C++, Python и Java используют одну и ту же двухфазную схему. Сначала все простые до \(10^8\) строятся с помощью решета, которое работает только с нечетными числами; число \(2\) обрабатывается отдельно, а затем перебираются только нечетные кандидаты.
Каждое простое вставляется в двоичный trie от младшего бита к старшему. В каждом узле хранится число простых, проходящих через него, признак того, оканчивается ли некоторое простое ровно в этом узле, а также ссылки на потомков для битов \(0\) и \(1\).
После построения trie выполняется обход в глубину, который вычисляет приведенную выше рекурсию снизу вверх. В каждом узле реализация читает размеры дочерних поддеревьев, выбирает более тяжелого потомка для текущей догадки, вычитает терминальные простые при подсчете вероятностей продолжения и собирает все это в ожидаемое значение узла.
В конце печатается значение в корне с фиксированной десятичной точностью. Различия между тремя языками касаются только хранения данных; математически все версии вычисляют одну и ту же динамику на trie.
При \(N=10^8\) этап решета занимает \(O(N\log\log N)\) времени. Вставка простых в trie стоит
$$O\!\left(\sum_{p\in P_N} \ell(p)\right)=O\!\bigl(\pi(N)\log N\bigr),$$
поскольку каждое простое проходит по одному ребру trie на каждый двоичный разряд. Финальный DFS-обход линейный по числу узлов trie, то есть тоже имеет порядок \(O\!\bigl(\pi(N)\log N\bigr)\).
Память в основном расходуется на массив для нечетного решета и на сам trie. Асимптотически метод использует \(O(N)\) памяти для решета и \(O\!\bigl(\pi(N)\log N\bigr)\) памяти для узлов trie.
لتكن \(P_N\) مجموعة جميع الأعداد الأولية التي لا تتجاوز \(N\)، وهنا \(N=10^8\). يُختار عدد أولي واحد من هذه المجموعة باحتمال متساوٍ. بعد ذلك نحاول تخمين تمثيله الثنائي بتًا بعد بت، بدءًا من أقل البتات أهمية.
بعد كل تخمين ينحصر مجال المرشحين في الأعداد الأولية التي تشترك في اللاحقة الثنائية المنكشفة حتى تلك اللحظة. وكل تخمين صحيح يعطي نقطة واحدة. لذلك فالمطلوب هو تعظيم القيمة المتوقعة لمجموع النقاط، أي إيجاد القرار الأمثل عند كل حالة تمثل لاحقة معروفة من البتات الدنيا.
أنسب تمثيل للحالات هنا هو trie ثنائي مبني على الكتابات الثنائية المعكوسة للأعداد الأولية. كل عقدة تمثل لاحقة معروفة من البتات الدنيا، ولذلك يمكن صياغة القرار في كل عقدة فقط من خلال عدد الأعداد الأولية المتبقية التي يكون بتها التالي \(0\) وعدد التي يكون بتها التالي \(1\).
نكتب العدد الأولي \(p\) على الصورة
$$p=\sum_{d=0}^{\ell(p)-1} b_d(p)\,2^d,\qquad b_d(p)\in\{0,1\},\qquad b_{\ell(p)-1}(p)=1.$$
في اللعبة تظهر البتات بالترتيب \(b_0(p),b_1(p),b_2(p),\dots\). لذلك يمكن وصف الحالة بلاحقة \(s\) من البتات الدنيا أصبحت معلومة بالفعل. وعند بناء trie على هذه السلاسل الثنائية المعكوسة، فإن كل عقدة تخزن بالضبط الأعداد الأولية المتوافقة مع تلك اللاحقة.
إذا رمزنا بـ \(S(s)\) إلى مجموعة الأعداد الأولية التي تبدأ كتابتها الثنائية المعكوسة باللاحقة \(s\)، فإن الوصول إلى العقدة \(s\) يعني أن العدد الأولي المخفي ينتمي إلى \(S(s)\).
في عقدة trie نرمز إلى عدد المرشحين المتوافقين بـ \(c(s)=|S(s)|\). بعض هذه الأعداد الأولية ينتهي تمامًا عند تلك العقدة لأن تمثيله الثنائي الكامل قد استُهلك بالفعل. ولنسمِّ هذا العدد الطرفي \(t(s)\)، ثم نعرّف
$$q(s)=c(s)-t(s).$$
فقط هذه الأعداد وعددها \(q(s)\) تحتاج إلى تخمين جديد. وإذا كان \(q(s)=0\)، فهذا يعني أن اللعبة انتهت في هذه الحالة لكل المرشحين المتوافقين، ومن ثم تكون القيمة المتوقعة المتبقية مساوية للصفر.
لننظر الآن إلى حالتي الابنين \(s^{(0)}\) و\(s^{(1)}\)، اللتين تمثلان انكشاف البت التالي بوصفه \(0\) أو \(1\). ولتكن \(c_0(s)\) و\(c_1(s)\) أعداد الأعداد الأولية المتوافقة داخل هاتين العقدتين. بما أن كل عدد أولي مستمر لا بد أن يذهب إلى ابن واحد فقط، فنحصل على
$$c_0(s)+c_1(s)=q(s).$$
افترض أننا في الحالة \(s\) وعلينا أن نخمن البت التالي. اختيار \(0\) أو \(1\) يؤثر فقط في نقطة الجولة الحالية. أما العقدة التالية التي سنصل إليها بعد كشف الحقيقة فهي تتحدد بالعدد الأولي المخفي نفسه، لا بالتخمين الذي اخترناه.
لهذا يكون القرار الأمثل في كل عقدة قرارًا محليًا بحتًا: نخمن البت الأكثر شيوعًا بين الأعداد الأولية التي ما زالت مستمرة. وعندئذ تكون أفضل احتمالية نجاح فوري هي
$$\frac{\max(c_0(s),c_1(s))}{q(s)}.$$
وهذا الاختيار الجشع هو أيضًا اختيار أمثل عالميًا، لأن الجزء المستقبلي من المسألة لا يعتمد على التخمين نفسه، بل يعتمد فقط على البت الحقيقي الذي يكشفه العدد الأولي المخفي.
لتكن \(E(s)\) هي أكبر قيمة متوقعة إضافية يمكن الحصول عليها بعد معرفة اللاحقة \(s\). في كل ابن قد توجد أعداد أولية تنتهي مباشرة بعد البت التالي، لذا يجب التمييز بين عدد الأعداد التي تدخل الابن وعدد الأعداد التي تواصل بعده. نرمز بـ \(q_0(s)\) و\(q_1(s)\) إلى عدد الأعداد الأولية التي تستمر إلى ما بعد \(s^{(0)}\) و\(s^{(1)}\) على الترتيب.
إذا كان \(q(s)=0\)، فإن
$$E(s)=0.$$
وإذا كان \(q(s)>0\)، فإن
$$E(s)=\frac{\max(c_0(s),c_1(s))}{q(s)}+\frac{q_0(s)}{q(s)}E\!\left(s^{(0)}\right)+\frac{q_1(s)}{q(s)}E\!\left(s^{(1)}\right).$$
الحد الأول يمثل النقطة المتوقعة في الجولة الحالية. والحدان الآخران يضيفان المساهمة المستقبلية موزونة باحتمال استمرار اللعبة في كل من الفرعين.
ومن ثم فإن القيمة المطلوبة في المسألة هي
$$E(\varnothing),$$
حيث تمثل \(\varnothing\) الجذر، أي الحالة التي لم يُكشف فيها أي بت بعد.
عندما يكون \(N=10\)، تكون الأعداد الأولية هي \(2,3,5,7\). وسلاسلها الثنائية المعكوسة هي
$$2\to 01,\qquad 3\to 11,\qquad 5\to 101,\qquad 7\to 111.$$
عند الجذر لدينا \(c_0=1\) و\(c_1=3\)، ولذلك يكون التخمين الأول الأمثل هو \(1\)، ومساهمته المتوقعة \(3/4\).
وعند العقدة ذات اللاحقة المرصودة \(1\)، تصبح الأعداد \(c_0=1\) و\(c_1=2\)، ولذلك تكون أفضل مساهمة محلية هي \(2/3\). ومن الابنين ذوي الصلة بعد ذلك نحصل في كل حالة على نقطة متوقعة إضافية تساوي \(1\) تمامًا.
إذًا
$$E(1)=\frac{2}{3}+\frac{1}{3}\cdot 1+\frac{1}{3}\cdot 1=\frac{4}{3},$$
وعند الجذر
$$E(\varnothing)=\frac{3}{4}+\frac{1}{4}\cdot 1+\frac{3}{4}\cdot \frac{4}{3}=2.$$
وهذه القيمة تطابق نقطة التحقق الصغيرة المستخدمة في التنفيذ. وهناك أيضًا نقطة تحقق ثانية في التنفيذات عند \(N=30\)، وتعطي فيها العلاقة نفسها القيمة \(2.9\).
تنفيذات C++ وPython وJava تتبع الخطة نفسها على مرحلتين. أولًا تُولَّد جميع الأعداد الأولية حتى \(10^8\) باستخدام غربال يعالج الأعداد الفردية فقط؛ فيُضاف العدد \(2\) على حدة ثم تُفحص المرشحات الفردية وحدها.
بعد ذلك يُدرج كل عدد أولي في trie ثنائي من البت الأقل أهمية إلى البت الأعلى. وتحفظ كل عقدة عدد الأعداد الأولية التي تمر بها، وما إذا كان عدد أولي ما ينتهي عندها تمامًا، وموضعي الابنين الموافقين للبت \(0\) والبت \(1\).
بعد اكتمال بناء trie، يقيّم مرورٌ عمقي العلاقة العودية من الأسفل إلى الأعلى. ففي كل عقدة يقرأ التنفيذ أعداد الابنين، ويختار الابن الأثقل للتخمين الفوري، ويطرح الأعداد الطرفية عند حساب احتمالات الاستمرار، ثم يجمع ذلك كله للحصول على القيمة المتوقعة في تلك العقدة.
وفي النهاية تُطبع قيمة الجذر بدقة عشرية ثابتة. والاختلاف بين اللغات الثلاث يقتصر على تفاصيل التخزين، أما رياضيًا فهي تحسب البرنامج الديناميكي نفسه فوق trie نفسها.
عند \(N=10^8\) تعمل مرحلة الغربال في زمن \(O(N\log\log N)\). أما إدراج الأعداد الأولية في trie فيكلف
$$O\!\left(\sum_{p\in P_N} \ell(p)\right)=O\!\bigl(\pi(N)\log N\bigr),$$
لأن كل عدد أولي يضيف خطوة واحدة في trie لكل رقم في تمثيله الثنائي. والمرور العمقي النهائي خطي في عدد عقد trie، ولذلك فهو أيضًا من الرتبة \(O\!\bigl(\pi(N)\log N\bigr)\).
يهيمن على الذاكرة كلٌّ من مصفوفة الغربال الخاصة بالأعداد الفردية وTrie نفسها. وبصورة تقاربية تستخدم الطريقة ذاكرة \(O(N)\) للغربال وذاكرة \(O\!\bigl(\pi(N)\log N\bigr)\) لعقد trie.