Let \(f(n)\) be the number of ways to write \(n\) as a sum of powers of 2 when each power may be used at most twice. These are the hyperbinary representations of \(n\). The Project Euler instance asks for the smallest positive integer \(n\) such that
$$\frac{f(n)}{f(n-1)}=\frac{123456789}{987654321},$$
and it wants the answer in shortened binary form: if the ordinary binary expansion of \(n\) is split into maximal runs of equal bits, we output the run lengths from left to right. For example, \(241=11110001_2\) becomes \([4,3,1]\).
The crucial point is that the implementations never search for \(n\) and never build a huge table of values for the real input. They turn the target fraction directly into those binary run lengths.
The solution rests on two facts: the counting function \(f(n)\) has a very rigid parity recurrence, and the quotient \(r(n)=f(n)/f(n-1)\) therefore moves through the positive rationals by simple deterministic rules.
Look at the coefficient of \(2^0=1\) in a representation of \(n\).
If \(n=2m+1\) is odd, that coefficient must be exactly 1. After removing that 1 and dividing every remaining term by 2, we obtain a bijection with representations of \(m\). Hence
$$f(2m+1)=f(m).$$
If \(n=2m\) is even, the coefficient of 1 can only be 0 or 2. In the first case, dividing by 2 gives a representation of \(m\). In the second case, removing the two 1s and dividing by 2 gives a representation of \(m-1\). Therefore
$$f(2m)=f(m)+f(m-1)\qquad (m\ge 1).$$
Together with \(f(0)=1\), this is exactly the recurrence used in the implementations:
$$f(0)=1,\qquad f(2m+1)=f(m),\qquad f(2m)=f(m)+f(m-1).$$
Define
$$r(n)=\frac{f(n)}{f(n-1)}\qquad (n\ge 1).$$
Apply the recurrence to the pair \((f(n),f(n-1))\). For an even index \(n=2m\),
$$r(2m)=\frac{f(m)+f(m-1)}{f(m-1)}=r(m)+1.$$
For an odd index \(n=2m+1\),
$$r(2m+1)=\frac{f(m)}{f(m)+f(m-1)}=\frac{r(m)}{r(m)+1}.$$
These formulas already tell us something important about the binary expansion of the unknown \(n\). If \(n\) is even, then \(r(n)>1\). If \(n\) is odd and \(n>1\), then \(0<r(n)<1\). So by comparing the numerator and denominator of the target fraction, we can tell whether the last binary digit is 0 or 1.
Binary expansion and parity recursion fit together perfectly. Starting from \(r(1)=1\), appending a binary digit to the right updates the ratio by one of two maps:
$$0:\ x\mapsto x+1,\qquad 1:\ x\mapsto \frac{x}{x+1}.$$
So if the binary expansion of \(n\) is read from left to right, every 0 means “add 1”, and every 1 after the leading bit means “replace \(x\) by \(x/(x+1)\)”. Consecutive equal bits therefore correspond to repeating the same transformation many times in a row.
This is exactly why the problem asks for the shortened binary expansion. The natural object recovered by the inverse process is not the full integer \(n\), but the lengths of alternating runs of 1s and 0s.
Now run the recurrence backward on a reduced positive fraction \(p/q\).
If \(p>q\), then the last step must have come from an even index, because only the map \(x\mapsto x+1\) produces a value greater than 1. Undoing one such step sends
$$\frac{p}{q}\longmapsto \frac{p-q}{q}.$$
If the inequality \(p>q\) continues to hold, we can strip several trailing 0s at once. Write
$$p=a q+p',\qquad a=\left\lfloor\frac{p-1}{q}\right\rfloor,\qquad 1\le p'\le q.$$
Then \(a\) is the length of the final run of 0s, and the smaller subproblem is \(p'/q\).
If \(p\le q\), then the last step must have come from an odd index, because the map \(x\mapsto x/(x+1)\) produces a value in \((0,1]\). Undoing one such step sends
$$\frac{p}{q}\longmapsto \frac{p}{q-p}.$$
Again we group repeated identical steps. Write
$$q=b p+q',\qquad b=\left\lfloor\frac{q}{p}\right\rfloor,\qquad 0\le q'<p.$$
Then \(b\) is the length of the final run of 1s, and the smaller subproblem is \(p/q'\). If \(q'=0\), we have reached the initial block of 1s at the far left of the binary expansion. In that sense, the algorithm is a Euclidean algorithm whose quotients are exactly the answer we want to print.
Take the checkpoint fraction \(13/17\).
Since \(13\le 17\), the binary expansion ends with a run of 1s. Divide \(17\) by \(13\):
$$17=1\cdot 13+4.$$
So the last run length is 1, and we continue with \(13/4\).
Now \(13>4\), so the previous run was a run of 0s. Divide \(13\) by \(4\) in the grouped form used above:
$$13=3\cdot 4+1.$$
This contributes a run length 3 and reduces the problem to \(1/4\).
Finally,
$$4=4\cdot 1+0,$$
so the leading run of 1s has length 4. Reading the recorded lengths from left to right gives
$$[4,3,1].$$
Indeed, \([4,3,1]\) is the shortened binary expansion of \(241=11110001_2\), and the checkpoint computation confirms
$$\frac{f(241)}{f(240)}=\frac{13}{17}.$$
The implementations first reduce the input fraction by its greatest common divisor. This is mathematically harmless, because the ratio \(f(n)/f(n-1)\) depends only on the reduced rational number.
After that, the main routine repeatedly compares the numerator and denominator. If the numerator is larger, it extracts one grouped quotient for a 0-run and replaces the numerator by the adjusted remainder in the interval \(1,\dots,q\). If the denominator is larger or equal, it extracts one grouped quotient for a 1-run and replaces the denominator by the ordinary remainder modulo the numerator. Those quotients are exactly the run lengths of the shortened binary expansion.
The C++ version emits the run lengths by recursive unwinding, so they appear directly in left-to-right order. The Python and Java versions collect them while descending through the Euclidean reductions and reverse the list once at the end. The C++ implementation also includes small checkpoints: it verifies the recurrence on tiny values, checks the sample fraction \(13/17\), and confirms that the minimal corresponding integer has shortened binary expansion \([4,3,1]\).
For the real input, none of the implementations constructs the enormous integer \(n\) itself. They stop as soon as the fraction has been fully decomposed into its alternating run lengths, then print those lengths as a comma-separated list.
The reduction steps are Euclidean steps, only grouped by runs instead of performed one subtraction at a time. Therefore the number of iterations is \(O(\log \max(p,q))\).
The output list has the same asymptotic size, so the memory usage is \(O(\log \max(p,q))\) as well. For the concrete Project Euler input, 64-bit integer arithmetic is sufficient throughout, and the method is extremely fast because it avoids both brute-force search over \(n\) and explicit computation of large values of \(f(n)\).
Sei \(f(n)\) die Anzahl der Darstellungen von \(n\) als Summe von Zweierpotenzen, wobei jede Potenz höchstens zweimal verwendet werden darf. Das sind die hyperbinären Darstellungen von \(n\). In der Aufgabeninstanz von Project Euler soll das kleinste positive \(n\) gefunden werden, für das
$$\frac{f(n)}{f(n-1)}=\frac{123456789}{987654321}$$
gilt. Ausgegeben wird jedoch nicht \(n\) selbst, sondern seine verkürzte Binärdarstellung: Man zerlegt die gewöhnliche Binärschreibweise in maximale Blöcke gleicher Bits und notiert die Blocklängen von links nach rechts. Aus \(241=11110001_2\) wird also \([4,3,1]\).
Die Implementierungen suchen nicht über Kandidaten für \(n\). Stattdessen wandeln sie den Zielbruch direkt in diese Folge von Blocklängen um.
Die gesamte Lösung basiert auf zwei Beobachtungen: \(f(n)\) erfüllt eine sehr starre Rekursion nach der Parität von \(n\), und deshalb bewegt sich der Quotient \(r(n)=f(n)/f(n-1)\) nach einfachen, eindeutig invertierbaren Regeln durch die positiven rationalen Zahlen.
Betrachte in einer Darstellung von \(n\) den Koeffizienten der Potenz \(2^0=1\).
Ist \(n=2m+1\) ungerade, dann muss dieser Koeffizient genau 1 sein. Entfernt man diese 1 und halbiert anschließend alle verbleibenden Zweierpotenzen, erhält man bijektiv eine Darstellung von \(m\). Also
$$f(2m+1)=f(m).$$
Ist \(n=2m\) gerade, dann kann der Koeffizient von 1 nur 0 oder 2 sein. Im ersten Fall liefert Halbieren eine Darstellung von \(m\). Im zweiten Fall entfernt man die zwei Einsen und erhält nach dem Halbieren eine Darstellung von \(m-1\). Daher
$$f(2m)=f(m)+f(m-1)\qquad (m\ge 1).$$
Zusammen mit \(f(0)=1\) ist dies genau die Rekursion aus dem Code:
$$f(0)=1,\qquad f(2m+1)=f(m),\qquad f(2m)=f(m)+f(m-1).$$
Definiere
$$r(n)=\frac{f(n)}{f(n-1)}\qquad (n\ge 1).$$
Setzt man die Rekursion in das Paar \((f(n),f(n-1))\) ein, erhält man für einen geraden Index \(n=2m\)
$$r(2m)=\frac{f(m)+f(m-1)}{f(m-1)}=r(m)+1,$$
und für einen ungeraden Index \(n=2m+1\)
$$r(2m+1)=\frac{f(m)}{f(m)+f(m-1)}=\frac{r(m)}{r(m)+1}.$$
Damit verrät schon der Vergleich von Zähler und Nenner, wie die Binärdarstellung von \(n\) endet. Gerade Indizes liefern Quotienten \(\gt 1\), ungerade Indizes \(\lt 1\) mit Ausnahme des Startwerts \(r(1)=1\).
Binärdarstellung und Paritätsrekursion passen exakt zusammen. Beginnt man bei \(r(1)=1\) und hängt rechts ein Binärbit an, dann entsteht auf dem Quotienten eine der beiden Abbildungen
$$0:\ x\mapsto x+1,\qquad 1:\ x\mapsto \frac{x}{x+1}.$$
Liests man also die Bits von links nach rechts, bedeutet jedes 0-Bit „addiere 1“ und jedes 1-Bit nach dem führenden Bit „ersetze \(x\) durch \(x/(x+1)\)“. Mehrere gleiche Bits hintereinander erzeugen daher mehrfach dieselbe Abbildung.
Genau deshalb ist die verkürzte Binärdarstellung die natürliche Ausgabeform. Der inverse Prozess rekonstruiert nicht zuerst die riesige Zahl \(n\), sondern unmittelbar die Längen der alternierenden Eins- und Nullblöcke.
Nun invertieren wir die Rekursion auf einem gekürzten Bruch \(p/q\).
Falls \(p>q\), muss der letzte Schritt von einem geraden Index stammen, denn nur \(x\mapsto x+1\) erzeugt Werte größer als 1. Ein einzelner Rückwärtsschritt ist dann
$$\frac{p}{q}\longmapsto \frac{p-q}{q}.$$
Solange \(p>q\) bleibt, kann man mehrere Endnullen auf einmal entfernen. Schreibe
$$p=a q+p',\qquad a=\left\lfloor\frac{p-1}{q}\right\rfloor,\qquad 1\le p'\le q.$$
Dann ist \(a\) die Länge des letzten Nullblocks, und das kleinere Teilproblem lautet \(p'/q\).
Falls \(p\le q\), muss der letzte Schritt von einem ungeraden Index stammen, denn \(x\mapsto x/(x+1)\) liefert Werte in \((0,1]\). Ein Rückwärtsschritt ist
$$\frac{p}{q}\longmapsto \frac{p}{q-p}.$$
Auch hier werden gleiche Schritte gebündelt. Schreibe
$$q=b p+q',\qquad b=\left\lfloor\frac{q}{p}\right\rfloor,\qquad 0\le q'<p.$$
Dann ist \(b\) die Länge des letzten Einsblocks, und das kleinere Teilproblem lautet \(p/q'\). Tritt \(q'=0\) auf, ist der linke Anfangsblock aus Einsen erreicht. In diesem Sinn ist der Algorithmus nichts anderes als der euklidische Algorithmus, nur dass seine Quotienten genau die gesuchten Blocklängen sind.
Nimm den Kontrollbruch \(13/17\).
Da \(13\le 17\), endet die Binärdarstellung mit einem Einsblock. Teile \(17\) durch \(13\):
$$17=1\cdot 13+4.$$
Also hat der letzte Block Länge 1, und wir gehen weiter zu \(13/4\).
Nun ist \(13>4\), also folgt zuvor ein Nullblock. In der gebündelten Form gilt
$$13=3\cdot 4+1.$$
Das liefert die Blocklänge 3 und reduziert auf \(1/4\).
Schließlich gilt
$$4=4\cdot 1+0,$$
also hat der führende Einsblock Länge 4. Von links nach rechts gelesen ergibt sich
$$[4,3,1].$$
Tatsächlich ist \([4,3,1]\) die verkürzte Binärdarstellung von \(241=11110001_2\), und die Kontrollrechnung bestätigt
$$\frac{f(241)}{f(240)}=\frac{13}{17}.$$
Zuerst kürzen die Implementierungen den Eingabebruch mit dem größten gemeinsamen Teiler. Das ist mathematisch korrekt, weil nur die reduzierte rationale Zahl für den Quotienten \(f(n)/f(n-1)\) relevant ist.
Danach vergleicht die Hauptroutine wiederholt Zähler und Nenner. Ist der Zähler größer, wird ein gebündelter Quotient für einen Nullblock erzeugt, und der Zähler wird durch den angepassten Rest im Bereich \(1,\dots,q\) ersetzt. Ist der Nenner größer oder gleich, entsteht ein gebündelter Quotient für einen Einsblock, und der Nenner wird durch den gewöhnlichen Rest modulo Zähler ersetzt. Diese Quotienten sind exakt die Blocklängen der Antwort.
Die C++-Version gibt die Längen beim Zurückkehren aus der Rekursion direkt in der richtigen Reihenfolge aus. Die Python- und Java-Versionen sammeln die Werte zunächst in umgekehrter Reihenfolge und drehen die Liste am Ende einmal um. Zusätzlich enthält die C++-Implementierung kleine Kontrolltests: die Rekursion für kleine \(f(n)\)-Werte, den Beispielbruch \(13/17\) und die verkürzte Binärdarstellung \([4,3,1]\) für die zugehörige kleinste Zahl.
Für die eigentliche Aufgabeninstanz konstruiert keine Implementierung die oft riesige Zahl \(n\). Sobald der Bruch vollständig in seine alternierenden Blocklängen zerlegt ist, werden diese Längen als kommaseparierte Folge ausgegeben.
Die Reduktionsschritte sind euklidische Schritte, nur nach Bitblöcken gruppiert statt als einzelne Subtraktionen ausgeführt. Deshalb beträgt die Zahl der Iterationen \(O(\log \max(p,q))\).
Die Ausgabeliste hat dieselbe asymptotische Größe, also ist auch der Speicherbedarf \(O(\log \max(p,q))\). Für die konkrete Project-Euler-Eingabe reichen 64-Bit-Ganzzahlen aus, und die Methode ist sehr schnell, weil weder eine Brute-Force-Suche über \(n\) noch die explizite Berechnung großer \(f(n)\)-Werte nötig ist.
\(f(n)\), \(n\) sayısını 2'nin kuvvetlerinin toplamı olarak yazmanın, her kuvvet en fazla iki kez kullanılacak şekilde, kaç farklı yolu olduğunu göstersin. Bunlar \(n\)'nin hiperbiner gösterimleridir. Project Euler sorusunda istenen şey,
$$\frac{f(n)}{f(n-1)}=\frac{123456789}{987654321}$$
eşitliğini sağlayan en küçük pozitif \(n\)'dir; fakat çıktı doğrudan \(n\) değildir. İstenen biçim, \(n\)'nin ikili yazımındaki ardışık eş bit bloklarının uzunluklarıdır. Örneğin \(241=11110001_2\) için kısaltılmış ikili gösterim \([4,3,1]\) olur.
Çözümün temel fikri, gerçek girdi için ne \(n\)'yi aramak ne de büyük bir \(f(n)\) tablosu üretmektir. Bunun yerine hedef kesir doğrudan bu blok uzunluklarına dönüştürülür.
Bütün çözüm iki olguya dayanır: \(f(n)\) pariteye göre çok düzenli bir yineleme sağlar ve bu yüzden \(r(n)=f(n)/f(n-1)\) oranı pozitif rasyonel sayılar arasında son derece basit kurallarla ilerler.
Bir gösterimde \(2^0=1\) katsayısına bakalım.
Eğer \(n=2m+1\) tek ise, bu katsayı zorunlu olarak 1'dir. Bu 1 çıkarılıp kalan bütün kuvvetler 2'ye bölündüğünde, \(m\)'nin gösterimleriyle bire bir eşleşme elde edilir. Dolayısıyla
$$f(2m+1)=f(m).$$
Eğer \(n=2m\) çift ise, 1'in katsayısı yalnızca 0 veya 2 olabilir. Katsayı 0 ise doğrudan ikiye bölünerek \(m\)'nin bir gösterimi elde edilir. Katsayı 2 ise iki tane 1 çıkarılır, sonra ikiye bölünür ve \(m-1\)'in bir gösterimi oluşur. Bu yüzden
$$f(2m)=f(m)+f(m-1)\qquad (m\ge 1).$$
\(f(0)=1\) ile birlikte kodun kullandığı yineleme tam olarak şudur:
$$f(0)=1,\qquad f(2m+1)=f(m),\qquad f(2m)=f(m)+f(m-1).$$
Şimdi
$$r(n)=\frac{f(n)}{f(n-1)}\qquad (n\ge 1)$$
tanımını yapalım. Yineleme \((f(n),f(n-1))\) çiftine uygulanırsa, \(n=2m\) için
$$r(2m)=\frac{f(m)+f(m-1)}{f(m-1)}=r(m)+1,$$
\(n=2m+1\) için ise
$$r(2m+1)=\frac{f(m)}{f(m)+f(m-1)}=\frac{r(m)}{r(m)+1}$$
elde edilir. Böylece hedef kesrin payı ile paydasını karşılaştırmak bile son ikili bit hakkında bilgi verir. Çift indekslerde oran \(>1\) olur; tek indekslerde ise başlangıç durumu \(r(1)=1\) dışında oran \((0,1)\) aralığındadır.
İkili yazım ile bu parite yinelemesi kusursuz biçimde örtüşür. Başlangıçta \(r(1)=1\) varken, ikili yazımın sağına bir bit eklemek oran üzerinde şu iki dönüşümden birini uygular:
$$0:\ x\mapsto x+1,\qquad 1:\ x\mapsto \frac{x}{x+1}.$$
Dolayısıyla soldan sağa okunan her 0 biti “1 ekle”, baştaki zorunlu 1'den sonraki her 1 biti ise “\(x\)'i \(x/(x+1)\) ile değiştir” anlamına gelir. Aynı bitlerin arka arkaya gelmesi, aynı dönüşümün tekrarlanması demektir.
Bu nedenle sorunun istediği kısaltılmış ikili gösterim tam da doğal çıktıdır. Ters süreç önce devasa \(n\)'yi kurmak yerine, 1 ve 0 bloklarının uzunluklarını doğrudan geri kazanır.
Şimdi indirgenmiş bir \(p/q\) kesrinden geriye gidelim.
Eğer \(p>q\) ise, son adım mutlaka çift bir indeksten gelmiştir; çünkü yalnızca \(x\mapsto x+1\) dönüşümü 1'den büyük değer üretir. Tek bir ters adım
$$\frac{p}{q}\longmapsto \frac{p-q}{q}$$
şeklindedir. Eğer hâlâ \(p>q\) kalıyorsa, sondaki birden fazla 0 aynı anda sökülebilir. Bunun için
$$p=a q+p',\qquad a=\left\lfloor\frac{p-1}{q}\right\rfloor,\qquad 1\le p'\le q$$
yazılır. Burada \(a\), sondaki 0 bloğunun uzunluğudur; yeni alt problem \(p'/q\) olur.
Eğer \(p\le q\) ise, son adım mutlaka tek bir indeksten gelmiştir; çünkü \(x\mapsto x/(x+1)\) dönüşümü \((0,1]\) aralığında kalır. Tek bir ters adım
$$\frac{p}{q}\longmapsto \frac{p}{q-p}$$
biçimindedir. Yine tekrarlanan aynı tip adımlar birlikte toplanır. Bunun için
$$q=b p+q',\qquad b=\left\lfloor\frac{q}{p}\right\rfloor,\qquad 0\le q'<p$$
yazılır. Bu kez \(b\), sondaki 1 bloğunun uzunluğudur; yeni alt problem \(p/q'\) olur. Eğer \(q'=0\) ise ikili yazımın en soldaki başlangıç 1 bloğuna ulaşılmıştır. Böylece yöntem, bölüm katsayıları doğrudan cevap olan bir Öklid algoritmasına dönüşür.
Kodun doğrulama örneğindeki \(13/17\) kesrini alalım.
\(13\le 17\) olduğundan ikili yazım 1'lerden oluşan bir blokla biter. \(17\)'yi \(13\)'e bölelim:
$$17=1\cdot 13+4.$$
Demek ki son blok uzunluğu 1'dir ve problem \(13/4\)'e iner.
Şimdi \(13>4\) olduğundan önce bir 0 bloğu vardır. Gruplanmış yazım
$$13=3\cdot 4+1$$
olur. Bu, uzunluğu 3 olan bir blok verir ve problemi \(1/4\)'e indirir.
Son olarak
$$4=4\cdot 1+0$$
elde edilir; yani baştaki 1 bloğunun uzunluğu 4'tür. Uzunluklar soldan sağa
$$[4,3,1]$$
şeklindedir. Gerçekten de bu dizi \(241=11110001_2\)'nin kısaltılmış ikili gösterimidir ve doğrulama hesabı
$$\frac{f(241)}{f(240)}=\frac{13}{17}$$
eşitliğini sağlar.
Uygulamalar önce giriş kesrini en büyük ortak bölen ile sadeleştirir. Bu adım matematiksel olarak güvenlidir; çünkü \(f(n)/f(n-1)\) yalnızca kesrin indirgenmiş haline bağlıdır.
Daha sonra ana rutin pay ile paydayı tekrar tekrar karşılaştırır. Pay daha büyükse, bir 0-bloğu için gruplanmış bölüm katsayısı çıkarılır ve pay, \(1,\dots,q\) aralığındaki ayarlı kalan ile değiştirilir. Payda daha büyük ya da eşitse, bu kez bir 1-bloğu için gruplanmış bölüm katsayısı çıkarılır ve payda, paya göre alınan normal kalanla değiştirilir. Toplanan bu katsayılar, cevapta yazdırılan blok uzunluklarıdır.
C++ uygulaması bu uzunlukları rekürsiyondan geri dönerken doğru sırayla üretir. Python ve Java uygulamaları ise değerleri önce ters sırada toplayıp sonunda listeyi çevirir. C++ tarafında ayrıca küçük doğrulamalar bulunur: ufak \(f(n)\) değerleri, örnek kesir \(13/17\) ve buna karşılık gelen \([4,3,1]\) kısaltılmış ikili gösterimi kontrol edilir.
Gerçek problem girdisi için hiçbir uygulama devasa \(n\)'yi inşa etmez. Kesir tüm blok uzunluklarına ayrıştığında işlem biter ve sonuç virgülle ayrılmış biçimde yazdırılır.
Azaltma adımları, tek tek çıkarma yapmak yerine bloklar halinde gruplanmış Öklid adımlarıdır. Bu nedenle iterasyon sayısı \(O(\log \max(p,q))\) olur.
Üretilen çıktı listesi de aynı mertebededir; dolayısıyla bellek kullanımı \(O(\log \max(p,q))\) seviyesindedir. Somut Project Euler girdisi için 64-bit tamsayılar yeterlidir ve yöntem çok hızlıdır; çünkü ne \(n\) üzerinde kaba kuvvet arama yapar ne de büyük \(f(n)\) değerlerini açıkça hesaplar.
Sea \(f(n)\) el número de formas de escribir \(n\) como suma de potencias de 2, usando cada potencia como mucho dos veces. Estas son las representaciones hiperbinaras de \(n\). En la instancia de Project Euler se pide el menor entero positivo \(n\) tal que
$$\frac{f(n)}{f(n-1)}=\frac{123456789}{987654321},$$
pero la salida no es \(n\) mismo. Hay que dar su expansión binaria abreviada: se toma la escritura binaria usual, se divide en bloques máximos de bits iguales y se anotan sus longitudes de izquierda a derecha. Por ejemplo, \(241=11110001_2\) se convierte en \([4,3,1]\).
La clave es que la implementación no busca candidatos para \(n\) ni genera una tabla enorme de valores de \(f\). Convierte la fracción objetivo directamente en esas longitudes de racha.
Toda la solución descansa en dos hechos: \(f(n)\) satisface una recurrencia muy rígida según la paridad, y por eso el cociente \(r(n)=f(n)/f(n-1)\) recorre los racionales positivos con reglas simples e invertibles.
Miremos el coeficiente de \(2^0=1\) en una representación de \(n\).
Si \(n=2m+1\) es impar, ese coeficiente tiene que ser exactamente 1. Al quitar ese 1 y dividir entre 2 todas las potencias restantes, obtenemos una biyección con las representaciones de \(m\). Por tanto,
$$f(2m+1)=f(m).$$
Si \(n=2m\) es par, el coeficiente de 1 solo puede ser 0 o 2. En el primer caso, dividir entre 2 produce una representación de \(m\). En el segundo, quitamos los dos unos, dividimos entre 2 y obtenemos una representación de \(m-1\). Luego
$$f(2m)=f(m)+f(m-1)\qquad (m\ge 1).$$
Junto con \(f(0)=1\), esta es exactamente la recurrencia usada por las implementaciones:
$$f(0)=1,\qquad f(2m+1)=f(m),\qquad f(2m)=f(m)+f(m-1).$$
Definamos
$$r(n)=\frac{f(n)}{f(n-1)}\qquad (n\ge 1).$$
Al aplicar la recurrencia al par \((f(n),f(n-1))\), para \(n=2m\) se obtiene
$$r(2m)=\frac{f(m)+f(m-1)}{f(m-1)}=r(m)+1,$$
y para \(n=2m+1\),
$$r(2m+1)=\frac{f(m)}{f(m)+f(m-1)}=\frac{r(m)}{r(m)+1}.$$
Esto ya distingue el último bit de la expansión binaria buscada. Los índices pares producen cocientes \(>1\); los impares, salvo el caso inicial \(r(1)=1\), producen valores estrictamente entre 0 y 1.
La escritura binaria y la recurrencia por paridad encajan exactamente. Si partimos de \(r(1)=1\) y añadimos un bit por la derecha, el cociente cambia mediante una de estas dos transformaciones:
$$0:\ x\mapsto x+1,\qquad 1:\ x\mapsto \frac{x}{x+1}.$$
Por tanto, al leer los bits de izquierda a derecha, cada 0 significa “sumar 1” y cada 1 después del bit inicial significa “reemplazar \(x\) por \(x/(x+1)\)”. Si varios bits iguales aparecen seguidos, la misma transformación se repite varias veces.
De ahí que la expansión binaria abreviada sea el objeto correcto para recuperar. El proceso inverso no necesita construir primero el entero enorme \(n\); devuelve directamente las longitudes de los bloques alternantes de 1 y 0.
Ahora invertimos la recurrencia sobre una fracción positiva reducida \(p/q\).
Si \(p>q\), el último paso debió venir de un índice par, porque solo la transformación \(x\mapsto x+1\) puede producir un valor mayor que 1. Deshacer un paso da
$$\frac{p}{q}\longmapsto \frac{p-q}{q}.$$
Si la desigualdad \(p>q\) sigue siendo cierta, podemos quitar varios ceros finales de una vez. Escribimos
$$p=a q+p',\qquad a=\left\lfloor\frac{p-1}{q}\right\rfloor,\qquad 1\le p'\le q.$$
Entonces \(a\) es la longitud de la última racha de 0 y el subproblema menor es \(p'/q\).
Si \(p\le q\), el último paso debió venir de un índice impar, porque \(x\mapsto x/(x+1)\) toma valores en \((0,1]\). Deshacer un paso da
$$\frac{p}{q}\longmapsto \frac{p}{q-p}.$$
Otra vez agrupamos pasos idénticos. Escribimos
$$q=b p+q',\qquad b=\left\lfloor\frac{q}{p}\right\rfloor,\qquad 0\le q'<p.$$
Ahora \(b\) es la longitud de la última racha de 1 y el subproblema menor es \(p/q'\). Cuando \(q'=0\), se ha alcanzado el bloque inicial de unos al extremo izquierdo. En otras palabras, el algoritmo es un algoritmo de Euclides cuyos cocientes son exactamente la salida pedida.
Tomemos la fracción de comprobación \(13/17\).
Como \(13\le 17\), la expansión binaria termina con un bloque de 1. Dividimos \(17\) entre \(13\):
$$17=1\cdot 13+4.$$
Eso da una longitud final 1 y reduce el problema a \(13/4\).
Ahora \(13>4\), así que antes hay un bloque de 0. En la forma agrupada,
$$13=3\cdot 4+1.$$
Esto aporta la longitud 3 y deja la fracción \(1/4\).
Finalmente,
$$4=4\cdot 1+0,$$
de modo que el bloque inicial de 1 tiene longitud 4. Leyendo de izquierda a derecha obtenemos
$$[4,3,1].$$
En efecto, esta es la expansión abreviada de \(241=11110001_2\), y la comprobación confirma que
$$\frac{f(241)}{f(240)}=\frac{13}{17}.$$
Las implementaciones empiezan reduciendo la fracción de entrada mediante su máximo común divisor. Esto es correcto porque el valor de \(f(n)/f(n-1)\) depende solo del racional reducido.
Después, la rutina principal compara repetidamente numerador y denominador. Si el numerador es mayor, extrae un cociente agrupado correspondiente a una racha de 0 y reemplaza el numerador por el resto ajustado en el intervalo \(1,\dots,q\). Si el denominador es mayor o igual, extrae un cociente agrupado correspondiente a una racha de 1 y reemplaza el denominador por el resto ordinario módulo el numerador. Esos cocientes son exactamente las longitudes de racha de la expansión binaria abreviada.
La versión en C++ produce las longitudes en el orden correcto al deshacer la recursión. Las versiones en Python y Java las acumulan mientras bajan por las reducciones euclídeas y luego invierten la lista una sola vez. Además, la implementación en C++ incorpora comprobaciones pequeñas: verifica la recurrencia sobre valores modestos, la fracción de ejemplo \(13/17\) y la expansión \([4,3,1]\) del entero mínimo correspondiente.
Para la entrada real, ninguna implementación construye el entero posiblemente enorme \(n\). En cuanto la fracción queda descompuesta por completo en sus longitudes alternantes de bloques, se imprimen esas longitudes separadas por comas.
Los pasos de reducción son pasos euclídeos, solo que agrupados por bloques de bits en vez de hacerse como restas individuales. Por ello, el número de iteraciones es \(O(\log \max(p,q))\).
La lista de salida tiene el mismo orden asintótico, así que el uso de memoria también es \(O(\log \max(p,q))\). Para la entrada concreta de Project Euler basta la aritmética de 64 bits, y el método es muy rápido porque evita tanto la búsqueda exhaustiva sobre \(n\) como el cálculo explícito de valores grandes de \(f(n)\).
设 \(f(n)\) 表示把 \(n\) 写成若干个 2 的幂之和的方法数，其中每个幂最多只能使用两次。这正是 \(n\) 的 hyperbinary 表示个数。Project Euler 175 要求找到最小的正整数 \(n\)，使得
$$\frac{f(n)}{f(n-1)}=\frac{123456789}{987654321},$$
但题目并不要求直接输出 \(n\)。要求输出的是 \(n\) 的“缩短二进制展开”：把普通二进制表示切成若干个相邻且最长的相同 bit 块，然后按从左到右的顺序写出各块长度。例如 \(241=11110001_2\)，所以它的缩短二进制展开是 \([4,3,1]\)。
真正高效的做法不是去枚举 \(n\)，也不是为目标输入构造一张很大的 \(f(n)\) 表，而是把目标分数直接反推成这些二进制块长度。
整个解法建立在两个事实之上：第一，\(f(n)\) 按奇偶性满足非常刚性的递推；第二，因此比值 \(r(n)=f(n)/f(n-1)\) 在正有理数集合中会按照非常简单、而且可以唯一反演的规则移动。
先看一个表示里 \(2^0=1\) 的系数。
如果 \(n=2m+1\) 是奇数，那么这个系数只能是 1。去掉这一个 1，再把剩余各项全部除以 2，就和 \(m\) 的表示建立了一一对应，所以
$$f(2m+1)=f(m).$$
如果 \(n=2m\) 是偶数，那么 1 的系数只能是 0 或 2。系数为 0 时，直接整体除以 2，就得到 \(m\) 的一个表示；系数为 2 时，先去掉两个 1，再整体除以 2，就得到 \(m-1\) 的一个表示。因此
$$f(2m)=f(m)+f(m-1)\qquad (m\ge 1).$$
配合初值 \(f(0)=1\)，实现中使用的递推正是
$$f(0)=1,\qquad f(2m+1)=f(m),\qquad f(2m)=f(m)+f(m-1).$$
定义
$$r(n)=\frac{f(n)}{f(n-1)}\qquad (n\ge 1).$$
把上面的递推应用到二元组 \((f(n),f(n-1))\) 上。对于偶数 \(n=2m\)，有
$$r(2m)=\frac{f(m)+f(m-1)}{f(m-1)}=r(m)+1.$$
对于奇数 \(n=2m+1\)，有
$$r(2m+1)=\frac{f(m)}{f(m)+f(m-1)}=\frac{r(m)}{r(m)+1}.$$
这两个公式已经说明了未知整数 \(n\) 的最后一位二进制 bit。偶数下标对应的比值一定大于 1；奇数下标对应的比值除起点 \(r(1)=1\) 外都严格落在 \((0,1)\) 内。也就是说，只要比较目标分数的分子和分母，就知道最后一位是 0 还是 1。
二进制展开和这个奇偶递推可以完全对接。从 \(r(1)=1\) 出发，在二进制串右侧追加一个 bit，会让比值发生下面两种变化之一：
$$0:\ x\mapsto x+1,\qquad 1:\ x\mapsto \frac{x}{x+1}.$$
因此，从左到右读二进制位时，每个 0 都表示“把当前值加 1”，而首位之后的每个 1 都表示“把当前值换成 \(x/(x+1)\)”。如果相同 bit 连续出现，那么同一种变换就会被重复很多次。
这正是题目要求“缩短二进制展开”的原因。反向恢复时，最自然拿到的不是庞大的整数 \(n\) 本身，而是交替出现的 1 块和 0 块的长度。
现在从一个既约正分数 \(p/q\) 反向走回去。
如果 \(p>q\)，那么最后一步一定来自偶数情况，因为只有 \(x\mapsto x+1\) 才会得到大于 1 的值。撤销一步就是
$$\frac{p}{q}\longmapsto \frac{p-q}{q}.$$
如果撤销一次后仍然满足 \(p>q\)，说明末尾其实有一整段连续的 0，可以一次性处理。写成
$$p=a q+p',\qquad a=\left\lfloor\frac{p-1}{q}\right\rfloor,\qquad 1\le p'\le q.$$
那么 \(a\) 就是最后那个 0 块的长度，而更小的子问题变成 \(p'/q\)。
如果 \(p\le q\)，那么最后一步一定来自奇数情况，因为 \(x\mapsto x/(x+1)\) 的值总在 \((0,1]\) 里。撤销一步就是
$$\frac{p}{q}\longmapsto \frac{p}{q-p}.$$
同样可以把重复出现的同类步骤打包。写成
$$q=b p+q',\qquad b=\left\lfloor\frac{q}{p}\right\rfloor,\qquad 0\le q'<p.$$
这里 \(b\) 是最后那个 1 块的长度，而更小的子问题是 \(p/q'\)。当 \(q'=0\) 时，说明已经走回到最左端的初始 1 块。换句话说，整个算法本质上就是欧几里得算法，只不过保留下来的商恰好就是题目要求输出的连续块长度。
来看实现里用作检查的分数 \(13/17\)。
因为 \(13\le 17\)，所以二进制展开末尾一定是一段 1。将 \(17\) 除以 \(13\)：
$$17=1\cdot 13+4.$$
这说明最后一段长度是 1，接下来只需处理 \(13/4\)。
现在 \(13>4\)，说明之前有一段 0。按上面的分组方式可写成
$$13=3\cdot 4+1.$$
于是得到长度 3，并把问题缩小为 \(1/4\)。
最后，
$$4=4\cdot 1+0,$$
所以最左边那段 1 的长度是 4。按从左到右的顺序读出，就是
$$[4,3,1].$$
而这正好对应于 \(241=11110001_2\) 的缩短二进制展开，实现中的检查也验证了
$$\frac{f(241)}{f(240)}=\frac{13}{17}.$$
三种语言的实现都会先用最大公约数把输入分数约成最简形式。这一步不会改变数学问题，因为 \(f(n)/f(n-1)\) 只与对应的既约有理数有关。
之后，主过程不断比较分子和分母。如果分子更大，就提取一个对应 0 块的分组商，并把分子改成落在 \(1,\dots,q\) 范围内的调整余数；如果分母大于或等于分子，就提取一个对应 1 块的分组商，并把分母改成对分子取模后的普通余数。提取出来的这些商，正是最终要输出的缩短二进制展开各段长度。
C++ 实现借助递归回溯，直接按从左到右的顺序输出这些长度。Python 和 Java 实现则是在向下做欧几里得分解时先把长度按相反顺序收集起来，最后统一翻转一次。C++ 版本还包含小规模自检：验证前几个 \(f(n)\) 的值，验证示例分数 \(13/17\)，并确认最小对应整数的缩短二进制展开确实是 \([4,3,1]\)。
对真正的 Project Euler 输入来说，实现从头到尾都不需要构造那个可能非常巨大的 \(n\)。一旦分数被完全拆成交替块长度，程序就把这些长度按逗号分隔输出。
这些约化步骤本质上就是欧几里得步骤，只不过不是一次减去一个，而是按连续 bit 块打包处理。因此迭代次数为 \(O(\log \max(p,q))\)。
输出列表的长度也是同一数量级，所以空间复杂度同样是 \(O(\log \max(p,q))\)。对于题目的具体输入，64 位整数已经足够，算法之所以快，是因为它避免了对 \(n\) 的暴力搜索，也避免了显式计算很大的 \(f(n)\) 值。
Пусть \(f(n)\) обозначает число способов представить \(n\) в виде суммы степеней двойки, если каждую степень разрешено использовать не более двух раз. Это и есть число гипербинарных представлений числа \(n\). В задаче Project Euler требуется найти наименьшее положительное \(n\), для которого
$$\frac{f(n)}{f(n-1)}=\frac{123456789}{987654321},$$
но выводить нужно не само \(n\), а его сокращенную двоичную запись: обычная двоичная запись разбивается на максимальные серии одинаковых битов, и выписываются длины этих серий слева направо. Например, \(241=11110001_2\), поэтому его сокращенная запись равна \([4,3,1]\).
Суть решения в том, что реализации не перебирают кандидаты на \(n\) и не строят для реального входа большую таблицу значений \(f(n)\). Они напрямую превращают заданную дробь в эти длины серий.
Решение опирается на два факта: функция \(f(n)\) имеет очень жесткую рекурсию по четности, а потому отношение \(r(n)=f(n)/f(n-1)\) перемещается по положительным рациональным числам по простым и однозначно обратимым правилам.
Рассмотрим коэффициент при \(2^0=1\) в представлении числа \(n\).
Если \(n=2m+1\) нечетно, этот коэффициент обязан быть равен 1. Если удалить эту единицу и поделить все остальные степени двойки на 2, получится биекция с представлениями числа \(m\). Следовательно,
$$f(2m+1)=f(m).$$
Если \(n=2m\) четно, коэффициент при 1 может быть только 0 или 2. В первом случае деление на 2 дает представление числа \(m\). Во втором случае удаляем две единицы, делим на 2 и получаем представление числа \(m-1\). Поэтому
$$f(2m)=f(m)+f(m-1)\qquad (m\ge 1).$$
Вместе с начальным условием \(f(0)=1\) это ровно та рекурсия, которая используется в коде:
$$f(0)=1,\qquad f(2m+1)=f(m),\qquad f(2m)=f(m)+f(m-1).$$
Определим
$$r(n)=\frac{f(n)}{f(n-1)}\qquad (n\ge 1).$$
Подставляя рекурсию в пару \((f(n),f(n-1))\), для четного \(n=2m\) получаем
$$r(2m)=\frac{f(m)+f(m-1)}{f(m-1)}=r(m)+1,$$
а для нечетного \(n=2m+1\)
$$r(2m+1)=\frac{f(m)}{f(m)+f(m-1)}=\frac{r(m)}{r(m)+1}.$$
Из этого сразу видно, как заканчивается двоичная запись искомого числа. У четных индексов отношение больше 1, а у нечетных, кроме стартового значения \(r(1)=1\), оно лежит строго между 0 и 1. Значит, сравнение числителя и знаменателя целевой дроби уже сообщает, последняя двоичная цифра равна 0 или 1.
Двоичная запись идеально согласована с рекурсией по четности. Если начать с \(r(1)=1\) и дописывать справа двоичные цифры, отношение будет меняться по одной из двух схем:
$$0:\ x\mapsto x+1,\qquad 1:\ x\mapsto \frac{x}{x+1}.$$
Поэтому при чтении двоичной записи слева направо каждая цифра 0 означает «прибавить 1», а каждая цифра 1 после ведущей единицы означает «заменить \(x\) на \(x/(x+1)\)». Если одинаковые биты идут подряд, то одна и та же операция просто повторяется несколько раз.
Именно поэтому сокращенная двоичная запись является правильным объектом для восстановления. Обратный процесс не обязан сначала строить огромное число \(n\); он сразу восстанавливает длины чередующихся блоков единиц и нулей.
Теперь пустим рекурсию назад по сокращенной положительной дроби \(p/q\).
Если \(p>q\), последний шаг должен был прийти от четного индекса, потому что только преобразование \(x\mapsto x+1\) дает значение больше 1. Один обратный шаг имеет вид
$$\frac{p}{q}\longmapsto \frac{p-q}{q}.$$
Если после этого все еще выполняется \(p>q\), можно снять сразу целую конечную серию нулей. Для этого пишем
$$p=a q+p',\qquad a=\left\lfloor\frac{p-1}{q}\right\rfloor,\qquad 1\le p'\le q.$$
Тогда \(a\) есть длина последней серии нулей, а меньшая задача становится \(p'/q\).
Если \(p\le q\), последний шаг должен был прийти от нечетного индекса, потому что \(x\mapsto x/(x+1)\) всегда попадает в интервал \((0,1]\). Один обратный шаг имеет вид
$$\frac{p}{q}\longmapsto \frac{p}{q-p}.$$
И здесь одинаковые шаги можно сгруппировать. Пишем
$$q=b p+q',\qquad b=\left\lfloor\frac{q}{p}\right\rfloor,\qquad 0\le q'<p.$$
Теперь \(b\) есть длина последней серии единиц, а меньшая задача равна \(p/q'\). Когда \(q'=0\), мы дошли до начального левого блока единиц. Иначе говоря, алгоритм представляет собой алгоритм Евклида, в котором сохраняемые частные и есть искомый ответ.
Возьмем дробь \(13/17\), используемую для проверки.
Так как \(13\le 17\), двоичная запись заканчивается серией единиц. Делим \(17\) на \(13\):
$$17=1\cdot 13+4.$$
Это дает конечную длину 1 и сводит задачу к дроби \(13/4\).
Теперь \(13>4\), значит перед этим шла серия нулей. В группированной форме имеем
$$13=3\cdot 4+1.$$
Получаем длину 3 и сокращаем задачу до \(1/4\).
Наконец,
$$4=4\cdot 1+0,$$
поэтому начальная серия единиц имеет длину 4. Читая слева направо, получаем
$$[4,3,1].$$
И действительно, это сокращенная двоичная запись числа \(241=11110001_2\), а проверка подтверждает равенство
$$\frac{f(241)}{f(240)}=\frac{13}{17}.$$
Сначала реализации сокращают входную дробь по наибольшему общему делителю. Это корректно, потому что значение \(f(n)/f(n-1)\) определяется только приведенным рациональным числом.
Далее основная процедура многократно сравнивает числитель и знаменатель. Если числитель больше, извлекается один сгруппированный частный, соответствующий серии нулей, а числитель заменяется специальным остатком из диапазона \(1,\dots,q\). Если знаменатель больше либо равен, извлекается сгруппированный частный для серии единиц, а знаменатель заменяется обычным остатком по модулю числителя. Эти частные и есть длины серий в сокращенной двоичной записи ответа.
Версия на C++ выдает длины в правильном порядке во время обратного хода рекурсии. Версии на Python и Java сначала накапливают их в обратном порядке, а затем один раз переворачивают список. Кроме того, реализация на C++ содержит небольшие проверки: значения \(f(n)\) на малых \(n\), дробь-пример \(13/17\) и сокращенную запись \([4,3,1]\) для соответствующего минимального числа.
Для реального входа ни одна из реализаций не строит потенциально огромное число \(n\). Как только дробь полностью разложена на чередующиеся длины блоков, эти длины печатаются через запятую.
Шаги сокращения представляют собой шаги алгоритма Евклида, только сгруппированные по блокам битов вместо выполнения по одной вычитательной операции. Поэтому число итераций равно \(O(\log \max(p,q))\).
Длина выходного списка имеет тот же порядок, так что и потребление памяти равно \(O(\log \max(p,q))\). Для конкретного входа Project Euler достаточно 64-битной арифметики, а метод работает очень быстро, потому что полностью избегает и перебора по \(n\), и явного вычисления больших значений \(f(n)\).
لتكن \(f(n)\) عدد الطرق المختلفة لكتابة \(n\) على صورة مجموع لقوى العدد 2، مع السماح باستعمال كل قوة بحد أقصى مرتين. هذا هو عدد التمثيلات hyperbinary للعدد \(n\). في مسألة Project Euler المطلوب هو إيجاد أصغر عدد صحيح موجب \(n\) يحقق
$$\frac{f(n)}{f(n-1)}=\frac{123456789}{987654321},$$
لكن المطلوب في الإخراج ليس \(n\) نفسه، بل تمثيله الثنائي المختصر: نأخذ الكتابة الثنائية المعتادة، نقسمها إلى كتل عظمى من البتات المتساوية، ثم نكتب أطوال هذه الكتل من اليسار إلى اليمين. على سبيل المثال، \(241=11110001_2\)، ولذلك يكون تمثيله المختصر \([4,3,1]\).
الفكرة الحاسمة هي أن التنفيذ لا يبحث عن \(n\) بالتجربة ولا يبني جدولًا ضخمًا لقيم \(f(n)\) من أجل المُدخل الحقيقي. بل يحول الكسر الهدف مباشرة إلى أطوال الكتل الثنائية.
الحل كله يعتمد على حقيقتين: الدالة \(f(n)\) تملك علاقة عودية صارمة جدًا بحسب parity العدد، ولذلك فإن النسبة \(r(n)=f(n)/f(n-1)\) تتحرك داخل مجموعة الكسور الموجبة بقواعد بسيطة وقابلة للعكس على نحو وحيد.
انظر إلى معامل \(2^0=1\) في أي تمثيل للعدد \(n\).
إذا كان \(n=2m+1\) فرديًا، فلا بد أن يكون هذا المعامل مساويًا لـ 1 بالضبط. بعد حذف هذه الـ 1 ثم قسمة جميع القوى المتبقية على 2، نحصل على تقابل واحد لواحد مع تمثيلات العدد \(m\). لذلك
$$f(2m+1)=f(m).$$
أما إذا كان \(n=2m\) زوجيًا، فإن معامل 1 لا يمكن أن يكون إلا 0 أو 2. إذا كان 0، فإن القسمة على 2 تعطي تمثيلًا لـ \(m\). وإذا كان 2، فإن حذف الواحدين ثم القسمة على 2 يعطي تمثيلًا لـ \(m-1\). ومن ثم
$$f(2m)=f(m)+f(m-1)\qquad (m\ge 1).$$
ومع الشرط الابتدائي \(f(0)=1\)، فهذه هي بالضبط العلاقة المستعملة في الشيفرات:
$$f(0)=1,\qquad f(2m+1)=f(m),\qquad f(2m)=f(m)+f(m-1).$$
لنعرّف
$$r(n)=\frac{f(n)}{f(n-1)}\qquad (n\ge 1).$$
عند تطبيق العلاقة العودية على الزوج \((f(n),f(n-1))\)، نجد أنه إذا كان \(n=2m\) زوجيًا فـ
$$r(2m)=\frac{f(m)+f(m-1)}{f(m-1)}=r(m)+1,$$
وإذا كان \(n=2m+1\) فرديًا فـ
$$r(2m+1)=\frac{f(m)}{f(m)+f(m-1)}=\frac{r(m)}{r(m)+1}.$$
هذان القانونان يكشفان مباشرة آخر بت في الكتابة الثنائية للعدد المطلوب. فالمؤشرات الزوجية تعطي نسبًا أكبر من 1، بينما المؤشرات الفردية تعطي نسبًا داخل \((0,1)\) باستثناء الحالة الابتدائية \(r(1)=1\). لذا فمجرد مقارنة البسط بالمقام تخبرنا إن كانت النهاية الثنائية هي 0 أم 1.
الكتابة الثنائية منسجمة تمامًا مع هذه العودية المبنية على parity. إذا بدأنا من \(r(1)=1\) وألحقنا بتًا من اليمين، فإن النسبة تتغير بإحدى التحويلين التاليين:
$$0:\ x\mapsto x+1,\qquad 1:\ x\mapsto \frac{x}{x+1}.$$
إذن، عند قراءة البتات من اليسار إلى اليمين، كل 0 يعني “أضف 1”، وكل 1 بعد البت الافتتاحي يعني “استبدل \(x\) بـ \(x/(x+1)\)”. وإذا تكررت البتات نفسها متتالية، فهذا يعني ببساطة تكرار التحويل نفسه عدة مرات.
لهذا السبب فإن التمثيل الثنائي المختصر هو الشكل الطبيعي للإجابة. فعملية العكس لا تحتاج أولًا إلى بناء العدد الضخم \(n\)، بل تستعيد مباشرة أطوال الكتل المتعاقبة من 1 و0.
الآن لنشغّل العلاقة العكسية على كسر موجب مختزل \(p/q\).
إذا كان \(p>q\)، فلا بد أن الخطوة الأخيرة جاءت من حالة زوجية، لأن التحويل \(x\mapsto x+1\) وحده هو الذي ينتج قيمة أكبر من 1. والتراجع بخطوة واحدة يعطينا
$$\frac{p}{q}\longmapsto \frac{p-q}{q}.$$
إذا بقيت المتباينة \(p>q\) صحيحة بعد ذلك، فيمكن إزالة عدة أصفار نهائية دفعة واحدة. نكتب
$$p=a q+p',\qquad a=\left\lfloor\frac{p-1}{q}\right\rfloor,\qquad 1\le p'\le q.$$
عندها يكون \(a\) هو طول الكتلة الأخيرة من الأصفار، وتصبح المسألة الأصغر هي \(p'/q\).
أما إذا كان \(p\le q\)، فلا بد أن الخطوة الأخيرة جاءت من حالة فردية، لأن \(x\mapsto x/(x+1)\) يبقي القيم داخل \((0,1]\). والتراجع بخطوة واحدة هو
$$\frac{p}{q}\longmapsto \frac{p}{q-p}.$$
وهنا أيضًا يمكن تجميع الخطوات المتشابهة. نكتب
$$q=b p+q',\qquad b=\left\lfloor\frac{q}{p}\right\rfloor,\qquad 0\le q'<p.$$
في هذه الحالة يكون \(b\) هو طول الكتلة الأخيرة من الواحدات، وتصبح المسألة الأصغر \(p/q'\). وإذا حصلنا على \(q'=0\)، فهذا يعني أننا وصلنا إلى الكتلة الابتدائية من الواحدات في أقصى اليسار. وبهذا المعنى، فالخوارزمية هي خوارزمية إقليدس، لكن خارج القسمة المحفوظة فيها هو نفسه الجواب المطلوب طباعته.
لنأخذ الكسر المستخدم في الفحوص \(13/17\).
بما أن \(13\le 17\)، فالنهاية الثنائية لا بد أن تكون كتلة من الواحدات. نقسم \(17\) على \(13\):
$$17=1\cdot 13+4.$$
إذن طول الكتلة الأخيرة هو 1، وتتحول المسألة إلى \(13/4\).
الآن \(13>4\)، وهذا يعني أن هناك قبلها كتلة من الأصفار. بالصيغة المجمعة نحصل على
$$13=3\cdot 4+1.$$
وهذا يضيف طولًا مقداره 3 ويختزل المسألة إلى \(1/4\).
وأخيرًا،
$$4=4\cdot 1+0,$$
أي إن الكتلة الافتتاحية من الواحدات طولها 4. وعند قراءة الأطوال من اليسار إلى اليمين نحصل على
$$[4,3,1].$$
وفعلًا، هذه هي أطوال الكتل في \(241=11110001_2\)، كما تؤكد عملية الفحص أن
$$\frac{f(241)}{f(240)}=\frac{13}{17}.$$
تبدأ التطبيقات الثلاثة باختزال الكسر المدخل بواسطة القاسم المشترك الأكبر. وهذا لا يغير المسألة رياضيًا، لأن قيمة \(f(n)/f(n-1)\) تعتمد فقط على الصورة المختزلة للكسر.
بعد ذلك، تقارن العملية الرئيسية بين البسط والمقام مرارًا. فإذا كان البسط أكبر، استخرجت خارج قسمة مجمعًا يمثل كتلة من الأصفار، ثم استبدلت البسط بباقٍ معدل يقع في المجال \(1,\dots,q\). وإذا كان المقام أكبر أو مساويًا، استخرجت خارج قسمة مجمعًا يمثل كتلة من الواحدات، ثم استبدلت المقام بالباقي العادي modulo البسط. هذه القيم المجمعة هي نفسها أطوال الكتل التي تشكل الجواب النهائي.
تنفيذ C++ يخرج الأطوال مباشرة بالترتيب الصحيح أثناء العودة من الاستدعاء التعاودي. أما تنفيذا Python وJava فيجمعان الأطوال أولًا بترتيب معكوس ثم يعكسان القائمة مرة واحدة في النهاية. كما أن تنفيذ C++ يحتوي على فحوص صغيرة: التحقق من قيم أولية لـ \(f(n)\)، والتحقق من الكسر \(13/17\)، والتأكد من أن العدد الأدنى الموافق له يملك التمثيل المختصر \([4,3,1]\).
بالنسبة إلى المُدخل الحقيقي للمسألة، لا يحتاج أي تنفيذ إلى بناء العدد الكبير \(n\) نفسه. بمجرد أن يتحلل الكسر بالكامل إلى أطوال كتل متناوبة، تُطبع هذه الأطوال مفصولة بفواصل.
خطوات الاختزال هنا هي في جوهرها خطوات من خوارزمية إقليدس، لكنها مجمعة بحسب كتل البتات بدل تنفيذها على شكل طرح منفرد في كل مرة. لذلك يكون عدد التكرارات \(O(\log \max(p,q))\).
وطول قائمة الخرج من نفس الرتبة التقريبية، لذا يكون استهلاك الذاكرة أيضًا \(O(\log \max(p,q))\). وفي المُدخل المحدد لمسألة Project Euler تكفي الحسابات على أعداد 64-بت، وتكون الطريقة سريعة جدًا لأنها تتجنب تمامًا البحث الشامل عن \(n\) وكذلك الحساب الصريح لقيم كبيرة من \(f(n)\).