For each positive integer \(x\), consider all integers obtained by deleting exactly one binary digit from the binary expansion of \(x\). These smaller integers act as predecessors. A deleted \(1\)-bit gives a lower constraint, and a deleted \(0\)-bit gives an upper constraint.
Starting from the base value \(v_0=0\), the value \(v_x\) is defined to be the simplest dyadic rational compatible with all those constraints. Here a dyadic rational means a number of the form \(\frac{m}{2^k}\) with \(m\in\mathbb{Z}\) and \(k\ge 0\).
The target quantity is
$$S(n)=\left\lceil \sum_{i=1}^{n} i\,v_i \right\rceil.$$
The recurrence is local: once the deleted-bit predecessors of \(x\) are known, \(v_x\) is forced to lie in an open interval, and the simplest dyadic number inside that interval is chosen.
Let the deleted-bit predecessors of \(x\) be \(y_1,\dots,y_\ell\), where \(\ell\) is the binary length of \(x\). Every predecessor is smaller than \(x\), because deleting one bit shortens the representation to at most \(\ell-1\) bits, so
$$y_j<2^{\ell-1}\le x.$$
This is why the values can be computed in increasing order of \(x\).
Let \(A_x\) be the set of predecessor values coming from deleted \(1\)-bits, and let \(B_x\) be the set coming from deleted \(0\)-bits. Define
$$L_x=\max A_x,$$
and, when \(B_x\neq\varnothing\), define
$$R_x=\min B_x.$$
The defining inequalities are
$$v_x>L_x,$$
and, if \(B_x\neq\varnothing\), also
$$v_x<R_x.$$
Because the leading binary digit is always \(1\), the set \(A_x\) is never empty, so every \(x\ge 1\) has at least a lower bound.
Suppose first that \(B_x\neq\varnothing\) and test a dyadic candidate \(\frac{m}{2^k}\). The condition
$$L_x<\frac{m}{2^k}<R_x$$
is equivalent to
$$\left\lfloor 2^kL_x\right\rfloor+1\le m\le \left\lceil 2^kR_x\right\rceil-1.$$
So, for a fixed denominator \(2^k\), admissible numerators are exactly the integers in that closed interval. The smallest \(k\) for which such an integer exists gives the coarsest denominator and therefore the simplest dyadic level.
If \(B_x=\varnothing\), then the binary expansion of \(x\) contains no \(0\)-bit. There is no upper bound, and the simplest admissible dyadic is just the smallest integer strictly larger than \(L_x\):
$$v_x=\lfloor L_x\rfloor+1.$$
Once the minimal denominator \(2^k\) is known, there may be several admissible numerators. The implementations select the feasible integer closest to \(0\): choose \(m=0\) if possible, otherwise choose the admissible integer with smallest absolute value. This reproduces the intended notion of the simplest dyadic inside the interval.
After that, remove all common factors of \(2\) from numerator and denominator. Each value is therefore stored in reduced form
$$v_x=\frac{a_x}{2^{e_x}},$$
where \(a_x\) is odd unless the value is \(0\).
This reduction is important because dyadic numbers can then be compared exactly by lifting them to a common power-of-two denominator and comparing the scaled numerators as integers. No floating-point approximation is needed anywhere.
After computing \(v_1,\dots,v_n\), write each one as \(v_i=\frac{a_i}{2^{e_i}}\) in reduced form, and let
$$E=\max_{1\le i\le n} e_i.$$
Then
$$\sum_{i=1}^{n} i\,v_i=\frac{1}{2^E}\sum_{i=1}^{n} i\,a_i\,2^{E-e_i}=\frac{N_n}{2^E},$$
where \(N_n\) is an integer.
In this recurrence every \(v_i\) is positive, so \(N_n\ge 0\). Therefore
$$S(n)=\left\lceil \frac{N_n}{2^E}\right\rceil=\left\lfloor \frac{N_n+2^E-1}{2^E}\right\rfloor.$$
The final ceiling can thus be computed with integer arithmetic only.
The first few values come directly from the interval rule:
$$\begin{aligned} v_1&=1,\\ v_2&=\frac{1}{2},\\ v_3&=2,\\ v_4&=\frac{1}{4},\\ v_5&=\frac{3}{2}. \end{aligned}$$
For example, \(x=5\) has binary form \(101_2\). Deleting the leftmost \(1\) gives \(1\), deleting the middle \(0\) gives \(3\), and deleting the last \(1\) gives \(2\). So the lower bound is
$$L_5=\max(v_1,v_2)=1,$$
the upper bound is
$$R_5=v_3=2,$$
and the simplest dyadic in \((1,2)\) is
$$v_5=\frac{3}{2}.$$
Using the first five values,
$$S(5)=\left\lceil 1\cdot 1+2\cdot \frac{1}{2}+3\cdot 2+4\cdot \frac{1}{4}+5\cdot \frac{3}{2}\right\rceil=\left\lceil \frac{33}{2}\right\rceil=17.$$
Continuing the same recurrence gives
$$v_6=1,\qquad v_7=3,\qquad v_8=\frac{1}{8},\qquad v_9=\frac{5}{4},\qquad v_{10}=\frac{3}{4},$$
hence
$$S(10)=64,$$
which matches the implementation checkpoint.
The C++, Python, and Java implementations iterate from \(1\) up to \(n\). For each \(x\), they scan all bit positions, form each deleted-bit predecessor, and update the best lower and upper bounds using exact dyadic comparisons. Because every predecessor is smaller than \(x\), all required values are already known when \(x\) is processed.
They then test denominators \(1,2,4,\dots\) until the interval contains an admissible dyadic rational. The chosen value is reduced immediately so the stored denominator is as small as possible. After the table is complete, the implementations lift every term \(i\,v_i\) to a common denominator, add the integer numerators, and apply the ceiling formula exactly.
For a given \(x\), there are \(\lfloor\log_2 x\rfloor+1\) deleted-bit predecessors to inspect, so building the interval for \(v_x\) costs \(O(\log x)\). The additional search over dyadic denominators is bounded by a small fixed constant in the implementations, so the total running time up to \(n\) is \(O(n\log n)\). The table of dyadic values uses \(O(n)\) memory.
Für jede positive ganze Zahl \(x\) betrachten wir alle Zahlen, die entstehen, wenn man aus der Binärdarstellung von \(x\) genau ein Bit löscht. Diese kleineren Zahlen sind die Vorgänger von \(x\). Ein gelöschtes \(1\)-Bit liefert eine untere Schranke, ein gelöschtes \(0\)-Bit eine obere Schranke.
Ausgehend vom Basiswert \(v_0=0\) wird \(v_x\) als die einfachste dyadische rationale Zahl definiert, die mit allen diesen Schranken verträglich ist. Dabei bedeutet dyadisch eine Darstellung der Form \(\frac{m}{2^k}\) mit \(m\in\mathbb{Z}\) und \(k\ge 0\).
Gesucht ist
$$S(n)=\left\lceil \sum_{i=1}^{n} i\,v_i \right\rceil.$$
Die Rekursion ist lokal: Sobald die durch Bit-Löschung entstehenden Vorgänger von \(x\) bekannt sind, ist das zulässige offene Intervall für \(v_x\) festgelegt, und darin wird die einfachste dyadische Zahl gewählt.
Seien \(y_1,\dots,y_\ell\) die Vorgänger von \(x\), wobei \(\ell\) die Binärlänge von \(x\) ist. Jeder Vorgänger ist kleiner als \(x\), denn nach dem Löschen eines Bits hat die Darstellung höchstens \(\ell-1\) Stellen, also
$$y_j<2^{\ell-1}\le x.$$
Darum können die Werte in aufsteigender Reihenfolge von \(x\) berechnet werden.
Sei \(A_x\) die Menge der Vorgängerwerte, die von gelöschten \(1\)-Bits stammen, und \(B_x\) die entsprechende Menge für gelöschte \(0\)-Bits. Dann definieren wir
$$L_x=\max A_x,$$
und falls \(B_x\neq\varnothing\), außerdem
$$R_x=\min B_x.$$
Die definierenden Ungleichungen lauten
$$v_x>L_x,$$
und, wenn \(B_x\neq\varnothing\), zusätzlich
$$v_x<R_x.$$
Da das führende Bit jeder Binärdarstellung immer \(1\) ist, ist \(A_x\) nie leer. Es gibt also für jedes \(x\ge 1\) mindestens eine untere Schranke.
Nehmen wir zunächst an, \(B_x\neq\varnothing\), und testen einen dyadischen Kandidaten \(\frac{m}{2^k}\). Die Bedingung
$$L_x<\frac{m}{2^k}<R_x$$
ist äquivalent zu
$$\left\lfloor 2^kL_x\right\rfloor+1\le m\le \left\lceil 2^kR_x\right\rceil-1.$$
Für festes \(2^k\) sind also genau die ganzzahligen \(m\) in diesem abgeschlossenen Intervall zulässig. Das kleinste \(k\), für das überhaupt ein solches \(m\) existiert, liefert den gröbsten Nenner und damit die einfachste dyadische Ebene.
Falls \(B_x=\varnothing\), enthält die Binärdarstellung von \(x\) kein einziges \(0\)-Bit. Dann gibt es keine obere Schranke, und die einfachste zulässige dyadische Zahl ist einfach die kleinste ganze Zahl strikt oberhalb von \(L_x\):
$$v_x=\lfloor L_x\rfloor+1.$$
Sobald der kleinste mögliche Nenner \(2^k\) feststeht, können mehrere zulässige Zähler vorkommen. Die Implementierungen wählen die zulässige ganze Zahl, die \(0\) am nächsten liegt: Falls möglich, wird \(m=0\) genommen, sonst die zulässige ganze Zahl mit kleinstem Betrag. Genau so wird die beabsichtigte Einfachheit der dyadischen Zahl umgesetzt.
Anschließend werden alle gemeinsamen Zweierfaktoren aus Zähler und Nenner entfernt. Jeder Wert wird also in reduzierter Form gespeichert als
$$v_x=\frac{a_x}{2^{e_x}},$$
wobei \(a_x\) ungerade ist, außer im Fall des Werts \(0\).
Diese Kürzung ist wichtig, weil dyadische Zahlen dann exakt verglichen werden können: Man bringt beide auf denselben Zweierpotenz-Nenner und vergleicht nur die skalierten Zähler als ganze Zahlen. Gleitkomma-Arithmetik wird nirgends benötigt.
Nachdem \(v_1,\dots,v_n\) berechnet sind, schreiben wir jeden Wert als \(v_i=\frac{a_i}{2^{e_i}}\) in reduzierter Form und setzen
$$E=\max_{1\le i\le n} e_i.$$
Dann gilt
$$\sum_{i=1}^{n} i\,v_i=\frac{1}{2^E}\sum_{i=1}^{n} i\,a_i\,2^{E-e_i}=\frac{N_n}{2^E},$$
wobei \(N_n\) eine ganze Zahl ist.
In dieser Rekursion ist jedes \(v_i\) positiv, also \(N_n\ge 0\). Damit folgt
$$S(n)=\left\lceil \frac{N_n}{2^E}\right\rceil=\left\lfloor \frac{N_n+2^E-1}{2^E}\right\rfloor.$$
Auch der letzte Deckenwert kann daher rein ganzzahlig berechnet werden.
Die ersten Werte ergeben sich direkt aus der Intervallregel:
$$\begin{aligned} v_1&=1,\\ v_2&=\frac{1}{2},\\ v_3&=2,\\ v_4&=\frac{1}{4},\\ v_5&=\frac{3}{2}. \end{aligned}$$
Betrachten wir etwa \(x=5\) mit Binärdarstellung \(101_2\). Löscht man die linke \(1\), erhält man \(1\); löscht man die mittlere \(0\), erhält man \(3\); löscht man die rechte \(1\), erhält man \(2\). Also ist die untere Schranke
$$L_5=\max(v_1,v_2)=1,$$
die obere Schranke
$$R_5=v_3=2,$$
und die einfachste dyadische Zahl in \((1,2)\) ist
$$v_5=\frac{3}{2}.$$
Mit den ersten fünf Werten erhält man
$$S(5)=\left\lceil 1\cdot 1+2\cdot \frac{1}{2}+3\cdot 2+4\cdot \frac{1}{4}+5\cdot \frac{3}{2}\right\rceil=\left\lceil \frac{33}{2}\right\rceil=17.$$
Setzt man die Rekursion fort, so bekommt man
$$v_6=1,\qquad v_7=3,\qquad v_8=\frac{1}{8},\qquad v_9=\frac{5}{4},\qquad v_{10}=\frac{3}{4},$$
also
$$S(10)=64,$$
genau wie im Kontrollwert der Implementierung.
Die C++-, Python- und Java-Implementierungen laufen von \(1\) bis \(n\). Für jedes \(x\) werden alle Bitpositionen durchlaufen, die Vorgänger durch Löschen eines Bits gebildet und daraus mittels exakter dyadischer Vergleiche die beste untere und obere Schranke bestimmt. Da jeder Vorgänger kleiner als \(x\) ist, sind beim Verarbeiten von \(x\) bereits alle nötigen Werte bekannt.
Danach werden die Nenner \(1,2,4,\dots\) getestet, bis das Intervall eine zulässige dyadische rationale Zahl enthält. Der gewählte Wert wird sofort gekürzt, damit der gespeicherte Nenner minimal bleibt. Nach dem Aufbau der gesamten Tabelle werden alle Terme \(i\,v_i\) auf einen gemeinsamen Nenner gebracht, die ganzzahligen Zähler addiert und die Deckenfunktion exakt ausgewertet.
Für ein gegebenes \(x\) müssen \(\lfloor\log_2 x\rfloor+1\) gelöschte-Bit-Vorgänger untersucht werden, also kostet der Aufbau des Intervalls für \(v_x\) \(O(\log x)\). Die zusätzliche Suche über dyadische Nenner ist in den Implementierungen durch eine kleine feste Konstante begrenzt. Daher beträgt die Gesamtlaufzeit bis \(n\) insgesamt \(O(n\log n)\). Die Tabelle der dyadischen Werte benötigt \(O(n)\) Speicher.
Her pozitif tamsayı \(x\) için, \(x\)'in ikili yazımından tam olarak bir bit silinerek elde edilen bütün sayıları düşünürüz. Bu daha küçük sayılar \(x\)'in öncülleridir. Silinen bit \(1\) ise alt sınır, silinen bit \(0\) ise üst sınır oluşur.
Başlangıç değeri \(v_0=0\) alınır ve \(v_x\), bu sınırların tamamını sağlayan en basit dyadik rasyonel olarak tanımlanır. Burada dyadik rasyonel, \(\frac{m}{2^k}\) biçimindeki bir sayıdır; \(m\in\mathbb{Z}\) ve \(k\ge 0\).
Hedef büyüklük
$$S(n)=\left\lceil \sum_{i=1}^{n} i\,v_i \right\rceil$$
ifadesidir.
Özyineleme yereldir: \(x\) için bit silerek oluşan öncüller bilindiğinde, \(v_x\)'in bulunması gereken açık aralık da belirlenmiş olur; sonra bu aralığın içindeki en basit dyadik sayı seçilir.
\(x\)'in bit silme ile oluşan öncülleri \(y_1,\dots,y_\ell\) olsun; burada \(\ell\), \(x\)'in ikili uzunluğudur. Her öncül \(x\)'ten küçüktür, çünkü bir bit silinince gösterim en fazla \(\ell-1\) bit kalır ve bu yüzden
$$y_j<2^{\ell-1}\le x$$
olur. Bu nedenle değerler \(x\) artan sırada dinamik olarak hesaplanabilir.
Silinen \(1\)-bitlerden gelen öncül değerleri kümesine \(A_x\), silinen \(0\)-bitlerden gelenlere \(B_x\) diyelim. O zaman
$$L_x=\max A_x$$
ve eğer \(B_x\neq\varnothing\) ise
$$R_x=\min B_x$$
tanımlanır. Tanım gereği gerekli eşitsizlikler
$$v_x>L_x$$
ve, \(B_x\neq\varnothing\) olduğunda ayrıca
$$v_x<R_x$$
şeklindedir. İkili yazımın ilk biti her zaman \(1\) olduğu için \(A_x\) hiçbir zaman boş değildir; yani her \(x\ge 1\) için en az bir alt sınır vardır.
Önce \(B_x\neq\varnothing\) durumunu ele alalım ve \(\frac{m}{2^k}\) biçiminde bir dyadik aday deneyelim. Şu koşul
$$L_x<\frac{m}{2^k}<R_x$$
tam olarak şu anlama gelir:
$$\left\lfloor 2^kL_x\right\rfloor+1\le m\le \left\lceil 2^kR_x\right\rceil-1.$$
Dolayısıyla sabit bir \(2^k\) paydası için uygun paylar, bu kapalı aralıkta kalan tam sayılardır. Böyle bir tam sayının ilk kez ortaya çıktığı en küçük \(k\), en kaba paydayı ve dolayısıyla en basit dyadik seviyeyi verir.
Eğer \(B_x=\varnothing\) ise, \(x\)'in ikili yazımında hiç \(0\)-bit yok demektir. Bu durumda üst sınır yoktur ve en basit uygun dyadik sayı, \(L_x\)'ten kesin olarak büyük olan en küçük tam sayıdır:
$$v_x=\lfloor L_x\rfloor+1.$$
En küçük uygun payda \(2^k\) bulunduktan sonra, birden fazla uygun pay olabilir. Uygulamalar mutlak değeri en küçük olan uygun tam sayıyı seçer: Mümkünse \(m=0\), değilse \(0\)'a en yakın uygun tam sayı alınır. Böylece aralıktaki en basit dyadik seçim tam olarak yeniden üretilmiş olur.
Bundan sonra pay ve paydadaki ortak tüm \(2\) çarpanları temizlenir. Yani her değer sadeleştirilmiş biçimde tutulur:
$$v_x=\frac{a_x}{2^{e_x}},$$
burada değer \(0\) değilse \(a_x\) tektir.
Bu sadeleştirme önemlidir, çünkü dyadik sayılar daha sonra tam olarak karşılaştırılabilir. Bunun için iki sayı ortak bir \(2\) kuvveti paydasına taşınır ve sadece ölçeklenmiş paylar tam sayı olarak karşılaştırılır. Hiçbir yerde kayan nokta hesabına ihtiyaç yoktur.
\(v_1,\dots,v_n\) hesaplandıktan sonra her değeri sadeleştirilmiş biçimde \(v_i=\frac{a_i}{2^{e_i}}\) olarak yazalım ve
$$E=\max_{1\le i\le n} e_i$$
olsun. O zaman
$$\sum_{i=1}^{n} i\,v_i=\frac{1}{2^E}\sum_{i=1}^{n} i\,a_i\,2^{E-e_i}=\frac{N_n}{2^E}$$
olur; burada \(N_n\) bir tam sayıdır.
Bu özyinelemede bütün \(v_i\) değerleri pozitiftir; dolayısıyla \(N_n\ge 0\). Bu yüzden
$$S(n)=\left\lceil \frac{N_n}{2^E}\right\rceil=\left\lfloor \frac{N_n+2^E-1}{2^E}\right\rfloor$$
eşitliği geçerlidir. Son tavan işlemi de tamamen tam sayı aritmetiği ile yapılır.
İlk birkaç değer doğrudan aralık kuralından çıkar:
$$\begin{aligned} v_1&=1,\\ v_2&=\frac{1}{2},\\ v_3&=2,\\ v_4&=\frac{1}{4},\\ v_5&=\frac{3}{2}. \end{aligned}$$
Örneğin \(x=5\) için ikili gösterim \(101_2\)'dir. Soldaki \(1\) silinince \(1\), ortadaki \(0\) silinince \(3\), sondaki \(1\) silinince \(2\) elde edilir. Bu yüzden alt sınır
$$L_5=\max(v_1,v_2)=1,$$
üst sınır ise
$$R_5=v_3=2$$
olur. \((1,2)\) aralığındaki en basit dyadik sayı da
$$v_5=\frac{3}{2}$$
olur.
İlk beş değer kullanılırsa
$$S(5)=\left\lceil 1\cdot 1+2\cdot \frac{1}{2}+3\cdot 2+4\cdot \frac{1}{4}+5\cdot \frac{3}{2}\right\rceil=\left\lceil \frac{33}{2}\right\rceil=17.$$
Aynı özyineleme sürdürülünce
$$v_6=1,\qquad v_7=3,\qquad v_8=\frac{1}{8},\qquad v_9=\frac{5}{4},\qquad v_{10}=\frac{3}{4}$$
elde edilir; dolayısıyla
$$S(10)=64$$
çıkar ve bu, uygulamadaki kontrol değeriyle aynıdır.
C++, Python ve Java uygulamaları \(1\)'den \(n\)'e kadar ilerler. Her \(x\) için bütün bit konumları taranır, bir bit silinerek öncül üretilir ve tam dyadik karşılaştırmalarla en iyi alt ve üst sınırlar güncellenir. Her öncül \(x\)'ten küçük olduğu için, \(x\) işlenirken gereken bütün değerler zaten hesaplanmış durumdadır.
Daha sonra \(1,2,4,\dots\) paydaları sırasıyla denenir ve aralığa düşen ilk uygun dyadik rasyonel seçilir. Seçilen değer anında sadeleştirilir; böylece saklanan payda gereksiz yere büyümez. Tablo tamamlandıktan sonra bütün \(i\,v_i\) terimleri ortak bir paydaya taşınır, tam sayı paylar toplanır ve tavan işlemi tam olarak uygulanır.
Verilen bir \(x\) için incelenecek silinmiş-bit öncül sayısı \(\lfloor\log_2 x\rfloor+1\) kadardır; bu yüzden \(v_x\) için aralığı kurmanın maliyeti \(O(\log x)\) olur. Dyadik payda araması uygulamalarda küçük bir sabit ile sınırlıdır. Böylece \(n\)'e kadar toplam çalışma süresi \(O(n\log n)\), dyadik değer tablosu için gereken bellek ise \(O(n)\) olur.
Para cada entero positivo \(x\), se consideran todos los números que se obtienen al borrar exactamente un bit de la representación binaria de \(x\). Esos números más pequeños son los predecesores de \(x\). Si el bit borrado era \(1\), aparece una restricción inferior; si era \(0\), aparece una restricción superior.
Partiendo del valor base \(v_0=0\), el valor \(v_x\) se define como el racional diádico más simple que satisface todas esas restricciones. Aquí un racional diádico es un número de la forma \(\frac{m}{2^k}\), con \(m\in\mathbb{Z}\) y \(k\ge 0\).
La cantidad buscada es
$$S(n)=\left\lceil \sum_{i=1}^{n} i\,v_i \right\rceil.$$
La recurrencia es local: una vez conocidos los predecesores obtenidos por borrado de bits, queda determinado el intervalo abierto en el que debe caer \(v_x\), y dentro de ese intervalo se escoge el racional diádico más simple.
Sean \(y_1,\dots,y_\ell\) los predecesores de \(x\), donde \(\ell\) es la longitud binaria de \(x\). Cada predecesor es menor que \(x\), porque al borrar un bit la representación resultante tiene a lo sumo \(\ell-1\) bits, así que
$$y_j<2^{\ell-1}\le x.$$
Por eso los valores se pueden calcular en orden creciente de \(x\).
Sea \(A_x\) el conjunto de valores de predecesores que provienen de borrar bits iguales a \(1\), y \(B_x\) el conjunto correspondiente a bits iguales a \(0\). Definimos
$$L_x=\max A_x,$$
y, cuando \(B_x\neq\varnothing\), también
$$R_x=\min B_x.$$
Las desigualdades que definen a \(v_x\) son
$$v_x>L_x,$$
y, si \(B_x\neq\varnothing\), además
$$v_x<R_x.$$
Como el bit inicial de toda representación binaria siempre es \(1\), el conjunto \(A_x\) nunca es vacío. Por lo tanto, todo \(x\ge 1\) tiene al menos una cota inferior.
Supongamos primero que \(B_x\neq\varnothing\) y probemos un candidato diádico \(\frac{m}{2^k}\). La condición
$$L_x<\frac{m}{2^k}<R_x$$
equivale a
$$\left\lfloor 2^kL_x\right\rfloor+1\le m\le \left\lceil 2^kR_x\right\rceil-1.$$
Así, para un denominador fijo \(2^k\), los numeradores válidos son exactamente los enteros de ese intervalo cerrado. El menor \(k\) para el cual existe alguno da el denominador más grueso posible y, por tanto, el nivel diádico más simple.
Si \(B_x=\varnothing\), entonces la expansión binaria de \(x\) no contiene ningún \(0\). En ese caso no existe cota superior y el racional diádico admisible más simple es simplemente el entero más pequeño estrictamente mayor que \(L_x\):
$$v_x=\lfloor L_x\rfloor+1.$$
Una vez encontrado el denominador mínimo \(2^k\), puede haber varios numeradores permitidos. Las implementaciones eligen el entero factible más cercano a \(0\): toman \(m=0\) si es posible; en caso contrario, el entero permitido de menor valor absoluto. Así se reproduce exactamente la noción de simplicidad usada en la construcción.
Después se eliminan todos los factores comunes de \(2\) entre numerador y denominador. Cada valor queda almacenado en forma reducida como
$$v_x=\frac{a_x}{2^{e_x}},$$
donde \(a_x\) es impar salvo que el valor sea \(0\).
Esta reducción importa porque permite comparar racionales diádicos de forma exacta: basta llevarlos a un denominador común que sea una potencia de \(2\) y comparar los numeradores escalados como enteros. No hace falta aritmética en coma flotante.
Cuando ya se conocen \(v_1,\dots,v_n\), escribimos cada valor como \(v_i=\frac{a_i}{2^{e_i}}\) en forma reducida y definimos
$$E=\max_{1\le i\le n} e_i.$$
Entonces
$$\sum_{i=1}^{n} i\,v_i=\frac{1}{2^E}\sum_{i=1}^{n} i\,a_i\,2^{E-e_i}=\frac{N_n}{2^E},$$
donde \(N_n\) es un entero.
En esta recurrencia todos los \(v_i\) son positivos, así que \(N_n\ge 0\). Por consiguiente,
$$S(n)=\left\lceil \frac{N_n}{2^E}\right\rceil=\left\lfloor \frac{N_n+2^E-1}{2^E}\right\rfloor.$$
La operación techo final se resuelve, por tanto, solo con aritmética entera.
Los primeros valores salen directamente de la regla del intervalo:
$$\begin{aligned} v_1&=1,\\ v_2&=\frac{1}{2},\\ v_3&=2,\\ v_4&=\frac{1}{4},\\ v_5&=\frac{3}{2}. \end{aligned}$$
Por ejemplo, \(x=5\) tiene forma binaria \(101_2\). Borrar el \(1\) de la izquierda produce \(1\), borrar el \(0\) central produce \(3\), y borrar el \(1\) de la derecha produce \(2\). Así, la cota inferior es
$$L_5=\max(v_1,v_2)=1,$$
la cota superior es
$$R_5=v_3=2,$$
y el diádico más simple dentro de \((1,2)\) es
$$v_5=\frac{3}{2}.$$
Con los cinco primeros valores,
$$S(5)=\left\lceil 1\cdot 1+2\cdot \frac{1}{2}+3\cdot 2+4\cdot \frac{1}{4}+5\cdot \frac{3}{2}\right\rceil=\left\lceil \frac{33}{2}\right\rceil=17.$$
Si continuamos la misma recurrencia obtenemos
$$v_6=1,\qquad v_7=3,\qquad v_8=\frac{1}{8},\qquad v_9=\frac{5}{4},\qquad v_{10}=\frac{3}{4},$$
y por tanto
$$S(10)=64,$$
que coincide con el valor de comprobación de la implementación.
Las implementaciones en C++, Python y Java recorren los enteros desde \(1\) hasta \(n\). Para cada \(x\), inspeccionan todas las posiciones de bits, forman cada predecesor por borrado y actualizan la mejor cota inferior y la mejor cota superior mediante comparaciones diádicas exactas. Como todo predecesor es menor que \(x\), cuando se procesa \(x\) ya están disponibles todos los valores necesarios.
Luego se prueban denominadores \(1,2,4,\dots\) hasta que el intervalo contiene algún racional diádico admisible. El valor elegido se reduce de inmediato para que el denominador almacenado sea lo más pequeño posible. Cuando la tabla completa está lista, cada término \(i\,v_i\) se lleva a un denominador común, se suman numeradores enteros y se aplica exactamente la fórmula del techo.
Para un \(x\) dado hay \(\lfloor\log_2 x\rfloor+1\) predecesores por borrado de bits, así que construir el intervalo de \(v_x\) cuesta \(O(\log x)\). La búsqueda adicional sobre denominadores diádicos está acotada por una pequeña constante fija en las implementaciones. En consecuencia, el tiempo total hasta \(n\) es \(O(n\log n)\), y la tabla de valores diádicos utiliza \(O(n)\) memoria.
对每个正整数 \(x\)，都要考察把 \(x\) 的二进制表示中恰好一位删掉后得到的所有整数。这些更小的整数就是 \(x\) 的前驱。若删掉的是 \(1\)-位，就产生一个下界约束；若删掉的是 \(0\)-位，就产生一个上界约束。
从基值 \(v_0=0\) 出发，\(v_x\) 被定义为满足全部约束的“最简单”二进有理数。这里二进有理数指形如 \(\frac{m}{2^k}\) 的数，其中 \(m\in\mathbb{Z}\)、\(k\ge 0\)。
最终要求的是
$$S(n)=\left\lceil \sum_{i=1}^{n} i\,v_i \right\rceil.$$
这套递推本质上是局部构造：一旦知道了由删位得到的前驱值，就能写出 \(v_x\) 必须落入的开区间，然后在这个区间里挑出最简单的二进有理数。
设 \(x\) 的删位前驱为 \(y_1,\dots,y_\ell\)，其中 \(\ell\) 是 \(x\) 的二进制长度。每个前驱都严格小于 \(x\)，因为删去一位后，剩下的表示至多只有 \(\ell-1\) 位，所以
$$y_j<2^{\ell-1}\le x.$$
这就说明可以按 \(x=1,2,3,\dots\) 的顺序递推计算。
把“删去 \(1\)-位”得到的前驱值集合记为 \(A_x\)，把“删去 \(0\)-位”得到的前驱值集合记为 \(B_x\)。定义
$$L_x=\max A_x,$$
如果 \(B_x\neq\varnothing\)，再定义
$$R_x=\min B_x.$$
于是 \(v_x\) 必须满足
$$v_x>L_x,$$
并且在 \(B_x\neq\varnothing\) 时还要满足
$$v_x<R_x.$$
由于二进制表示的最高位一定是 \(1\)，所以 \(A_x\) 永远不为空，这意味着每个 \(x\ge 1\) 至少都有一个下界。
先看 \(B_x\neq\varnothing\) 的情形。若候选值写成 \(\frac{m}{2^k}\)，那么
$$L_x<\frac{m}{2^k}<R_x$$
等价于
$$\left\lfloor 2^kL_x\right\rfloor+1\le m\le \left\lceil 2^kR_x\right\rceil-1.$$
因此，对固定分母 \(2^k\) 而言，所有可行分子恰好就是这个闭区间中的整数。第一个出现可行整数的 \(k\)，就给出了最粗的二进分母层级，也就是“最简单”的分母。
如果 \(B_x=\varnothing\)，说明 \(x\) 的二进制展开里根本没有 \(0\)-位。此时没有上界，最简单的可行二进有理数就是严格大于 \(L_x\) 的最小整数：
$$v_x=\lfloor L_x\rfloor+1.$$
当最小可行分母 \(2^k\) 已经确定后，往往还会有多个可行分子。实现所采用的规则是：优先选择最接近 \(0\) 的可行整数；如果 \(0\) 本身可行就取 \(m=0\)，否则取绝对值最小的那个可行整数。这样就把“最简单”的选择规则完全落到了整数层面。
随后把分子和分母中的公共 \(2\) 因子全部消掉，于是每个值都以约分后的形式存储：
$$v_x=\frac{a_x}{2^{e_x}},$$
除非该值为 \(0\)，否则 \(a_x\) 一定是奇数。
这种存储方式非常重要，因为两个二进有理数的比较可以完全精确地完成：只要把它们提升到同一个 \(2\) 的幂分母，再比较放大后的整数分子即可，整个过程都不需要浮点数。
当 \(v_1,\dots,v_n\) 全部求出之后，把每个值写成约分形式 \(v_i=\frac{a_i}{2^{e_i}}\)，并设
$$E=\max_{1\le i\le n} e_i.$$
于是
$$\sum_{i=1}^{n} i\,v_i=\frac{1}{2^E}\sum_{i=1}^{n} i\,a_i\,2^{E-e_i}=\frac{N_n}{2^E},$$
其中 \(N_n\) 是整数。
在这道题的递推中，所有 \(v_i\) 都是正数，所以 \(N_n\ge 0\)。因此
$$S(n)=\left\lceil \frac{N_n}{2^E}\right\rceil=\left\lfloor \frac{N_n+2^E-1}{2^E}\right\rfloor.$$
这说明最终的上取整同样可以只用整数算术精确完成。
前几个值可以直接按区间规则算出：
$$\begin{aligned} v_1&=1,\\ v_2&=\frac{1}{2},\\ v_3&=2,\\ v_4&=\frac{1}{4},\\ v_5&=\frac{3}{2}. \end{aligned}$$
以 \(x=5\) 为例，它的二进制形式是 \(101_2\)。删掉最左边的 \(1\) 得到 \(1\)，删掉中间的 \(0\) 得到 \(3\)，删掉最右边的 \(1\) 得到 \(2\)。因此下界是
$$L_5=\max(v_1,v_2)=1,$$
上界是
$$R_5=v_3=2,$$
而开区间 \((1,2)\) 中最简单的二进有理数就是
$$v_5=\frac{3}{2}.$$
用前五项计算，得到
$$S(5)=\left\lceil 1\cdot 1+2\cdot \frac{1}{2}+3\cdot 2+4\cdot \frac{1}{4}+5\cdot \frac{3}{2}\right\rceil=\left\lceil \frac{33}{2}\right\rceil=17.$$
继续递推还能得到
$$v_6=1,\qquad v_7=3,\qquad v_8=\frac{1}{8},\qquad v_9=\frac{5}{4},\qquad v_{10}=\frac{3}{4},$$
于是
$$S(10)=64,$$
这与实现中的校验值完全一致。
C++、Python 和 Java 实现都按 \(1\) 到 \(n\) 的顺序处理。对于每个 \(x\)，它们扫描所有比特位置，生成删位前驱，并用精确的二进有理数比较来维护最佳下界和最佳上界。因为每个前驱都严格小于 \(x\)，所以处理 \(x\) 时需要的值已经全部求好。
接着，程序按 \(1,2,4,\dots\) 这样的分母顺序尝试，直到当前区间中第一次出现可行的二进有理数。选中的值会立刻约分，使存储时的分母尽可能小。整张表构造完成后，再把所有 \(i\,v_i\) 提升到同一个分母，累加整数分子，并用精确的整数公式完成上取整。
对给定的 \(x\) 来说，需要检查的删位前驱个数是 \(\lfloor\log_2 x\rfloor+1\)，因此构造 \(v_x\) 的可行区间需要 \(O(\log x)\) 时间。实现中对二进分母的额外搜索只是一小段固定上界的循环，所以总时间复杂度为 \(O(n\log n)\)。存储整张二进有理数表需要 \(O(n)\) 空间。
Для каждого положительного целого \(x\) рассматриваются все числа, которые получаются после удаления ровно одного бита из двоичной записи \(x\). Эти меньшие числа играют роль предшественников. Если удален бит \(1\), возникает нижнее ограничение; если удален бит \(0\), возникает верхнее ограничение.
Начиная с базового значения \(v_0=0\), величина \(v_x\) определяется как простейшее диадическое рациональное число, удовлетворяющее всем этим ограничениям. Под диадическим рациональным числом понимается число вида \(\frac{m}{2^k}\), где \(m\in\mathbb{Z}\) и \(k\ge 0\).
Нужно вычислить
$$S(n)=\left\lceil \sum_{i=1}^{n} i\,v_i \right\rceil.$$
Рекурсия здесь локальная: как только известны предшественники, полученные удалением одного бита, сразу определяется открытый интервал, в котором обязан лежать \(v_x\), а затем внутри этого интервала выбирается простейшее диадическое число.
Пусть \(y_1,\dots,y_\ell\) - все предшественники числа \(x\), где \(\ell\) есть длина двоичной записи \(x\). Каждый такой предшественник строго меньше \(x\), потому что после удаления одного бита остается не более \(\ell-1\) двоичных разрядов, а значит
$$y_j<2^{\ell-1}\le x.$$
Отсюда следует, что значения можно вычислять в порядке возрастания \(x\).
Обозначим через \(A_x\) множество значений предшественников, полученных удалением бита \(1\), а через \(B_x\) - множество значений предшественников, полученных удалением бита \(0\). Тогда
$$L_x=\max A_x,$$
а если \(B_x\neq\varnothing\), то
$$R_x=\min B_x.$$
Определяющие неравенства имеют вид
$$v_x>L_x,$$
и, если \(B_x\neq\varnothing\), дополнительно
$$v_x<R_x.$$
Поскольку старший бит двоичной записи всегда равен \(1\), множество \(A_x\) никогда не пусто. Значит, для каждого \(x\ge 1\) нижняя граница существует всегда.
Сначала рассмотрим случай \(B_x\neq\varnothing\) и проверим диадический кандидат \(\frac{m}{2^k}\). Условие
$$L_x<\frac{m}{2^k}<R_x$$
равносильно системе
$$\left\lfloor 2^kL_x\right\rfloor+1\le m\le \left\lceil 2^kR_x\right\rceil-1.$$
Следовательно, для фиксированного знаменателя \(2^k\) допустимыми числителями являются ровно целые числа из этого замкнутого интервала. Наименьшее \(k\), при котором хотя бы один такой числитель существует, дает самый грубый знаменатель и тем самым самый простой диадический уровень.
Если же \(B_x=\varnothing\), то в двоичной записи \(x\) нет ни одного нуля. Верхней границы тогда нет, и простейшее допустимое диадическое число - это просто наименьшее целое, строго большее \(L_x\):
$$v_x=\lfloor L_x\rfloor+1.$$
После того как найден минимальный допустимый знаменатель \(2^k\), может существовать несколько подходящих числителей. Реализации выбирают допустимое целое, ближайшее к \(0\): если возможно, берут \(m=0\), иначе - допустимое целое с наименьшим абсолютным значением. Именно так формализуется правило выбора простейшего диадического числа.
Затем из числителя и знаменателя убираются все общие множители \(2\). Поэтому каждый результат хранится в сокращенном виде
$$v_x=\frac{a_x}{2^{e_x}},$$
где \(a_x\) нечетно, если только само значение не равно \(0\).
Это сокращение существенно, потому что сравнение диадических чисел становится точным: достаточно привести оба числа к общему знаменателю - степени двойки - и сравнить масштабированные числители как целые числа. Никакой арифметики с плавающей точкой не требуется.
Когда все \(v_1,\dots,v_n\) уже найдены, запишем каждое значение в сокращенном виде \(v_i=\frac{a_i}{2^{e_i}}\) и положим
$$E=\max_{1\le i\le n} e_i.$$
Тогда
$$\sum_{i=1}^{n} i\,v_i=\frac{1}{2^E}\sum_{i=1}^{n} i\,a_i\,2^{E-e_i}=\frac{N_n}{2^E},$$
где \(N_n\) - целое число.
В данной рекурсии все \(v_i\) положительны, следовательно \(N_n\ge 0\). Поэтому
$$S(n)=\left\lceil \frac{N_n}{2^E}\right\rceil=\left\lfloor \frac{N_n+2^E-1}{2^E}\right\rfloor.$$
Итак, завершающий потолок тоже вычисляется чисто целочисленно.
Первые значения непосредственно следуют из интервального правила:
$$\begin{aligned} v_1&=1,\\ v_2&=\frac{1}{2},\\ v_3&=2,\\ v_4&=\frac{1}{4},\\ v_5&=\frac{3}{2}. \end{aligned}$$
Например, для \(x=5\) двоичная запись равна \(101_2\). Удаление левой \(1\) дает \(1\), удаление среднего \(0\) дает \(3\), удаление правой \(1\) дает \(2\). Поэтому нижняя граница равна
$$L_5=\max(v_1,v_2)=1,$$
верхняя граница равна
$$R_5=v_3=2,$$
а простейшее диадическое число в интервале \((1,2)\) есть
$$v_5=\frac{3}{2}.$$
Тогда
$$S(5)=\left\lceil 1\cdot 1+2\cdot \frac{1}{2}+3\cdot 2+4\cdot \frac{1}{4}+5\cdot \frac{3}{2}\right\rceil=\left\lceil \frac{33}{2}\right\rceil=17.$$
Если продолжить ту же рекурсию, получаем
$$v_6=1,\qquad v_7=3,\qquad v_8=\frac{1}{8},\qquad v_9=\frac{5}{4},\qquad v_{10}=\frac{3}{4},$$
и, следовательно,
$$S(10)=64,$$
что совпадает с контрольным значением из реализации.
Реализации на C++, Python и Java проходят числа от \(1\) до \(n\). Для каждого \(x\) они просматривают все позиции битов, строят предшественников удалением одного бита и с помощью точных сравнений диадических чисел обновляют лучшую нижнюю и лучшую верхнюю границы. Поскольку каждый предшественник меньше самого \(x\), в момент обработки \(x\) все нужные значения уже вычислены.
Затем проверяются знаменатели \(1,2,4,\dots\), пока интервал не начнет содержать допустимое диадическое рациональное число. Найденное значение сразу сокращается, чтобы хранимый знаменатель был минимальным. После построения всей таблицы каждый член \(i\,v_i\) переводится к общему знаменателю, целочисленные числители суммируются, и формула для потолка применяется точно.
Для данного \(x\) нужно просмотреть \(\lfloor\log_2 x\rfloor+1\) предшественников, получаемых удалением бита, так что построение интервала для \(v_x\) стоит \(O(\log x)\). Дополнительный перебор диадических знаменателей в реализациях ограничен небольшой фиксированной константой. Поэтому суммарное время до \(n\) равно \(O(n\log n)\), а таблица диадических значений требует \(O(n)\) памяти.
لكل عدد صحيح موجب \(x\)، ننظر إلى جميع الأعداد التي تنتج من حذف بت واحد بالضبط من التمثيل الثنائي لـ \(x\). هذه الأعداد الأصغر تمثل السوابق الخاصة بـ \(x\). إذا كان البت المحذوف هو \(1\) نحصل على قيد سفلي، وإذا كان \(0\) نحصل على قيد علوي.
انطلاقًا من القيمة الأساسية \(v_0=0\)، تُعرَّف \(v_x\) على أنها أبسط قيمة كسرية ثنائية تحقق جميع هذه القيود. والمقصود بالكسر الثنائي هنا عدد من الشكل \(\frac{m}{2^k}\) حيث \(m\in\mathbb{Z}\) و\(k\ge 0\).
والكمية المطلوبة هي
$$S(n)=\left\lceil \sum_{i=1}^{n} i\,v_i \right\rceil.$$
العلاقة العودية محلية: ما إن تُعرف السوابق الناتجة من حذف البتات حتى يتحدد المجال المفتوح الذي يجب أن تقع فيه \(v_x\)، ثم نختار أبسط عدد ثنائي داخل هذا المجال.
لتكن \(y_1,\dots,y_\ell\) هي السوابق الناتجة من حذف بت واحد من \(x\)، حيث تمثل \(\ell\) طول \(x\) بالثنائي. كل سابق أصغر من \(x\)، لأن حذف بت واحد يترك تمثيلًا طوله على الأكثر \(\ell-1\) بت، ومن ثم
$$y_j<2^{\ell-1}\le x.$$
ولهذا السبب يمكن حساب القيم بترتيب تصاعدي بالنسبة إلى \(x\).
لنرمز إلى مجموعة قيم السوابق القادمة من حذف بتات تساوي \(1\) بالرمز \(A_x\)، وإلى مجموعة القيم القادمة من حذف بتات تساوي \(0\) بالرمز \(B_x\). عندئذ نعرّف
$$L_x=\max A_x,$$
وإذا كان \(B_x\neq\varnothing\) نعرّف أيضًا
$$R_x=\min B_x.$$
وعليه يجب أن تحقق \(v_x\) الشرطين
$$v_x>L_x,$$
وإذا كان \(B_x\neq\varnothing\) فهناك أيضًا
$$v_x<R_x.$$
وبما أن أول بت في أي تمثيل ثنائي هو دائمًا \(1\)، فإن المجموعة \(A_x\) لا تكون فارغة أبدًا، أي إن لكل \(x\ge 1\) حدًا سفليًا على الأقل.
لنفرض أولًا أن \(B_x\neq\varnothing\)، ولنختبر مرشحًا ثنائيًا من الشكل \(\frac{m}{2^k}\). عندئذ تكون المتراجحة
$$L_x<\frac{m}{2^k}<R_x$$
مكافئة تمامًا لـ
$$\left\lfloor 2^kL_x\right\rfloor+1\le m\le \left\lceil 2^kR_x\right\rceil-1.$$
إذن، عند تثبيت المقام \(2^k\)، تكون البسوط المقبولة هي بالضبط الأعداد الصحيحة الواقعة في هذا المجال المغلق. وأصغر \(k\) يظهر معه حل صحيح يعطي أبسط مستوى ممكن للمقام الثنائي.
أما إذا كان \(B_x=\varnothing\)، فهذا يعني أن التمثيل الثنائي لـ \(x\) لا يحتوي على أي بت يساوي \(0\). في هذه الحالة لا يوجد حد علوي، وأبسط قيمة ثنائية مقبولة هي أصغر عدد صحيح أكبر من \(L_x\) بصرامة:
$$v_x=\lfloor L_x\rfloor+1.$$
بعد معرفة أصغر مقام ممكن \(2^k\)، قد يوجد أكثر من بسط صالح. تختار التطبيقات العدد الصحيح المقبول الأقرب إلى \(0\): إذا أمكن أخذ \(m=0\) فذلك هو الاختيار، وإلا يُختار العدد الصحيح المقبول ذو أصغر قيمة مطلقة. وبهذا تتحول فكرة "الأبسط" إلى قاعدة صحيحة واضحة على مستوى الأعداد الصحيحة.
بعد ذلك تزال كل عوامل \(2\) المشتركة بين البسط والمقام. لذلك تُخزَّن كل قيمة في الصورة المختزلة
$$v_x=\frac{a_x}{2^{e_x}},$$
حيث يكون \(a_x\) عددًا فرديًا إلا إذا كانت القيمة نفسها تساوي \(0\).
هذا الاختزال مهم لأن مقارنة الكسور الثنائية تصبح دقيقة تمامًا: نرفع الكسرين إلى مقام مشترك هو قوة للعدد \(2\)، ثم نقارن البسوط بعد التكبير كأعداد صحيحة. لا حاجة إلى أي تقريب عشري.
بعد حساب \(v_1,\dots,v_n\)، نكتب كل قيمة بالشكل المختزل \(v_i=\frac{a_i}{2^{e_i}}\)، ثم نضع
$$E=\max_{1\le i\le n} e_i.$$
عندئذ
$$\sum_{i=1}^{n} i\,v_i=\frac{1}{2^E}\sum_{i=1}^{n} i\,a_i\,2^{E-e_i}=\frac{N_n}{2^E},$$
حيث إن \(N_n\) عدد صحيح.
وفي هذه العودية تكون كل القيم \(v_i\) موجبة، لذا \(N_n\ge 0\). ومن ثم
$$S(n)=\left\lceil \frac{N_n}{2^E}\right\rceil=\left\lfloor \frac{N_n+2^E-1}{2^E}\right\rfloor.$$
وهكذا يمكن تنفيذ عملية السقف النهائية بدقة تامة باستخدام الحساب الصحيح فقط.
أول القيم تُستخرج مباشرة من قاعدة المجال:
$$\begin{aligned} v_1&=1,\\ v_2&=\frac{1}{2},\\ v_3&=2,\\ v_4&=\frac{1}{4},\\ v_5&=\frac{3}{2}. \end{aligned}$$
خذ مثلًا \(x=5\) ذي التمثيل الثنائي \(101_2\). حذف الـ\(1\) اليسرى يعطي \(1\)، وحذف الـ\(0\) الوسطى يعطي \(3\)، وحذف الـ\(1\) اليمنى يعطي \(2\). لذلك يكون الحد السفلي
$$L_5=\max(v_1,v_2)=1,$$
والحد العلوي
$$R_5=v_3=2,$$
وأبسط كسر ثنائي داخل المجال \((1,2)\) هو
$$v_5=\frac{3}{2}.$$
وباستخدام أول خمس قيم نحصل على
$$S(5)=\left\lceil 1\cdot 1+2\cdot \frac{1}{2}+3\cdot 2+4\cdot \frac{1}{4}+5\cdot \frac{3}{2}\right\rceil=\left\lceil \frac{33}{2}\right\rceil=17.$$
ومع متابعة العودية نجد
$$v_6=1,\qquad v_7=3,\qquad v_8=\frac{1}{8},\qquad v_9=\frac{5}{4},\qquad v_{10}=\frac{3}{4},$$
ومن ثم
$$S(10)=64,$$
وهو نفس مقدار التحقق المستخدم في التنفيذ.
تسير تطبيقات C++ وPython وJava من \(1\) إلى \(n\). ولكل \(x\)، تفحص جميع مواضع البتات، وتولد السابق الناتج من حذف بت واحد، ثم تحدّث أفضل حد سفلي وأفضل حد علوي بواسطة مقارنات دقيقة بين الكسور الثنائية. وبما أن كل سابق أصغر من \(x\)، فإن جميع القيم المطلوبة تكون معروفة بالفعل عند معالجة \(x\).
بعد ذلك تُجرَّب المقامات \(1,2,4,\dots\) حتى يظهر أول كسر ثنائي مقبول داخل المجال. وتُختزل القيمة المختارة فورًا حتى يبقى المقام المخزَّن أصغر ما يمكن. وبعد اكتمال الجدول، تُرفع جميع الحدود \(i\,v_i\) إلى مقام مشترك، وتُجمع البسوط الصحيحة، ثم تُطبَّق صيغة السقف بدقة كاملة.
بالنسبة إلى عدد معين \(x\)، يوجد \(\lfloor\log_2 x\rfloor+1\) سابقًا ناتجًا من حذف البتات، ولذلك فإن بناء المجال المناسب لـ \(v_x\) يكلف \(O(\log x)\). أما البحث الإضافي في مقامات القوى الثنائية فهو محدود في التطبيقات بحلقة قصيرة ذات حد ثابت صغير. لذا يكون الزمن الكلي حتى \(n\) من رتبة \(O(n\log n)\)، بينما يحتاج جدول القيم الثنائية إلى \(O(n)\) من الذاكرة.