For a bound \(n\), we consider all pairs of nonnegative integers \((u,v)\) with \(u \le v \le n\) that satisfy the carry-less equation
$$u \otimes u \oplus \bigl((2u) \otimes v\bigr) \oplus (v \otimes v)=5.$$
Here \(\oplus\) is bitwise XOR and \(\otimes\) is carry-less multiplication, meaning binary digits are multiplied without carries. The required value is
$$X(n)=\bigoplus_{\substack{(u,v)\text{ solves the equation}\\v\le n}} v.$$
A direct search over all pairs up to \(n\) would cost \(O(n^2)\), so the real task is to describe the complete solution set in a structured way and then aggregate the second coordinates.
The decisive simplification is to reinterpret binary integers as polynomials over \(\mathbb{F}_2\). In that model, XOR becomes addition, carry-less multiplication becomes ordinary polynomial multiplication, and the equation turns into a quadratic form preserved by a simple recurrence.
Write the binary expansions
$$u=\sum_{i\ge 0} u_i 2^i,\qquad v=\sum_{i\ge 0} v_i 2^i,\qquad u_i,v_i\in\{0,1\},$$
and associate to them the polynomials
$$U(t)=\sum_{i\ge 0} u_i t^i,\qquad V(t)=\sum_{i\ge 0} v_i t^i.$$
Under this dictionary, bitwise XOR is just addition in \(\mathbb{F}_2[t]\):
$$u\oplus v \leftrightarrow U(t)+V(t).$$
Carry-less multiplication is exactly polynomial multiplication:
$$u\otimes v \leftrightarrow U(t)V(t).$$
Also, multiplying an integer by \(2\) shifts every bit left by one place, so it corresponds to multiplication by \(t\):
$$2u \leftrightarrow tU(t).$$
Because \(5=101_2\), the constant on the right becomes
$$5 \leftrightarrow 1+t^2.$$
Therefore the original equation is equivalent to
$$U(t)^2+tU(t)V(t)+V(t)^2=1+t^2.$$
It is convenient to define the quadratic form
$$Q(U,V)=U^2+tUV+V^2.$$
The problem is now: find all polynomial pairs \((U,V)\) over \(\mathbb{F}_2[t]\) such that \(Q(U,V)=1+t^2\), then XOR the corresponding integer values of \(v\).
Consider the map
$$T(U,V)=\bigl(V,tV+U\bigr).$$
A direct calculation in characteristic \(2\) shows that it preserves \(Q\):
$$\begin{aligned} Q\bigl(V,tV+U\bigr) &=V^2+tV(tV+U)+(tV+U)^2\\ &=V^2+t^2V^2+tUV+t^2V^2+U^2\\ &=U^2+tUV+V^2\\ &=Q(U,V). \end{aligned}$$
The cancellation of the two \(t^2V^2\) terms is the key point. So every solution generates another solution after one application of \(T\).
The pair
$$\bigl(0,1+t\bigr)$$
is an obvious base solution because
$$Q(0,1+t)=(1+t)^2=1+t^2.$$
Mapping back from polynomials to integers gives the first valid pair
$$(0,3).$$
The inverse map is just as simple:
$$T^{-1}(U,V)=\bigl(V+tU,U\bigr).$$
It also preserves \(Q\). Now suppose \((U,V)\) is any nonzero solution and \(\deg U \le \deg V=d\). Since the right-hand side \(1+t^2\) has degree \(2\), the leading term of \(V^2\), which has degree \(2d\), must disappear whenever \(d>1\).
The only other term that can cancel degree \(2d\) is \(tUV\). Therefore
$$\deg U=d-1.$$
That means the leading terms of \(V\) and \(tU\) are equal, so in characteristic \(2\) they cancel and
$$\deg(V+tU)<d.$$
Applying \(T^{-1}\) to \((U,V)\) yields another solution whose maximum degree is strictly smaller. Repeating this descent eventually reaches a solution with \(\deg V=1\).
At that point we can write
$$U=c,\qquad V=t+d,\qquad c,d\in\{0,1\},$$
and substitute into \(Q(U,V)=1+t^2\). Comparing coefficients shows that the unique possibility is
$$U=0,\qquad V=1+t.$$
So every admissible pair lies in the orbit generated by repeated applications of \(T\) to the base solution.
If \((u_k,v_k)\) is the integer pair corresponding to \((U_k,V_k)\), then multiplying \(V_k\) by \(t\) means left-shifting by one bit. So the polynomial recurrence becomes the integer recurrence
$$u_{k+1}=v_k,\qquad v_{k+1}=(2v_k)\oplus u_k,$$
with initial values
$$(u_0,v_0)=(0,3).$$
The first few pairs are
$$(0,3),\ (3,6),\ (6,15),\ (15,24),\ (24,63),\dots$$
Every valid pair with \(u\le v\) appears exactly once in this sequence. The same degree argument also explains why the sequence grows quickly: if \(\deg v_k=d\), then \(\deg u_k=d-1\), so the new highest term in \(2v_k\) survives the XOR and \(\deg v_{k+1}=d+1\). Thus the second coordinate gains one binary digit at each step.
Take \(n=10\). Starting from the base pair, the recurrence gives
$$(0,3)\to(3,6)\to(6,15).$$
The third second-coordinate already exceeds \(10\), so the only relevant solutions are
$$(0,3)\quad\text{and}\quad(3,6).$$
Therefore
$$X(10)=3\oplus 6=5.$$
This small case matches the built-in checkpoint used by the implementations and illustrates the whole method: generate the orbit, stop at the bound, XOR the second coordinates.
The C++, Python, and Java implementations all use the same compact loop. They store the current solution pair, maintain a running XOR accumulator, and repeatedly apply
$$ (u,v)\mapsto \bigl(v,(2v)\oplus u\bigr). $$
Whenever the current second coordinate satisfies \(v\le n\), it is folded into the accumulator. As soon as the next second coordinate exceeds the bound, the loop stops and the accumulator is returned.
This is correct because the mathematical argument above proves both directions: the recurrence never leaves the solution set, and every admissible solution belongs to that same orbit. One implementation also performs a tiny brute-force check on small bounds, but the real computation for the Euler input uses only the recurrence.
Each iteration performs constant work: one left shift, one XOR to create the next solution, one XOR into the answer, and one comparison with the bound. Since the second coordinate gains one bit per step, the number of iterations up to \(n\) is \(O(\log n)\). The memory usage is \(O(1)\).
Für eine Schranke \(n\) betrachten wir alle Paare nichtnegativer ganzer Zahlen \((u,v)\) mit \(u \le v \le n\), die die übertragslose Gleichung
$$u \otimes u \oplus \bigl((2u) \otimes v\bigr) \oplus (v \otimes v)=5$$
erfüllen. Dabei steht \(\oplus\) für bitweises XOR und \(\otimes\) für übertragslose Multiplikation. Gesucht ist
$$X(n)=\bigoplus_{\substack{(u,v)\text{ die Gleichung loest}\\v\le n}} v.$$
Ein direkter Durchlauf über alle Paare bis \(n\) hätte Aufwand \(O(n^2)\). Deshalb muss man die Lösungsmenge zuerst vollständig beschreiben und erst danach die zweiten Koordinaten zusammenfassen.
Der entscheidende Schritt ist die Übersetzung von Binärzahlen in Polynome über \(\mathbb{F}_2\). In diesem Modell wird XOR zur Addition, die übertragslose Multiplikation zur gewöhnlichen Polynom-Multiplikation, und die ganze Aufgabe reduziert sich auf eine quadratische Form mit einer einfachen Invariante.
Schreibe die Binärdarstellungen als
$$u=\sum_{i\ge 0} u_i 2^i,\qquad v=\sum_{i\ge 0} v_i 2^i,\qquad u_i,v_i\in\{0,1\},$$
und ordne ihnen die Polynome
$$U(t)=\sum_{i\ge 0} u_i t^i,\qquad V(t)=\sum_{i\ge 0} v_i t^i$$
zu. Dann gilt
$$u\oplus v \leftrightarrow U(t)+V(t),$$
weil XOR genau die Addition in \(\mathbb{F}_2[t]\) ist. Ebenso gilt
$$u\otimes v \leftrightarrow U(t)V(t),$$
denn bei der übertragslosen Multiplikation werden die Bits wie Koeffizienten eines Polynoms multipliziert. Multiplikation einer ganzen Zahl mit \(2\) verschiebt alle Bits um eine Position nach links und entspricht daher
$$2u \leftrightarrow tU(t).$$
Da \(5=101_2\) ist, wird die rechte Seite zu
$$5 \leftrightarrow 1+t^2.$$
Damit ist die ursprüngliche Gleichung äquivalent zu
$$U(t)^2+tU(t)V(t)+V(t)^2=1+t^2.$$
Wir definieren die quadratische Form
$$Q(U,V)=U^2+tUV+V^2.$$
Nun geht es also darum, alle Polynompaare \((U,V)\) mit \(Q(U,V)=1+t^2\) zu finden.
Betrachte die Abbildung
$$T(U,V)=\bigl(V,tV+U\bigr).$$
In Charakteristik \(2\) bleibt \(Q\) unter dieser Abbildung erhalten:
$$\begin{aligned} Q\bigl(V,tV+U\bigr) &=V^2+tV(tV+U)+(tV+U)^2\\ &=V^2+t^2V^2+tUV+t^2V^2+U^2\\ &=U^2+tUV+V^2\\ &=Q(U,V). \end{aligned}$$
Die beiden Terme \(t^2V^2\) heben sich weg; genau das macht die Rekursion möglich. Also erzeugt jede Anwendung von \(T\) aus einer Lösung wieder eine Lösung.
Die Basislösung ist
$$\bigl(0,1+t\bigr),$$
denn
$$Q(0,1+t)=(1+t)^2=1+t^2.$$
Zurück in ganzen Zahlen entspricht das dem Paar
$$(0,3).$$
Die Umkehrabbildung lautet
$$T^{-1}(U,V)=\bigl(V+tU,U\bigr),$$
und auch sie erhält \(Q\). Sei nun \((U,V)\) irgendeine nichttriviale Lösung mit \(\deg U \le \deg V=d\). Wenn \(d>1\), dann hat \(V^2\) Grad \(2d\), während die rechte Seite \(1+t^2\) nur Grad \(2\) besitzt.
Der führende Term von \(V^2\) kann nur durch den führenden Term von \(tUV\) verschwinden. Daher muss gelten
$$\deg U=d-1.$$
Damit haben \(V\) und \(tU\) denselben führenden Term, also folgt in Charakteristik \(2\)
$$\deg(V+tU)<d.$$
Wendet man \(T^{-1}\) an, erhält man wieder eine Lösung, aber mit strikt kleinerem Maximalgrad. Durch wiederholten Abstieg landet man schließlich bei einer Lösung mit \(\deg V=1\).
Dann kann man schreiben
$$U=c,\qquad V=t+d,\qquad c,d\in\{0,1\},$$
und in \(Q(U,V)=1+t^2\) einsetzen. Der Koeffizientenvergleich liefert als einzige Möglichkeit
$$U=0,\qquad V=1+t.$$
Also liegt jede zulässige Lösung in genau derselben Bahn, die von der Basislösung ausgeht.
Sei \((u_k,v_k)\) das ganzzahlige Paar zu \((U_k,V_k)\). Multiplikation mit \(t\) ist dann einfach ein Linksshift um ein Bit. Deshalb wird die Polynom-Rekursion zu
$$u_{k+1}=v_k,\qquad v_{k+1}=(2v_k)\oplus u_k,$$
mit Anfangswerten
$$(u_0,v_0)=(0,3).$$
Die ersten Paare lauten
$$(0,3),\ (3,6),\ (6,15),\ (15,24),\ (24,63),\dots$$
Jedes gültige Paar mit \(u\le v\) erscheint genau einmal in dieser Folge. Dass die Folge schnell wächst, sieht man ebenfalls am Grad: Aus \(\deg v_k=d\) und \(\deg u_k=d-1\) folgt, dass der neue höchste Term aus \(2v_k\) beim XOR nicht gelöscht wird, also \(\deg v_{k+1}=d+1\). Die zweite Koordinate gewinnt in jedem Schritt ein Binärbit hinzu.
Nehmen wir \(n=10\). Ausgehend von der Basislösung erhält man
$$(0,3)\to(3,6)\to(6,15).$$
Die dritte zweite Koordinate überschreitet bereits \(10\). Relevant sind also nur
$$(0,3)\quad\text{und}\quad(3,6).$$
Daher ist
$$X(10)=3\oplus 6=5.$$
Genau dieser kleine Test wird von den Implementierungen bestätigt. Das Beispiel zeigt das Grundprinzip vollständig: Bahn erzeugen, an der Schranke stoppen, zweite Koordinaten per XOR zusammenfassen.
Die C++-, Python- und Java-Implementierungen verwenden alle dieselbe kompakte Schleife. Sie speichern das aktuelle Lösungspaar, führen einen laufenden XOR-Akkumulator und wenden wiederholt die Abbildung
$$ (u,v)\mapsto \bigl(v,(2v)\oplus u\bigr) $$
an. Solange die aktuelle zweite Koordinate \(v\le n\) ist, wird sie in den Akkumulator eingexort. Sobald die nächste zweite Koordinate die Schranke übersteigt, endet die Schleife und der Akkumulator ist das Ergebnis.
Die Korrektheit folgt direkt aus dem mathematischen Teil: Die Rekursion bleibt immer in der Lösungsmenge, und es gibt keine weiteren Lösungen außerhalb dieser Bahn. Eine Implementierung enthält zusätzlich einen winzigen Bruteforce-Test für kleine Schranken, aber die eigentliche Euler-Berechnung benutzt ausschließlich die logarithmische Rekursion.
Jede Iteration hat konstanten Aufwand: ein Linksshift, ein XOR zur Erzeugung des nächsten Paares, ein XOR in die Antwort und ein Vergleich mit der Schranke. Weil die zweite Koordinate pro Schritt genau ein Binärbit gewinnt, ist die Anzahl der Iterationen bis \(n\) gleich \(O(\log n)\). Der Speicherverbrauch ist \(O(1)\).
Bir \(n\) sınırı için, \(u \le v \le n\) koşulunu sağlayan ve aşağıdaki taşımasız çarpım denklemini karşılayan tüm negatif olmayan tamsayı çiftlerini \((u,v)\) inceliyoruz:
$$u \otimes u \oplus \bigl((2u) \otimes v\bigr) \oplus (v \otimes v)=5.$$
Burada \(\oplus\) bit düzeyinde XOR, \(\otimes\) ise taşımasız çarpımdır. İstenen büyüklük
$$X(n)=\bigoplus_{\substack{(u,v)\text{ denklemi saglar}\\v\le n}} v$$
şeklindedir. Tüm çiftleri tek tek denemek \(O(n^2)\) maliyetli olur. Bu yüzden çözüm, önce tüm uygun çiftleri yapısal olarak üretip sonra ikinci bileşenleri XOR'lar.
Kritik fikir, ikili sayıların \(\mathbb{F}_2\) üzerindeki polinomlar gibi yorumlanmasıdır. Bu çeviride XOR toplama olur, taşımasız çarpım sıradan polinom çarpımına dönüşür ve denklem basit bir yineleme tarafından korunan kuadratik bir forma indirgenir.
İkili açılımları
$$u=\sum_{i\ge 0} u_i 2^i,\qquad v=\sum_{i\ge 0} v_i 2^i,\qquad u_i,v_i\in\{0,1\}$$
olarak yazalım ve bunlara
$$U(t)=\sum_{i\ge 0} u_i t^i,\qquad V(t)=\sum_{i\ge 0} v_i t^i$$
polinomlarını eşleyelim. Bu eşlemede
$$u\oplus v \leftrightarrow U(t)+V(t)$$
olur; çünkü XOR tam olarak \(\mathbb{F}_2[t]\) içinde toplamadır. Aynı şekilde
$$u\otimes v \leftrightarrow U(t)V(t)$$
eşitliği geçerlidir; çünkü taşımasız çarpım, bitleri polinom katsayıları gibi çarpar. Sayıyı \(2\) ile çarpmak bir bit sola kaydırma demektir, dolayısıyla
$$2u \leftrightarrow tU(t).$$
\(5=101_2\) olduğundan sağ taraf
$$5 \leftrightarrow 1+t^2$$
şeklini alır. Böylece başlangıç denklemi
$$U(t)^2+tU(t)V(t)+V(t)^2=1+t^2$$
olur. Şimdi
$$Q(U,V)=U^2+tUV+V^2$$
kuadratik formunu tanımlayalım. Problem, \(Q(U,V)=1+t^2\) sağlayan tüm polinom çiftlerini bulma problemine dönüşür.
Aşağıdaki dönüşümü ele alalım:
$$T(U,V)=\bigl(V,tV+U\bigr).$$
Karakteristik \(2\)'de bu dönüşüm \(Q\)'yu korur:
$$\begin{aligned} Q\bigl(V,tV+U\bigr) &=V^2+tV(tV+U)+(tV+U)^2\\ &=V^2+t^2V^2+tUV+t^2V^2+U^2\\ &=U^2+tUV+V^2\\ &=Q(U,V). \end{aligned}$$
Burada iki adet \(t^2V^2\) terimi birbirini yok eder. Bu yüzden bir çözümü \(T\) ile ileri taşırsak yine çözüm elde ederiz.
Başlangıç çözümü
$$\bigl(0,1+t\bigr)$$
olur; çünkü
$$Q(0,1+t)=(1+t)^2=1+t^2.$$
Bu çift tam sayılara geri çevrildiğinde
$$(0,3)$$
elde edilir.
Ters dönüşüm de çok basittir:
$$T^{-1}(U,V)=\bigl(V+tU,U\bigr).$$
Bu dönüşüm de \(Q\)'yu korur. Şimdi \((U,V)\) herhangi bir sıfır olmayan çözüm olsun ve \(\deg U \le \deg V=d\) olsun. Eğer \(d>1\) ise, \(V^2\)'nin derecesi \(2d\) olur; oysa sağ taraf \(1+t^2\) yalnızca derece \(2\)'dir.
Bu en yüksek dereceli terimi yalnızca \(tUV\) iptal edebilir. Dolayısıyla zorunlu olarak
$$\deg U=d-1$$
olmalıdır. Bu da \(V\) ile \(tU\)'nun önder terimlerinin aynı olduğu anlamına gelir; karakteristik \(2\)'de bunlar birbirini götürdüğü için
$$\deg(V+tU)<d$$
elde edilir. Yani \(T^{-1}\) uygulandığında yine bir çözüm kalırız ama maksimum derece küçülür. Bu inişi tekrar ederek sonunda \(\deg V=1\) olan çözüme ulaşırız.
Bu durumda
$$U=c,\qquad V=t+d,\qquad c,d\in\{0,1\}$$
yazabiliriz. Bunu \(Q(U,V)=1+t^2\) içine koyup katsayıları karşılaştırınca tek olasılık
$$U=0,\qquad V=1+t$$
çıkar. Demek ki her uygun çözüm, başlangıç çözümünün ardışık \(T\) uygulamalarından oluşan aynı orbit içindedir.
\((U_k,V_k)\) çiftine karşılık gelen tam sayı çifti \((u_k,v_k)\) olsun. \(t\) ile çarpmak, bitleri bir sola kaydırmak demektir. Bu nedenle polinom yinelemesi tam sayılarda
$$u_{k+1}=v_k,\qquad v_{k+1}=(2v_k)\oplus u_k$$
halini alır ve başlangıç değerleri
$$(u_0,v_0)=(0,3)$$
olur. İlk birkaç çift
$$(0,3),\ (3,6),\ (6,15),\ (15,24),\ (24,63),\dots$$
şeklindedir. \(u\le v\) koşulunu sağlayan her geçerli çift bu dizide tam bir kez görünür. Aynı derece argümanı büyümenin neden hızlı olduğunu da açıklar: \(\deg v_k=d\) ve \(\deg u_k=d-1\) iken, \(2v_k\)'daki yeni en yüksek bit XOR sırasında iptal olmaz ve \(\deg v_{k+1}=d+1\) olur. Yani ikinci bileşen her adımda bir ikili basamak kazanır.
\(n=10\) alalım. Başlangıçtan itibaren yineleme
$$(0,3)\to(3,6)\to(6,15)$$
şeklindedir. Üçüncü çiftin ikinci bileşeni artık \(10\)'u geçtiği için yalnızca
$$(0,3)\quad\text{ve}\quad(3,6)$$
çiftleri hesaba katılır. Bu yüzden
$$X(10)=3\oplus 6=5.$$
Bu küçük örnek, uygulamaların kullandığı kontrol değeriyle aynıdır ve yöntemi tamamen gösterir: çözüm orbitini üret, sınırda dur, ikinci bileşenleri XOR'la.
C++, Python ve Java implementasyonlarının hepsi aynı kısa döngüyü kullanır. Güncel çözüm çifti tutulur, biriken XOR değeri korunur ve sürekli olarak
$$ (u,v)\mapsto \bigl(v,(2v)\oplus u\bigr) $$
dönüşümü uygulanır. Güncel ikinci bileşen \(v\le n\) olduğu sürece sonuç içine XOR'lanır. Bir sonraki ikinci bileşen sınırı geçtiğinde döngü durur ve akümülatör cevap olur.
Bunun doğru olmasının nedeni matematiksel ispatın iki yönü de sağlamasıdır: yineleme hiçbir zaman çözüm kümesinin dışına çıkmaz ve o orbit dışında başka çözüm yoktur. Uygulamalardan biri küçük sınırlar için minicik bir kaba kuvvet doğrulaması da yapar, fakat gerçek Euler hesabında yalnızca bu logaritmik yineleme kullanılır.
Her iterasyon sabit iş yapar: bir sola kaydırma, yeni çifti üretmek için bir XOR, cevaba eklemek için bir XOR ve sınıra karşı bir karşılaştırma. İkinci bileşen her adımda bir bit büyüdüğü için \(n\)'e kadar gereken iterasyon sayısı \(O(\log n)\) olur. Bellek kullanımı \(O(1)\)'dir.
Para una cota \(n\), consideramos todos los pares de enteros no negativos \((u,v)\) con \(u \le v \le n\) que satisfacen la ecuacion sin acarreo
$$u \otimes u \oplus \bigl((2u) \otimes v\bigr) \oplus (v \otimes v)=5.$$
Aqui \(\oplus\) es XOR bit a bit y \(\otimes\) es multiplicacion sin acarreo. La cantidad pedida es
$$X(n)=\bigoplus_{\substack{(u,v)\text{ satisface la ecuacion}\\v\le n}} v.$$
Probar todos los pares hasta \(n\) costaria \(O(n^2)\), asi que la solucion real debe describir toda la familia de pares validos y despues acumular las segundas coordenadas.
La idea decisiva es reinterpretar los enteros binarios como polinomios sobre \(\mathbb{F}_2\). Con esa traduccion, XOR se convierte en suma, la multiplicacion sin acarreo pasa a ser multiplicacion ordinaria de polinomios y la ecuacion se transforma en una forma cuadratica preservada por una recurrencia muy simple.
Escribimos las expansiones binarias
$$u=\sum_{i\ge 0} u_i 2^i,\qquad v=\sum_{i\ge 0} v_i 2^i,\qquad u_i,v_i\in\{0,1\},$$
y asociamos los polinomios
$$U(t)=\sum_{i\ge 0} u_i t^i,\qquad V(t)=\sum_{i\ge 0} v_i t^i.$$
Con este diccionario,
$$u\oplus v \leftrightarrow U(t)+V(t),$$
porque XOR coincide con la suma en \(\mathbb{F}_2[t]\). Ademas,
$$u\otimes v \leftrightarrow U(t)V(t),$$
ya que en la multiplicacion sin acarreo los bits se comportan como coeficientes de un polinomio. Multiplicar un entero por \(2\) desplaza todos los bits una posicion a la izquierda, asi que corresponde a
$$2u \leftrightarrow tU(t).$$
Como \(5=101_2\), el lado derecho se vuelve
$$5 \leftrightarrow 1+t^2.$$
Por tanto, la ecuacion original equivale a
$$U(t)^2+tU(t)V(t)+V(t)^2=1+t^2.$$
Definimos entonces
$$Q(U,V)=U^2+tUV+V^2.$$
Ahora el problema consiste en hallar todos los pares de polinomios \((U,V)\) que satisfacen \(Q(U,V)=1+t^2\).
Consideremos la aplicacion
$$T(U,V)=\bigl(V,tV+U\bigr).$$
En caracteristica \(2\), esta transformacion preserva \(Q\):
$$\begin{aligned} Q\bigl(V,tV+U\bigr) &=V^2+tV(tV+U)+(tV+U)^2\\ &=V^2+t^2V^2+tUV+t^2V^2+U^2\\ &=U^2+tUV+V^2\\ &=Q(U,V). \end{aligned}$$
Los dos terminos \(t^2V^2\) se cancelan, y esa cancelacion es justo la razon por la que la recurrencia funciona. Asi, aplicar \(T\) a una solucion produce otra solucion.
La solucion base es
$$\bigl(0,1+t\bigr),$$
porque
$$Q(0,1+t)=(1+t)^2=1+t^2.$$
Al volver a enteros, esto corresponde al par
$$(0,3).$$
La transformacion inversa es
$$T^{-1}(U,V)=\bigl(V+tU,U\bigr),$$
y tambien preserva \(Q\). Sea ahora \((U,V)\) una solucion no nula con \(\deg U \le \deg V=d\). Si \(d>1\), entonces \(V^2\) tiene grado \(2d\), mientras que el lado derecho \(1+t^2\) solo tiene grado \(2\).
El unico termino capaz de cancelar ese grado \(2d\) es \(tUV\). Por eso necesariamente
$$\deg U=d-1.$$
Entonces los terminos lideres de \(V\) y \(tU\) coinciden, de modo que en caracteristica \(2\)
$$\deg(V+tU)<d.$$
Al aplicar \(T^{-1}\), seguimos dentro del conjunto de soluciones pero con grado maximo estrictamente menor. Repitiendo el descenso, terminamos en una solucion con \(\deg V=1\).
En ese caso puede escribirse
$$U=c,\qquad V=t+d,\qquad c,d\in\{0,1\},$$
y al sustituir en \(Q(U,V)=1+t^2\) la comparacion de coeficientes muestra que la unica posibilidad es
$$U=0,\qquad V=1+t.$$
Por lo tanto, toda solucion admisible pertenece a la misma orbita generada a partir de la solucion base.
Si \((u_k,v_k)\) es el par entero asociado a \((U_k,V_k)\), multiplicar por \(t\) equivale a desplazar un bit a la izquierda. Por eso la recurrencia polinomial se convierte en
$$u_{k+1}=v_k,\qquad v_{k+1}=(2v_k)\oplus u_k,$$
con condicion inicial
$$(u_0,v_0)=(0,3).$$
Los primeros pares son
$$(0,3),\ (3,6),\ (6,15),\ (15,24),\ (24,63),\dots$$
Cada par valido con \(u\le v\) aparece exactamente una vez en esta sucesion. El mismo argumento con grados explica el crecimiento rapido: si \(\deg v_k=d\) y \(\deg u_k=d-1\), entonces el nuevo bit principal de \(2v_k\) sobrevive al XOR y \(\deg v_{k+1}=d+1\). Es decir, la segunda coordenada gana un digito binario en cada paso.
Tomemos \(n=10\). Partiendo de la solucion base, la recurrencia produce
$$(0,3)\to(3,6)\to(6,15).$$
La tercera segunda coordenada ya supera \(10\), asi que las unicas soluciones relevantes son
$$(0,3)\quad\text{y}\quad(3,6).$$
En consecuencia,
$$X(10)=3\oplus 6=5.$$
Este caso pequeno coincide con la comprobacion incluida en las implementaciones y resume el metodo completo: generar la orbita, detenerse en la cota y aplicar XOR a las segundas coordenadas.
Las implementaciones en C++, Python y Java usan exactamente el mismo bucle compacto. Guardan el par actual de solucion, mantienen un acumulador XOR y aplican repetidamente
$$ (u,v)\mapsto \bigl(v,(2v)\oplus u\bigr). $$
Mientras la segunda coordenada actual cumpla \(v\le n\), se incorpora al acumulador. En cuanto la siguiente segunda coordenada supera la cota, el bucle termina y el acumulador es la respuesta.
Esto es correcto porque la prueba matematica establece ambos sentidos: la recurrencia nunca sale del conjunto de soluciones y no falta ninguna solucion fuera de esa misma orbita. Una de las implementaciones ademas hace una verificacion minima por fuerza bruta en cotas pequenas, pero el calculo real del problema usa solo la recurrencia logaritmica.
Cada iteracion realiza trabajo constante: un desplazamiento a la izquierda, un XOR para construir el siguiente par, un XOR para acumular la respuesta y una comparacion con la cota. Como la segunda coordenada gana un bit en cada paso, el numero de iteraciones hasta \(n\) es \(O(\log n)\). La memoria utilizada es \(O(1)\).
对于给定上界 \(n\)，我们考察所有满足 \(u \le v \le n\) 的非负整数对 \((u,v)\)，并要求它们满足下面这个无进位乘法方程：
$$u \otimes u \oplus \bigl((2u) \otimes v\bigr) \oplus (v \otimes v)=5.$$
这里 \(\oplus\) 表示按位 XOR，\(\otimes\) 表示无进位乘法，也就是把二进制位当作 \(\mathbb{F}_2\) 上的系数来相乘，不发生进位。题目要求计算
$$X(n)=\bigoplus_{\substack{(u,v)\text{ 满足方程}\\v\le n}} v.$$
如果直接枚举所有 \((u,v)\)，复杂度会达到 \(O(n^2)\)。真正可行的做法不是逐对检查，而是先把所有合法解的结构完整刻画出来，再把所有第二坐标做一次 XOR 汇总。
本题最关键的化简，是把二进制整数改写成 \(\mathbb{F}_2\) 上的多项式。这样一来，XOR 变成加法，无进位乘法变成普通多项式乘法，原方程就转化为一个由简单递推保持不变的二次型。
先把二进制展开写成
$$u=\sum_{i\ge 0} u_i 2^i,\qquad v=\sum_{i\ge 0} v_i 2^i,\qquad u_i,v_i\in\{0,1\}.$$
对应的多项式定义为
$$U(t)=\sum_{i\ge 0} u_i t^i,\qquad V(t)=\sum_{i\ge 0} v_i t^i.$$
在这个对应关系下，按位 XOR 恰好就是 \(\mathbb{F}_2[t]\) 中的加法，所以有
$$u\oplus v \leftrightarrow U(t)+V(t).$$
无进位乘法则恰好对应普通多项式乘法，因此
$$u\otimes v \leftrightarrow U(t)V(t).$$
另外，把整数乘以 \(2\) 就是把所有位左移一位，所以对应于多项式乘以 \(t\)：
$$2u \leftrightarrow tU(t).$$
由于 \(5=101_2\)，右侧常数项对应为
$$5 \leftrightarrow 1+t^2.$$
于是原方程完全等价于
$$U(t)^2+tU(t)V(t)+V(t)^2=1+t^2.$$
记二次型
$$Q(U,V)=U^2+tUV+V^2.$$
那么问题就变成：找出所有满足 \(Q(U,V)=1+t^2\) 的多项式对 \((U,V)\)，再把它们对应的整数第二坐标做 XOR。
考虑下面这个线性变换：
$$T(U,V)=\bigl(V,tV+U\bigr).$$
在特征 \(2\) 下，可以直接验证这个变换保持 \(Q\) 不变：
$$\begin{aligned} Q\bigl(V,tV+U\bigr) &=V^2+tV(tV+U)+(tV+U)^2\\ &=V^2+t^2V^2+tUV+t^2V^2+U^2\\ &=U^2+tUV+V^2\\ &=Q(U,V). \end{aligned}$$
这里两个 \(t^2V^2\) 项会互相抵消，这正是特征 \(2\) 的核心作用。因此，只要 \((U,V)\) 是一个解，应用一次 \(T\) 之后得到的仍然是解。
最基本的解是
$$\bigl(0,1+t\bigr),$$
因为
$$Q(0,1+t)=(1+t)^2=1+t^2.$$
把它翻译回整数，就是第一个合法解
$$(0,3).$$
逆变换同样很简单：
$$T^{-1}(U,V)=\bigl(V+tU,U\bigr).$$
它也保持 \(Q\) 不变。现在设 \((U,V)\) 是任意一个非零解，并且 \(\deg U \le \deg V=d\)。如果 \(d>1\)，那么 \(V^2\) 的次数是 \(2d\)，而右边 \(1+t^2\) 的次数只有 \(2\)。
因此，\(V^2\) 的最高次项必须被 \(tUV\) 的最高次项抵消掉，别的项做不到这一点，所以必然有
$$\deg U=d-1.$$
于是 \(V\) 与 \(tU\) 的首项相同，在特征 \(2\) 下相加后会消掉，因此
$$\deg(V+tU)<d.$$
这说明对任意非平凡解应用一次 \(T^{-1}\)，仍然是解，但最大次数严格下降。不断重复这个下降过程，最终一定会到达 \(\deg V=1\) 的情形。
当 \(\deg V=1\) 时，可以写成
$$U=c,\qquad V=t+d,\qquad c,d\in\{0,1\}.$$
把它代回 \(Q(U,V)=1+t^2\)，逐项比较系数，就会得到唯一可能是
$$U=0,\qquad V=1+t.$$
也就是说，所有合法解都落在同一个轨道里，而这个轨道正是从基解 \((0,1+t)\) 反复应用 \(T\) 得到的。
设 \((u_k,v_k)\) 是 \((U_k,V_k)\) 对应的整数对。多项式乘以 \(t\) 在整数里就是左移一位，因此上面的多项式递推会变成
$$u_{k+1}=v_k,\qquad v_{k+1}=(2v_k)\oplus u_k,$$
初始值为
$$(u_0,v_0)=(0,3).$$
前几项具体是
$$(0,3),\ (3,6),\ (6,15),\ (15,24),\ (24,63),\dots$$
所有满足 \(u\le v\) 的合法整数解都会在这条序列中恰好出现一次。为什么它增长得这么快？因为如果 \(\deg v_k=d\)，那么一定有 \(\deg u_k=d-1\)，于是 \(2v_k\) 的最高位比 \(u_k\) 高一位，不会在 XOR 时被抵消，所以 \(\deg v_{k+1}=d+1\)。换句话说，第二坐标每一步都会多出一个二进制位。
取 \(n=10\)。从基解开始，递推序列是
$$(0,3)\to(3,6)\to(6,15).$$
第三个第二坐标已经大于 \(10\)，因此真正需要计入的只有
$$(0,3)\quad\text{和}\quad(3,6).$$
于是
$$X(10)=3\oplus 6=5.$$
这正好对应实现里使用的小范围校验值，也很好地说明了整个算法流程：顺着轨道生成解，到达上界就停止，把所有第二坐标做 XOR。
C++、Python 和 Java 的实现都采用同一个非常短的循环。它们保存当前解对、维护一个运行中的 XOR 累积值，并不断应用
$$ (u,v)\mapsto \bigl(v,(2v)\oplus u\bigr). $$
只要当前第二坐标满足 \(v\le n\)，就把它 XOR 进答案。一旦下一项的第二坐标超过上界，循环立即结束，累积值就是最终结果。
之所以这样做是正确的，是因为上面的数学证明已经给出了两个关键结论：这个递推不会离开解集，而且解集里也没有任何遗漏的其他轨道。某个实现还额外做了一个很小范围的暴力验证，但真正用于 Euler 输入的核心计算完全依赖这个对数级递推。
每次迭代只做常数个操作：一次左移、一次 XOR 生成下一个解、一次 XOR 累积答案，以及一次与上界的比较。由于第二坐标每一步都会增加一个二进制位，所以到达 \(n\) 之前的迭代次数是 \(O(\log n)\)。额外空间开销为 \(O(1)\)。
Для заданной границы \(n\) рассматриваются все пары неотрицательных целых чисел \((u,v)\) с условием \(u \le v \le n\), которые удовлетворяют уравнению без переносов
$$u \otimes u \oplus \bigl((2u) \otimes v\bigr) \oplus (v \otimes v)=5.$$
Здесь \(\oplus\) означает побитовый XOR, а \(\otimes\) означает умножение без переносов. Требуется вычислить
$$X(n)=\bigoplus_{\substack{(u,v)\text{ удовлетворяет уравнению}\\v\le n}} v.$$
Прямой перебор всех пар до \(n\) стоил бы \(O(n^2)\). Поэтому нужно не проверять пары по одной, а сначала описать всю структуру множества решений, а затем сделать XOR всех вторых координат.
Главное упрощение состоит в том, чтобы заменить двоичные числа полиномами над \(\mathbb{F}_2\). В этой модели XOR становится сложением, умножение без переносов становится обычным умножением полиномов, а исходное уравнение превращается в квадратичную форму, сохраняемую простой рекуррентной схемой.
Запишем двоичные разложения
$$u=\sum_{i\ge 0} u_i 2^i,\qquad v=\sum_{i\ge 0} v_i 2^i,\qquad u_i,v_i\in\{0,1\},$$
и сопоставим им полиномы
$$U(t)=\sum_{i\ge 0} u_i t^i,\qquad V(t)=\sum_{i\ge 0} v_i t^i.$$
Тогда
$$u\oplus v \leftrightarrow U(t)+V(t),$$
потому что XOR в точности совпадает со сложением в \(\mathbb{F}_2[t]\). Аналогично
$$u\otimes v \leftrightarrow U(t)V(t),$$
так как умножение без переносов ведет себя как обычное умножение коэффициентов по модулю \(2\). Умножение целого числа на \(2\) означает сдвиг всех битов влево на один разряд, то есть
$$2u \leftrightarrow tU(t).$$
Поскольку \(5=101_2\), правая часть переходит в
$$5 \leftrightarrow 1+t^2.$$
Следовательно, исходное уравнение эквивалентно
$$U(t)^2+tU(t)V(t)+V(t)^2=1+t^2.$$
Обозначим
$$Q(U,V)=U^2+tUV+V^2.$$
Теперь задача сводится к поиску всех пар полиномов \((U,V)\), для которых \(Q(U,V)=1+t^2\).
Рассмотрим отображение
$$T(U,V)=\bigl(V,tV+U\bigr).$$
В характеристике \(2\) оно сохраняет \(Q\):
$$\begin{aligned} Q\bigl(V,tV+U\bigr) &=V^2+tV(tV+U)+(tV+U)^2\\ &=V^2+t^2V^2+tUV+t^2V^2+U^2\\ &=U^2+tUV+V^2\\ &=Q(U,V). \end{aligned}$$
Два слагаемых \(t^2V^2\) сокращаются, и именно это делает рекурсию возможной. Значит, каждое применение \(T\) переводит решение в новое решение.
Базовое решение имеет вид
$$\bigl(0,1+t\bigr),$$
потому что
$$Q(0,1+t)=(1+t)^2=1+t^2.$$
При переходе обратно к целым числам это дает первую допустимую пару
$$(0,3).$$
Обратное преобразование столь же просто:
$$T^{-1}(U,V)=\bigl(V+tU,U\bigr).$$
Оно тоже сохраняет \(Q\). Пусть теперь \((U,V)\) является каким-то ненулевым решением и \(\deg U \le \deg V=d\). Если \(d>1\), то \(V^2\) имеет степень \(2d\), тогда как правая часть \(1+t^2\) имеет степень только \(2\).
Следовательно, старший член \(V^2\) может сократиться только со старшим членом \(tUV\). Отсюда обязательно следует
$$\deg U=d-1.$$
Тогда старшие члены \(V\) и \(tU\) совпадают, поэтому в характеристике \(2\)
$$\deg(V+tU)<d.$$
После применения \(T^{-1}\) мы снова остаемся в множестве решений, но максимальная степень строго уменьшается. Повторяя этот спуск, мы неизбежно придем к случаю \(\deg V=1\).
Тогда можно записать
$$U=c,\qquad V=t+d,\qquad c,d\in\{0,1\},$$
и подставить это в \(Q(U,V)=1+t^2\). Сравнение коэффициентов показывает, что возможен только вариант
$$U=0,\qquad V=1+t.$$
Значит, любое допустимое решение лежит в одной и той же орбите, порожденной из базового решения последовательными применениями \(T\).
Пусть \((u_k,v_k)\) соответствует паре \((U_k,V_k)\). Умножение на \(t\) означает сдвиг влево на один бит, поэтому полиномиальная рекурсия превращается в
$$u_{k+1}=v_k,\qquad v_{k+1}=(2v_k)\oplus u_k,$$
с начальными значениями
$$(u_0,v_0)=(0,3).$$
Первые пары имеют вид
$$(0,3),\ (3,6),\ (6,15),\ (15,24),\ (24,63),\dots$$
Каждая допустимая пара с \(u\le v\) возникает в этой последовательности ровно один раз. Тот же аргумент со степенями объясняет быстрый рост: если \(\deg v_k=d\) и \(\deg u_k=d-1\), то новый старший бит в \(2v_k\) не уничтожается при XOR, и потому \(\deg v_{k+1}=d+1\). То есть вторая координата на каждом шаге получает еще один двоичный разряд.
Возьмем \(n=10\). Начиная с базовой пары, рекурсия дает
$$(0,3)\to(3,6)\to(6,15).$$
Третья вторая координата уже больше \(10\), поэтому учитывать нужно только пары
$$(0,3)\quad\text{и}\quad(3,6).$$
Следовательно,
$$X(10)=3\oplus 6=5.$$
Это совпадает с небольшой проверкой, встроенной в реализации, и полностью показывает идею метода: порождаем орбиту решений, останавливаемся на границе и берем XOR всех вторых координат.
Реализации на C++, Python и Java используют один и тот же короткий цикл. Они хранят текущую пару решения, поддерживают накопитель XOR и многократно применяют преобразование
$$ (u,v)\mapsto \bigl(v,(2v)\oplus u\bigr). $$
Пока текущая вторая координата удовлетворяет \(v\le n\), она добавляется в накопитель через XOR. Как только следующая вторая координата превосходит границу, цикл завершается, и накопитель возвращается как ответ.
Корректность следует напрямую из математического доказательства: рекурсия никогда не покидает множество решений, и никаких других решений вне этой орбиты не существует. Одна из реализаций дополнительно делает крошечную проверку полным перебором на малых пределах, но основное вычисление для входа Euler опирается только на логарифмическую рекурсию.
Каждая итерация выполняет постоянное число операций: один сдвиг влево, один XOR для построения следующего решения, один XOR для обновления ответа и одно сравнение с границей. Поскольку вторая координата на каждом шаге получает один новый бит, число итераций до \(n\) равно \(O(\log n)\). Память равна \(O(1)\).
من اجل حد علوي \(n\)، ننظر الى جميع الازواج الصحيحة غير السالبة \((u,v)\) التي تحقق \(u \le v \le n\) وتلبي معادلة الضرب من دون حمل التالية:
$$u \otimes u \oplus \bigl((2u) \otimes v\bigr) \oplus (v \otimes v)=5.$$
هنا ترمز \(\oplus\) الى XOR على مستوى البتات، وترمز \(\otimes\) الى الضرب من دون حمل. اذا رمزنا بمجموعة جميع الحلول المقبولة حتى الحد \(n\) بالرمز \(S_n\)، فان المطلوب هو حساب
$$X(n)=\bigoplus_{(u,v)\in S_n} v.$$
التعداد المباشر لكل الازواج حتى \(n\) يكلف \(O(n^2)\)، ولذلك فالفكرة الصحيحة ليست اختبار كل زوج على حدة، بل وصف جميع الحلول وصفا بنيويا ثم اخذ XOR لكل الاحداثيات الثانية.
التبسيط الحاسم في هذه المسألة هو تحويل الاعداد الثنائية الى كثيرات حدود فوق \(\mathbb{F}_2\). عندها يصبح XOR عملية جمع، ويصبح الضرب من دون حمل ضربا عاديا لكثيرات الحدود، وتتحول المعادلة الى صيغة تربيعية يحافظ عليها تكرار بسيط جدا.
نكتب التوسع الثنائي على الصورة
$$u=\sum_{i\ge 0} u_i 2^i,\qquad v=\sum_{i\ge 0} v_i 2^i,\qquad u_i,v_i\in\{0,1\},$$
ونربط بهما كثيري الحدود
$$U(t)=\sum_{i\ge 0} u_i t^i,\qquad V(t)=\sum_{i\ge 0} v_i t^i.$$
ضمن هذا الترميز يصبح
$$u\oplus v \leftrightarrow U(t)+V(t),$$
لان XOR هو بالضبط الجمع داخل \(\mathbb{F}_2[t]\). كذلك نحصل على
$$u\otimes v \leftrightarrow U(t)V(t),$$
لان الضرب من دون حمل يتعامل مع البتات كما لو كانت معاملات كثير حدود. وضرب عدد صحيح في \(2\) يعني ازاحة كل البتات خانة واحدة الى اليسار، ولذلك يقابل
$$2u \leftrightarrow tU(t).$$
وبما ان \(5=101_2\)، فان الطرف الايمن يصبح
$$5 \leftrightarrow 1+t^2.$$
ومن ثم تكون المعادلة الاصلية مكافئة تماما للمعادلة
$$U(t)^2+tU(t)V(t)+V(t)^2=1+t^2.$$
لذلك نعرف الصيغة التربيعية
$$Q(U,V)=U^2+tUV+V^2.$$
والهدف الجديد هو ايجاد جميع ازواج كثيرات الحدود \((U,V)\) التي تحقق \(Q(U,V)=1+t^2\).
لننظر الى التحويل
$$T(U,V)=\bigl(V,tV+U\bigr).$$
في characteristic \(2\) يحافظ هذا التحويل على \(Q\):
$$\begin{aligned} Q\bigl(V,tV+U\bigr) &=V^2+tV(tV+U)+(tV+U)^2\\ &=V^2+t^2V^2+tUV+t^2V^2+U^2\\ &=U^2+tUV+V^2\\ &=Q(U,V). \end{aligned}$$
يتلاشى الحدّان \(t^2V^2\) لانهما متساويان في characteristic \(2\)، وهذا هو لب الفكرة. لذلك، اذا كان \((U,V)\) حلا، فان تطبيق \(T\) يعطي حلا جديدا مباشرة.
الحل الابتدائي هو
$$\bigl(0,1+t\bigr),$$
لان
$$Q(0,1+t)=(1+t)^2=1+t^2.$$
وعند العودة الى الاعداد الصحيحة نحصل على الزوج الاول
$$(0,3).$$
التحويل العكسي بسيط ايضا:
$$T^{-1}(U,V)=\bigl(V+tU,U\bigr).$$
وهو بدوره يحافظ على \(Q\). لنفترض الان ان \((U,V)\) حل غير صفري ويحقق \(\deg U \le \deg V=d\). اذا كان \(d>1\)، فان درجة \(V^2\) تساوي \(2d\)، بينما درجة الطرف الايمن \(1+t^2\) هي \(2\) فقط.
هذا يعني ان الحد الاعلى في \(V^2\) لا بد ان يلغيه الحد الاعلى في \(tUV\)، ولا يوجد حد اخر قادر على ذلك. ومن هنا نحصل بالضرورة على
$$\deg U=d-1.$$
وعندئذ يكون الحد الرائد في \(V\) مساويا للحد الرائد في \(tU\)، ولذلك نحصل في characteristic \(2\) على
$$\deg(V+tU)<d.$$
اي ان تطبيق \(T^{-1}\) يبقينا داخل مجموعة الحلول، لكنه ينقص الدرجة العظمى نقصانا صارما. وبتكرار هذا الهبوط نصل في النهاية الى حالة \(\deg V=1\).
عندها يمكن كتابة
$$U=c,\qquad V=t+d,\qquad c,d\in\{0,1\},$$
وبالتعويض في \(Q(U,V)=1+t^2\) ومقارنة المعاملات يتبين ان الاحتمال الوحيد هو
$$U=0,\qquad V=1+t.$$
اذن كل حل مقبول يقع في المدار نفسه الذي يولده تكرار \(T\) انطلاقا من الحل الاساسي.
اذا كانت \((u_k,v_k)\) هي الصورة الصحيحة للزوج \((U_k,V_k)\)، فان الضرب في \(t\) يعني فقط ازاحة يسارية بمقدار بت واحد. لذلك يتحول التكرار كثيري الحدود الى
$$u_{k+1}=v_k,\qquad v_{k+1}=(2v_k)\oplus u_k,$$
مع البداية
$$(u_0,v_0)=(0,3).$$
واوائل الازواج هي
$$(0,3),\ (3,6),\ (6,15),\ (15,24),\ (24,63),\dots$$
كل زوج صحيح يحقق \(u\le v\) يظهر مرة واحدة بالضبط داخل هذه المتتالية. كما يوضح برهان الدرجات سبب النمو السريع: اذا كانت \(\deg v_k=d\) فسنحصل دائما على \(\deg u_k=d-1\)، ومن ثم يبقى البت الرائد الجديد في \(2v_k\) بعد عملية XOR، وبالتالي \(\deg v_{k+1}=d+1\). وهذا يعني ان الاحداثي الثاني يكتسب خانة ثنائية جديدة في كل خطوة.
لنأخذ \(n=10\). انطلاقا من الحل الاساسي نحصل على
$$(0,3)\to(3,6)\to(6,15).$$
الاحداثي الثاني الثالث صار اكبر من \(10\)، ولذلك لا تدخل في الحساب الا الازواج
$$(0,3),\ (3,6).$$
وعليه يكون
$$X(10)=3\oplus 6=5.$$
وهذه القيمة تطابق الفحص الصغير الموجود في التنفيذ، كما انها تلخص الخطة كلها: نولد مدار الحلول، نتوقف عند الحد، ثم نأخذ XOR لكل الاحداثيات الثانية.
التنفيذات في C++ وPython وJava تستخدم الحلقة المدمجة نفسها. فهي تحتفظ بزوج الحل الحالي، وتبني قيمة XOR تراكمية، وتكرر التحويل
$$ (u,v)\mapsto \bigl(v,(2v)\oplus u\bigr). $$
طالما ان الاحداثي الثاني الحالي يحقق \(v\le n\)، تتم اضافته الى الجواب بواسطة XOR. وعندما يتجاوز الاحداثي الثاني التالي الحد المطلوب تتوقف الحلقة ويعاد التراكم باعتباره النتيجة النهائية.
صحة هذا التنفيذ مضمونة من البرهان الرياضي السابق: التكرار لا يخرج ابدا من مجموعة الحلول، ولا توجد حلول اخرى خارج هذا المدار. احد التنفيذات يحتوي ايضا على تحقق صغير جدا بالقوة الغاشمة لحدود صغيرة، لكن الحساب الحقيقي للادخال الكبير يعتمد كليا على هذا التكرار ذي الكلفة اللوغاريتمية.
كل دورة تنفذ عددا ثابتا من العمليات: ازاحة يسارية واحدة، وXOR واحد لبناء الحل التالي، وXOR واحد لتحديث الجواب، ومقارنة واحدة مع الحد. وبما ان الاحداثي الثاني يكسب بتا جديدا في كل خطوة، فان عدد الدورات حتى \(n\) هو \(O(\log n)\). اما الذاكرة المستعملة فهي \(O(1)\).