Let \(\phi=\dfrac{1+\sqrt5}{2}\). The problem asks for the sum of all positive integers at most \(L\) whose canonical base-\(\phi\) representation is palindromic around the radix point. The implementation uses the standard phinary digit rules: every digit is \(0\) or \(1\), and no two adjacent digits may both be \(1\).
If the left half of the palindrome is \(d_{n-1}\dots d_1d_0\), then the full representation is \(d_{n-1}\dots d_1d_0.d_0d_1\dots d_{n-1}\) in base \(\phi\). The highest digit must be \(1\), and the central pair forces \(d_0=0\), because the two digits adjacent to the radix point are equal and therefore cannot both be \(1\).
The actual limit is \(L=10^{10}\). A built-in checkpoint is
$$\sum_{\substack{x\le 1000\\ x\text{ phigital}}} x = 4345,$$
which the C++, Python, and Java implementations all use as a sanity check.
The key observation is that a palindromic base-\(\phi\) string can be rewritten as a sum of paired powers \(\phi^i+\phi^{-i-1}\). That converts the problem from digit strings into a meet-in-the-middle search over integer linear combinations.
For digits \(d_i\in\{0,1\}\), define
$$w_i=\phi^i+\phi^{-i-1}.$$
Then every palindromic representation described above has value
$$x=\sum_{i=0}^{n-1} d_i w_i.$$
The admissibility conditions become purely combinatorial:
$$d_{n-1}=1,\qquad d_0=0,\qquad d_i d_{i+1}=0 \text{ for } 0\le i\lt n-1.$$
So the search space is not all binary strings, but exactly the legal no-adjacent-ones strings with fixed boundary digits.
Let \(F_0=0\), \(F_1=1\). For \(k\ge 1\),
$$\phi^k = F_k\phi + F_{k-1}.$$
For negative powers,
$$\phi^{-m}=(-1)^m\left(F_{m+1}-F_m\phi\right).$$
Therefore every paired weight can be written as
$$w_i=u_i+v_i\phi,$$
with integer coefficients \(u_i,v_i\) that can be precomputed once. The first few values are
$$w_0=\phi,\qquad w_1=2,\qquad w_2=3\phi-2,\qquad w_3=6-\phi,\qquad w_4=8\phi-5.$$
This is exactly why the implementation stores, for each digit position, one coefficient for the rational part and one coefficient for the \(\phi\)-part.
Summing the chosen weights gives
$$x=\sum_{i=0}^{n-1} d_i(u_i+v_i\phi)=U+V\phi,$$
where
$$U=\sum_{i=0}^{n-1} d_i u_i,\qquad V=\sum_{i=0}^{n-1} d_i v_i.$$
Because \(1\) and \(\phi\) are linearly independent over \(\mathbb{Q}\), the value \(x\) is an integer if and only if
$$V=0.$$
When that happens, the actual integer is simply
$$x=U.$$
So the problem is reduced to finding all legal digit strings for which the irrational coefficient vanishes and the remaining integer coefficient satisfies
$$1\le U\le L.$$
For a fixed length \(n\), split the positions at a midpoint. The lower half contributes a pair \((U_{\ell},V_{\ell})\) and remembers its last digit near the split. The upper half contributes \((U_h,V_h)\) and remembers its first digit near the split.
A merge is valid exactly when three conditions hold:
$$V_{\ell}+V_h=0,$$
$$1\le U_{\ell}+U_h\le L,$$
and the two boundary digits are not both \(1\).
This turns a global search into two smaller enumerations plus a structured merge step.
All upper-half states are grouped by their value of \(V_h\) and by their first boundary digit. Inside each group, the \(U_h\) values are sorted and equipped with prefix sums.
For one fixed lower-half state, only groups with
$$V_h=-V_{\ell}$$
can possibly cancel the \(\phi\)-part. The range condition becomes
$$1-U_{\ell}\le U_h\le L-U_{\ell}.$$
Two binary searches locate the admissible interval in the sorted list. If that interval contains \(c\) states and their \(U_h\)-sum is \(S\), then the total contribution of this lower-half state is
$$c\,U_{\ell}+S.$$
That formula accumulates the sum of all resulting integers without iterating over every matching pair one by one.
The legal palindrome
$$100100.001001_{\phi}$$
uses positions \(5\) and \(2\), so
$$x=w_5+w_2=(13-3\phi)+(3\phi-2)=11.$$
The \(\phi\)-terms cancel exactly, leaving the integer \(11\). This is the basic phenomenon the algorithm searches for at scale. The special case \(x=1\) is handled separately at the start, because it is a one-digit phigital number and does not belong to the paired-length loop.
The implementation first precomputes Fibonacci numbers and, from them, the paired coefficients \((u_i,v_i)\) for all digit positions that can matter below the given limit. It then immediately initializes the answer with \(1\), covering the standalone phigital number \(1\).
For each candidate palindrome length, the implementation computes the minimum and maximum possible value of the integer coefficient \(U\) under the digit rules. If that interval does not intersect \([1,L]\), the entire length can be skipped before any meet-in-the-middle work begins.
Otherwise it recursively enumerates all legal lower-half states and all legal upper-half states. Each state records its contribution to the rational coefficient, its contribution to the \(\phi\)-coefficient, and the boundary digit needed to enforce the no-adjacent-ones rule across the split.
The upper-half states are reorganized into lookup tables keyed by the \(\phi\)-coefficient and the boundary bit. Inside each table entry, the rational coefficients are sorted and accompanied by prefix sums. The lower-half enumeration then probes only the entries that can cancel the irrational part, performs two binary searches for the admissible interval, and adds the resulting block contribution to the total.
For a length \(n\), each half enumerates only legal binary strings with no adjacent ones, so the state count grows like a Fibonacci sequence. A convenient worst-case description is still
$$O\!\left(2^{n/2}\log 2^{n/2}\right),$$
because sorting and binary searching dominate after the split. In practice the no-adjacent-ones restriction makes the actual state count noticeably smaller than \(2^{n/2}\).
The memory usage is linear in the number of stored upper-half states for the current length. Since only lengths up to a fixed safe cutoff are explored, the method is easily feasible for \(L=10^{10}\), whereas a direct enumeration of all full digit strings would be hopeless.
Sei \(\phi=\dfrac{1+\sqrt5}{2}\). Gesucht ist die Summe aller positiven ganzen Zahlen bis \(L\), deren kanonische Darstellung zur Basis \(\phi\) um das Komma herum palindromisch ist. Die Implementierung benutzt die üblichen Regeln der Phinary-Darstellung: Jede Ziffer ist \(0\) oder \(1\), und zwei benachbarte Ziffern dürfen nicht beide \(1\) sein.
Wenn die linke Hälfte des Palindroms \(d_{n-1}\dots d_1d_0\) lautet, dann ist die vollständige Darstellung \(d_{n-1}\dots d_1d_0.d_0d_1\dots d_{n-1}\) in Basis \(\phi\). Die höchste Ziffer muss \(1\) sein, und das mittlere Ziffernpaar erzwingt \(d_0=0\), weil die beiden an das Komma angrenzenden Ziffern gleich sind und daher nicht beide \(1\) sein können.
Die eigentliche Schranke ist \(L=10^{10}\). Ein eingebauter Kontrollwert lautet
$$\sum_{\substack{x\le 1000\\ x\text{ phigital}}} x = 4345,$$
und genau diesen Prüfpunkt verwenden die C++-, Python- und Java-Implementierungen.
Die zentrale Beobachtung ist, dass sich ein palindromischer Basis-\(\phi\)-String als Summe gepaarter Potenzen \(\phi^i+\phi^{-i-1}\) schreiben lässt. Dadurch wird aus einer Ziffernaufgabe eine Meet-in-the-middle-Suche über ganzzahlige Linearkombinationen.
Für Ziffern \(d_i\in\{0,1\}\) definieren wir
$$w_i=\phi^i+\phi^{-i-1}.$$
Dann hat jede oben beschriebene palindromische Darstellung den Wert
$$x=\sum_{i=0}^{n-1} d_i w_i.$$
Die Zulässigkeitsbedingungen sind rein kombinatorisch:
$$d_{n-1}=1,\qquad d_0=0,\qquad d_i d_{i+1}=0 \text{ für } 0\le i\lt n-1.$$
Der Suchraum besteht also nicht aus allen Binärwörtern, sondern genau aus den legalen Wörtern ohne benachbarte Einsen und mit festen Randziffern.
Es seien \(F_0=0\) und \(F_1=1\). Für \(k\ge 1\) gilt
$$\phi^k = F_k\phi + F_{k-1}.$$
Für negative Potenzen gilt
$$\phi^{-m}=(-1)^m\left(F_{m+1}-F_m\phi\right).$$
Damit lässt sich jedes gepaarte Gewicht als
$$w_i=u_i+v_i\phi$$
mit ganzzahligen Koeffizienten \(u_i,v_i\) schreiben, die einmalig vorab berechnet werden. Die ersten Werte sind
$$w_0=\phi,\qquad w_1=2,\qquad w_2=3\phi-2,\qquad w_3=6-\phi,\qquad w_4=8\phi-5.$$
Genau deshalb speichert die Implementierung pro Ziffernposition einen rationalen und einen \(\phi\)-Koeffizienten.
Die Summe der gewählten Gewichte hat die Form
$$x=\sum_{i=0}^{n-1} d_i(u_i+v_i\phi)=U+V\phi,$$
wobei
$$U=\sum_{i=0}^{n-1} d_i u_i,\qquad V=\sum_{i=0}^{n-1} d_i v_i.$$
Da \(1\) und \(\phi\) über \(\mathbb{Q}\) linear unabhängig sind, ist \(x\) genau dann eine ganze Zahl, wenn
$$V=0.$$
In diesem Fall ist die gesuchte ganze Zahl einfach
$$x=U.$$
Das Problem reduziert sich also darauf, alle legalen Ziffernfolgen zu finden, für die der irrationale Koeffizient verschwindet und der verbleibende ganze Koeffizient die Schranke
$$1\le U\le L$$
erfüllt.
Für eine feste Länge \(n\) wird am Mittelpunkt geteilt. Die untere Hälfte liefert ein Paar \((U_{\ell},V_{\ell})\) und merkt sich die letzte Ziffer an der Schnittstelle. Die obere Hälfte liefert \((U_h,V_h)\) und merkt sich die erste Ziffer an der Schnittstelle.
Eine Zusammenführung ist genau dann gültig, wenn drei Bedingungen erfüllt sind:
$$V_{\ell}+V_h=0,$$
$$1\le U_{\ell}+U_h\le L,$$
und die beiden Randziffern an der Teilungsstelle sind nicht gleichzeitig \(1\).
Damit wird aus einer globalen Suche eine Kombination aus zwei kleineren Enumerationen und einem strukturierten Zusammenführen.
Alle Zustände der oberen Hälfte werden nach ihrem Wert \(V_h\) und nach der ersten Randziffer gruppiert. Innerhalb jeder Gruppe werden die \(U_h\)-Werte sortiert und mit Präfixsummen versehen.
Für einen festen Zustand der unteren Hälfte können nur Gruppen mit
$$V_h=-V_{\ell}$$
den \(\phi\)-Anteil eliminieren. Die Bereichsbedingung wird zu
$$1-U_{\ell}\le U_h\le L-U_{\ell}.$$
Zwei Binärsuchen finden das zulässige Intervall. Enthält dieses Intervall \(c\) Zustände und haben diese zusammen \(U_h\)-Summe \(S\), dann ist der Gesamtbeitrag des unteren Zustands
$$c\,U_{\ell}+S.$$
So wird direkt die Summe aller resultierenden ganzen Zahlen akkumuliert, ohne jedes passende Paar einzeln zu durchlaufen.
Das legale Palindrom
$$100100.001001_{\phi}$$
benutzt die Positionen \(5\) und \(2\), also
$$x=w_5+w_2=(13-3\phi)+(3\phi-2)=11.$$
Die \(\phi\)-Terme heben sich exakt auf, und übrig bleibt die ganze Zahl \(11\). Genau nach diesem Phänomen sucht der Algorithmus in großem Maßstab. Der Spezialfall \(x=1\) wird zu Beginn separat erfasst, weil er ein phigitaler Ein-Ziffern-Wert ist und nicht in die Schleife über gepaarte Längen fällt.
Die Implementierung berechnet zuerst Fibonacci-Zahlen vor und daraus für jede relevante Ziffernposition die gepaarten Koeffizienten \((u_i,v_i)\). Anschließend wird das Ergebnis sofort mit \(1\) initialisiert, um die eigenständige phigitale Zahl \(1\) abzudecken.
Für jede mögliche Palindromlänge bestimmt die Implementierung dann den minimalen und maximalen erreichbaren Wert des ganzzahligen Koeffizienten \(U\) unter den Ziffernregeln. Schneidet dieses Intervall \([1,L]\) nicht, kann die gesamte Länge ohne weitere Arbeit übersprungen werden.
Andernfalls werden rekursiv alle legalen Zustände der unteren und oberen Hälfte erzeugt. Jeder Zustand speichert seinen Beitrag zum rationalen Anteil, seinen Beitrag zum \(\phi\)-Anteil und die Randziffer, die für die Prüfung der Teilungsstelle benötigt wird.
Die Zustände der oberen Hälfte werden danach in Nachschlagetabellen organisiert, indiziert durch den \(\phi\)-Koeffizienten und das Randbit. Innerhalb jedes Eintrags werden die rationalen Koeffizienten sortiert und mit Präfixsummen kombiniert. Die untere Hälfte fragt dann nur die Einträge ab, die den irrationalen Anteil aufheben können, führt zwei Binärsuchen für das zulässige Intervall aus und addiert den entsprechenden Blockbeitrag zum Gesamtergebnis.
Für eine Länge \(n\) enumeriert jede Hälfte nur legale Binärwörter ohne benachbarte Einsen; die Anzahl der Zustände wächst also Fibonacci-artig. Als bequeme Worst-Case-Beschreibung kann man dennoch schreiben
$$O\!\left(2^{n/2}\log 2^{n/2}\right),$$
weil nach der Teilung Sortierung und Binärsuche dominieren. In der Praxis ist die tatsächliche Zustandszahl wegen des Adjazenzverbots merklich kleiner als \(2^{n/2}\).
Der Speicherbedarf ist linear in der Zahl der gespeicherten Zustände der oberen Hälfte für die aktuelle Länge. Da nur Längen bis zu einer festen sicheren Grenze untersucht werden, ist die Methode für \(L=10^{10}\) gut beherrschbar, während eine direkte Enumeration aller vollständigen Ziffernfolgen aussichtslos wäre.
\(\phi=\dfrac{1+\sqrt5}{2}\) olsun. Problem, kanonik taban-\(\phi\) gösterimi radix noktasına göre palindrom olan ve \(L\)'yi aşmayan bütün pozitif tamsayıların toplamını istiyor. Uygulama, standart phinary kurallarını kullanır: her basamak \(0\) veya \(1\) olur ve yan yana iki basamak aynı anda \(1\) olamaz.
Palindromun sol yarısı \(d_{n-1}\dots d_1d_0\) ise tam gösterim taban \(\phi\)'de \(d_{n-1}\dots d_1d_0.d_0d_1\dots d_{n-1}\) biçimindedir. En büyük basamak \(1\) olmalıdır; orta çiftten dolayı da \(d_0=0\) zorunludur, çünkü radix noktasının iki yanındaki bitler eşittir ve ikisi birden \(1\) olamaz.
Asıl sınır \(L=10^{10}\)'dur. Kod içindeki kontrol noktası
$$\sum_{\substack{x\le 1000\\ x\text{ phigital}}} x = 4345$$
şeklindedir; C++, Python ve Java uygulamaları bu değeri doğrulama amacıyla kullanır.
Ana fikir şudur: radix noktasına göre palindrom olan bir taban-\(\phi\) dizisi, \(\phi^i+\phi^{-i-1}\) biçimindeki eşlenik ağırlıkların toplamına dönüştürülebilir. Böylece sorun bir basamak dizisi problemi olmaktan çıkıp tamsayı katsayılı bir meet-in-the-middle aramasına dönüşür.
\(d_i\in\{0,1\}\) için
$$w_i=\phi^i+\phi^{-i-1}$$
tanımını yapalım. O zaman yukarıdaki biçimdeki her palindromun değeri
$$x=\sum_{i=0}^{n-1} d_i w_i$$
olur. Geçerlilik koşulları artık yalnızca birleşimsel şartlardır:
$$d_{n-1}=1,\qquad d_0=0,\qquad d_i d_{i+1}=0 \text{ için } 0\le i\lt n-1.$$
Yani taranan uzay tüm ikili diziler değildir; sınır bitleri sabitlenmiş ve ardışık \(1\) içermeyen yasal dizilerdir.
\(F_0=0\), \(F_1=1\) olsun. \(k\ge 1\) için
$$\phi^k = F_k\phi + F_{k-1}$$
eşitliği vardır. Negatif kuvvetler için ise
$$\phi^{-m}=(-1)^m\left(F_{m+1}-F_m\phi\right)$$
kullanılır. Böylece her eşlenik ağırlık
$$w_i=u_i+v_i\phi$$
şeklinde, önceden hesaplanabilir tamsayı katsayılarıyla yazılır. İlk değerler şöyledir:
$$w_0=\phi,\qquad w_1=2,\qquad w_2=3\phi-2,\qquad w_3=6-\phi,\qquad w_4=8\phi-5.$$
Bu yüzden uygulama her basamak konumu için bir rasyonel katsayı ve bir de \(\phi\)-katsayısı saklar.
Seçilen ağırlıkların toplamı
$$x=\sum_{i=0}^{n-1} d_i(u_i+v_i\phi)=U+V\phi$$
biçimindedir; burada
$$U=\sum_{i=0}^{n-1} d_i u_i,\qquad V=\sum_{i=0}^{n-1} d_i v_i.$$
\(1\) ile \(\phi\), \(\mathbb{Q}\) üzerinde lineer bağımsız olduğundan \(x\) ancak ve ancak
$$V=0$$
olduğunda tamsayıdır. Bu durumda gerçek değer doğrudan
$$x=U$$
olur. Dolayısıyla sorun, hem irrasyonel katsayısı yok olan hem de
$$1\le U\le L$$
koşulunu sağlayan bütün yasal basamak dizilerini bulmaya indirgenir.
Sabit bir \(n\) uzunluğu için konumlar ortadan ikiye ayrılır. Alt yarı \((U_{\ell},V_{\ell})\) katkısını ve bölme noktasındaki son biti, üst yarı ise \((U_h,V_h)\) katkısını ve ilk biti üretir.
Birleşmenin geçerli olması için üç koşul gerekir:
$$V_{\ell}+V_h=0,$$
$$1\le U_{\ell}+U_h\le L,$$
ve bölme çizgisinin iki yanında yer alan sınır bitleri birlikte \(1\) olmamalıdır.
Böylece tek parça küresel arama yerine, iki küçük durum üretimi ve düzenli bir birleştirme adımı elde edilir.
Üst yarıdaki bütün durumlar, \(V_h\) değerlerine ve ilk sınır bitlerine göre gruplanır. Her grupta \(U_h\) değerleri sıralanır ve önek toplam dizileri oluşturulur.
Belirli bir alt-yarı durumu için yalnızca
$$V_h=-V_{\ell}$$
şartını sağlayan gruplar irrasyonel kısmı silebilir. Aralık koşulu da
$$1-U_{\ell}\le U_h\le L-U_{\ell}$$
şeklini alır. İki ikili arama, uygun aralığı bulur. Bu aralıkta \(c\) durum varsa ve bunların \(U_h\) toplamı \(S\) ise, alt-yarı durumunun toplam katkısı
$$c\,U_{\ell}+S$$
olur. Böylece her eşleşen çifti tek tek gezmeden bütün tamsayı katkıları toplanır.
Yasal palindrom
$$100100.001001_{\phi}$$
\(5\) ve \(2\) konumlarını kullanır; dolayısıyla
$$x=w_5+w_2=(13-3\phi)+(3\phi-2)=11.$$
\(\phi\)-terimleri tam olarak birbirini götürür ve sonuçta \(11\) kalır. Algoritmanın büyük ölçekte aradığı temel olay budur. Özel \(x=1\) durumu ise başta ayrı eklenir; çünkü bu değer tek basamaklı bir phigital sayıdır ve eşlenik uzunluk döngüsünün dışında kalır.
Uygulama önce Fibonacci sayılarını ve bunlardan türeyen \((u_i,v_i)\) eşlenik katsayılarını, verilen sınır altında gerekebilecek bütün basamak konumları için önceden hesaplar. Ardından bağımsız phigital sayı \(1\) için toplamı \(1\) ile başlatır.
Sonra her aday palindrom uzunluğu için, basamak kuralları altında ulaşılabilecek en küçük ve en büyük \(U\) değerlerini hesaplar. Bu aralık \([1,L]\) ile kesişmiyorsa o uzunluk daha meet-in-the-middle aşamasına gelmeden tamamen atlanır.
Aralık uygunsa alt yarıdaki ve üst yarıdaki bütün yasal durumlar özyinelemeli olarak üretilir. Her durum, rasyonel katsayıya katkısını, \(\phi\)-katsayısına katkısını ve ayrım çizgisindeki bit bilgisini saklar.
Üst yarı durumları daha sonra \(\phi\)-katsayısı ve sınır biti ile indekslenen arama tablolarına dönüştürülür. Her girişte rasyonel katsayılar sıralanır ve önek toplamlarla desteklenir. Alt yarı yalnızca irrasyonel kısmı sıfırlayabilecek girişleri sorgular, uygun aralık için iki ikili arama yapar ve o blok katkısını toplam cevaba ekler.
Uzunluk \(n\) için her yarı yalnızca ardışık \(1\) içermeyen yasal ikili dizileri üretir; bu nedenle durum sayısı Fibonacci benzeri büyür. Yine de kullanışlı bir üst sınır
$$O\!\left(2^{n/2}\log 2^{n/2}\right)$$
şeklindedir; çünkü bölmeden sonra baskın maliyet sıralama ve ikili aramadır. Pratikte ardışık \(1\) yasağı, gerçek durum sayısını \(2^{n/2}\)'den belirgin biçimde küçültür.
Bellek kullanımı, o uzunluk için saklanan üst-yarı durum sayısı ile lineerdir. İncelenen uzunluklar sabit güvenli bir üst sınıra kadar gittiği için yöntem \(L=10^{10}\) için rahatça uygulanabilir; tam dizileri doğrudan üretmek ise pratik değildir.
Sea \(\phi=\dfrac{1+\sqrt5}{2}\). El problema pide la suma de todos los enteros positivos no mayores que \(L\) cuya representación canónica en base \(\phi\) es palindrómica alrededor del punto radix. La implementación usa las reglas estándar de la numeración phinary: cada dígito es \(0\) o \(1\), y dos dígitos adyacentes no pueden ser ambos \(1\).
Si la mitad izquierda del palíndromo es \(d_{n-1}\dots d_1d_0\), entonces la representación completa en base \(\phi\) es \(d_{n-1}\dots d_1d_0.d_0d_1\dots d_{n-1}\). El dígito más alto debe ser \(1\), y el par central obliga a \(d_0=0\), porque los dos dígitos junto al punto radix son iguales y por tanto no pueden ser simultáneamente \(1\).
El límite real es \(L=10^{10}\). El punto de control incorporado es
$$\sum_{\substack{x\le 1000\\ x\text{ phigital}}} x = 4345,$$
valor que las implementaciones en C++, Python y Java utilizan como verificación básica.
La observación clave es que una cadena palindrómica en base \(\phi\) puede reescribirse como una suma de potencias emparejadas \(\phi^i+\phi^{-i-1}\). Así el problema deja de ser una búsqueda ingenua sobre cadenas de dígitos y se convierte en una búsqueda meet-in-the-middle sobre combinaciones lineales enteras.
Para dígitos \(d_i\in\{0,1\}\), definimos
$$w_i=\phi^i+\phi^{-i-1}.$$
Entonces toda representación palindrómica de la forma descrita vale
$$x=\sum_{i=0}^{n-1} d_i w_i.$$
Las condiciones de validez pasan a ser puramente combinatorias:
$$d_{n-1}=1,\qquad d_0=0,\qquad d_i d_{i+1}=0 \text{ para } 0\le i\lt n-1.$$
Por tanto, el espacio de búsqueda no son todas las cadenas binarias, sino exactamente las cadenas legales sin unos consecutivos y con dígitos de borde fijados.
Sea \(F_0=0\), \(F_1=1\). Para \(k\ge 1\),
$$\phi^k = F_k\phi + F_{k-1}.$$
Para exponentes negativos,
$$\phi^{-m}=(-1)^m\left(F_{m+1}-F_m\phi\right).$$
De este modo, cada peso emparejado se puede escribir como
$$w_i=u_i+v_i\phi,$$
donde \(u_i\) y \(v_i\) son enteros precalculables. Los primeros valores son
$$w_0=\phi,\qquad w_1=2,\qquad w_2=3\phi-2,\qquad w_3=6-\phi,\qquad w_4=8\phi-5.$$
Por eso la implementación almacena, para cada posición, un coeficiente racional y otro coeficiente multiplicando a \(\phi\).
La suma de los pesos elegidos toma la forma
$$x=\sum_{i=0}^{n-1} d_i(u_i+v_i\phi)=U+V\phi,$$
con
$$U=\sum_{i=0}^{n-1} d_i u_i,\qquad V=\sum_{i=0}^{n-1} d_i v_i.$$
Como \(1\) y \(\phi\) son linealmente independientes sobre \(\mathbb{Q}\), el valor \(x\) es un entero si y solo si
$$V=0.$$
Cuando eso ocurre, el entero buscado es simplemente
$$x=U.$$
Así, el problema se reduce a encontrar todas las cadenas legales para las que desaparece el coeficiente irracional y el coeficiente entero restante satisface
$$1\le U\le L.$$
Para una longitud fija \(n\), las posiciones se parten en un punto medio. La mitad baja aporta un par \((U_{\ell},V_{\ell})\) y recuerda su último dígito en la frontera. La mitad alta aporta \((U_h,V_h)\) y recuerda su primer dígito en la misma frontera.
Una combinación es válida exactamente cuando se cumplen tres condiciones:
$$V_{\ell}+V_h=0,$$
$$1\le U_{\ell}+U_h\le L,$$
y los dos dígitos fronterizos no son ambos \(1\).
Eso transforma una búsqueda global en dos enumeraciones más pequeñas más un paso de fusión estructurada.
Todos los estados de la mitad alta se agrupan por su valor \(V_h\) y por su bit de frontera inicial. Dentro de cada grupo, los valores \(U_h\) se ordenan y se acompañan con sumas prefijas.
Para un estado fijo de la mitad baja, solo pueden cancelar la parte con \(\phi\) los grupos con
$$V_h=-V_{\ell}.$$
La condición de rango se convierte en
$$1-U_{\ell}\le U_h\le L-U_{\ell}.$$
Dos búsquedas binarias localizan el intervalo admisible. Si ese intervalo contiene \(c\) estados y la suma de sus \(U_h\) es \(S\), entonces la contribución total de ese estado bajo es
$$c\,U_{\ell}+S.$$
Así se acumula directamente la suma de todos los enteros válidos sin recorrer uno a uno todos los emparejamientos compatibles.
El palíndromo legal
$$100100.001001_{\phi}$$
usa las posiciones \(5\) y \(2\), por lo que
$$x=w_5+w_2=(13-3\phi)+(3\phi-2)=11.$$
Los términos con \(\phi\) se cancelan exactamente y queda el entero \(11\). Ese es el fenómeno básico que el algoritmo busca a gran escala. El caso especial \(x=1\) se maneja por separado al principio, porque es un phigital de un solo dígito y no entra en el bucle de longitudes emparejadas.
La implementación precalcula primero los números de Fibonacci y, a partir de ellos, los coeficientes emparejados \((u_i,v_i)\) para todas las posiciones relevantes bajo el límite dado. Después inicializa inmediatamente el total con \(1\), cubriendo así el phigital aislado \(1\).
Para cada longitud candidata, la implementación calcula el valor mínimo y máximo que puede tomar el coeficiente entero \(U\) bajo las reglas de los dígitos. Si ese intervalo no intersecta \([1,L]\), toda esa longitud se descarta antes de empezar la parte meet-in-the-middle.
Si la longitud puede contribuir, se enumeran recursivamente todos los estados legales de la mitad baja y de la mitad alta. Cada estado registra su aportación al coeficiente racional, su aportación al coeficiente de \(\phi\) y el bit de frontera necesario para imponer la restricción de no tener unos adyacentes a través del corte.
Los estados de la mitad alta se reorganizan en tablas de consulta indexadas por el coeficiente de \(\phi\) y por el bit de frontera. Dentro de cada entrada, los coeficientes racionales se ordenan y se acompañan con sumas prefijas. La enumeración de la mitad baja consulta solo las entradas capaces de cancelar la parte irracional, hace dos búsquedas binarias para el intervalo permitido y añade la contribución en bloque al total.
Para una longitud \(n\), cada mitad enumera únicamente cadenas binarias legales sin unos consecutivos, así que el número de estados crece de manera tipo Fibonacci. Como cota superior cómoda puede escribirse
$$O\!\left(2^{n/2}\log 2^{n/2}\right),$$
porque tras la partición dominan la ordenación y las búsquedas binarias. En la práctica, la restricción de no adyacencia reduce el número real de estados por debajo de \(2^{n/2}\).
El uso de memoria es lineal en el número de estados de la mitad alta almacenados para la longitud actual. Como solo se exploran longitudes hasta un tope seguro fijo, el método es perfectamente viable para \(L=10^{10}\), mientras que una enumeración directa de todas las cadenas completas sería inviable.
设 \(\phi=\dfrac{1+\sqrt5}{2}\)。本题要求把所有不超过 \(L\) 的正整数中，凡是其规范 base-\(\phi\) 表示在小数点两侧呈回文结构的数全部求和。实现采用标准 phinary 规则：每一位只能是 \(0\) 或 \(1\)，并且任意两个相邻位置不能同时为 \(1\)。
如果回文左半部分写成 \(d_{n-1}\dots d_1d_0\)，那么完整表示就是 base \(\phi\) 下的 \(d_{n-1}\dots d_1d_0.d_0d_1\dots d_{n-1}\)。最高位必须是 \(1\)；同时由于小数点两侧最靠近中心的两位相等，而规范表示又禁止相邻两个 \(1\)，因此必然有 \(d_0=0\)。
实际限制是 \(L=10^{10}\)。程序中的校验点为
$$\sum_{\substack{x\le 1000\\ x\text{ phigital}}} x = 4345,$$
这一数值被 C++、Python 和 Java 实现共同用作基本正确性检查。
核心观察是：围绕小数点对称的 base-\(\phi\) 回文串，可以改写成若干对幂 \(\phi^i+\phi^{-i-1}\) 的和。这样问题就从“枚举整串数字”转化为“枚举一组整数线性组合并在中间汇合”的问题。
对每个 \(d_i\in\{0,1\}\)，定义
$$w_i=\phi^i+\phi^{-i-1}.$$
则任何上述形式的回文表示，其数值都可写为
$$x=\sum_{i=0}^{n-1} d_i w_i.$$
合法性条件因此变成纯粹的组合约束：
$$d_{n-1}=1,\qquad d_0=0,\qquad d_i d_{i+1}=0 \text{ 对所有 } 0\le i\lt n-1.$$
也就是说，搜索空间并不是所有二进制串，而是“边界位固定且没有相邻两个 \(1\)”的合法串。
设 \(F_0=0\)、\(F_1=1\)。对 \(k\ge 1\) 有
$$\phi^k = F_k\phi + F_{k-1}.$$
对负幂则有
$$\phi^{-m}=(-1)^m\left(F_{m+1}-F_m\phi\right).$$
因此每个成对权重都能写成
$$w_i=u_i+v_i\phi,$$
其中 \(u_i,v_i\) 都是整数，可以一次性预计算。前几个权重是
$$w_0=\phi,\qquad w_1=2,\qquad w_2=3\phi-2,\qquad w_3=6-\phi,\qquad w_4=8\phi-5.$$
这正是实现中为每个位置同时维护“整数部分系数”和“\(\phi\) 部分系数”的原因。
把选中的权重相加，可得
$$x=\sum_{i=0}^{n-1} d_i(u_i+v_i\phi)=U+V\phi,$$
其中
$$U=\sum_{i=0}^{n-1} d_i u_i,\qquad V=\sum_{i=0}^{n-1} d_i v_i.$$
由于 \(1\) 与 \(\phi\) 在 \(\mathbb{Q}\) 上线性无关，所以 \(x\) 是整数当且仅当
$$V=0.$$
一旦该条件成立，真实的整数值就直接等于
$$x=U.$$
于是问题被化简为：找出所有合法数字串，使得无理部分系数消失，并且剩下的整数部分满足
$$1\le U\le L.$$
对固定长度 \(n\)，将位置在中点处分成两部分。低位半段贡献一对 \((U_{\ell},V_{\ell})\)，并记录靠近切分点的最后一位；高位半段贡献 \((U_h,V_h)\)，并记录靠近切分点的第一位。
两个半段可以合并，当且仅当满足以下三个条件：
$$V_{\ell}+V_h=0,$$
$$1\le U_{\ell}+U_h\le L,$$
并且切分点两侧的边界位不能同时为 \(1\)。
这样，全局搜索就被拆成了两个较小的枚举问题，加上一个结构化的合并步骤。
所有高位半段状态按照 \(V_h\) 的取值以及其边界首位分组。每个分组内部，把所有 \(U_h\) 排序，并建立前缀和。
对某个固定的低位状态来说，只有满足
$$V_h=-V_{\ell}$$
的分组才可能抵消无理项。与此同时，取值范围限制可写成
$$1-U_{\ell}\le U_h\le L-U_{\ell}.$$
在排序后的列表中做两次二分查找，就能定位全部可行的 \(U_h\)。如果这个区间里共有 \(c\) 个状态，而这些状态的 \(U_h\) 之和为 \(S\)，那么该低位状态对答案的总贡献就是
$$c\,U_{\ell}+S.$$
这样就能一次性累计整批匹配结果，而不必把所有匹配对逐个展开。
合法回文
$$100100.001001_{\phi}$$
对应的位置是 \(5\) 和 \(2\)，因此
$$x=w_5+w_2=(13-3\phi)+(3\phi-2)=11.$$
\(\phi\) 项恰好完全抵消，最后得到整数 \(11\)。这正是算法在大规模搜索时要捕捉的核心现象。特殊值 \(x=1\) 在程序开始时单独加入，因为它是单个数字构成的 phigital 数，不属于成对长度的主循环。
实现首先预计算 Fibonacci 数，再据此为所有可能相关的位置生成配对系数 \((u_i,v_i)\)。随后答案会先初始化为 \(1\)，用来覆盖独立的 phigital 数 \(1\)。
对于每一个候选长度，程序先在“满足数字规则”的前提下计算整数系数 \(U\) 可能取得的最小值和最大值。如果这个区间与 \([1,L]\) 没有交集，那么该长度不可能产生任何有效整数，可以直接跳过。
若该长度仍有可能贡献答案，程序就分别递归枚举低位半段和高位半段的所有合法状态。每个状态都保存三个信息：它对整数系数的贡献、它对 \(\phi\) 系数的贡献，以及跨越切分点时需要检查的边界位。
高位半段状态随后被整理成查询结构，键为 \(\phi\) 系数和边界位；每个键下面的整数系数列表都经过排序并附带前缀和。低位半段只去查询那些能把无理项抵消掉的桶，对允许区间做两次二分，然后把这一整块的贡献加进总和。
对长度 \(n\) 而言，每一半只会枚举没有相邻两个 \(1\) 的合法二进制串，因此状态数呈 Fibonacci 型增长。写成方便的上界，可以记为
$$O\!\left(2^{n/2}\log 2^{n/2}\right),$$
因为切分之后主导成本是排序和二分搜索。实际运行时，由于相邻 \(1\) 被禁止，状态数会明显小于 \(2^{n/2}\)。
内存使用量与当前长度下需要保存的高位半段状态数线性相关。由于只需要考察到一个固定且安全的最大长度，所以在 \(L=10^{10}\) 的范围内该方法完全可行，而直接枚举整串数字则几乎不可能。
Пусть \(\phi=\dfrac{1+\sqrt5}{2}\). Требуется найти сумму всех положительных целых чисел, не превосходящих \(L\), чья каноническая запись в системе счисления по основанию \(\phi\) является палиндромом относительно radix-точки. Реализация использует стандартные правила phinary-записи: каждая цифра равна \(0\) или \(1\), и две соседние цифры не могут одновременно быть \(1\).
Если левая половина палиндрома равна \(d_{n-1}\dots d_1d_0\), то полная запись в базе \(\phi\) имеет вид \(d_{n-1}\dots d_1d_0.d_0d_1\dots d_{n-1}\). Старшая цифра обязана быть \(1\), а центральная пара принуждает \(d_0=0\), потому что две цифры по обе стороны от radix-точки совпадают и потому не могут обе быть \(1\).
Настоящее ограничение равно \(L=10^{10}\). Встроенная контрольная сумма такова:
$$\sum_{\substack{x\le 1000\\ x\text{ phigital}}} x = 4345,$$
и именно это значение используют реализации на C++, Python и Java как базовую проверку.
Главное наблюдение состоит в том, что палиндромическая строка в базе \(\phi\) переписывается как сумма парных степеней \(\phi^i+\phi^{-i-1}\). После этого задача превращается из грубого перебора строк в meet-in-the-middle поиск по целочисленным линейным комбинациям.
Для цифр \(d_i\in\{0,1\}\) введём
$$w_i=\phi^i+\phi^{-i-1}.$$
Тогда любая палиндромическая запись описанного вида имеет значение
$$x=\sum_{i=0}^{n-1} d_i w_i.$$
Условия допустимости становятся чисто комбинаторными:
$$d_{n-1}=1,\qquad d_0=0,\qquad d_i d_{i+1}=0 \text{ для } 0\le i\lt n-1.$$
Итак, пространство поиска состоит не из всех двоичных строк, а только из легальных строк без соседних единиц и с фиксированными крайними условиями.
Пусть \(F_0=0\), \(F_1=1\). Для \(k\ge 1\) верно
$$\phi^k = F_k\phi + F_{k-1}.$$
Для отрицательных степеней используется формула
$$\phi^{-m}=(-1)^m\left(F_{m+1}-F_m\phi\right).$$
Следовательно, любой парный вес можно записать как
$$w_i=u_i+v_i\phi,$$
где \(u_i\) и \(v_i\) являются целыми коэффициентами, вычисляемыми заранее. Первые значения таковы:
$$w_0=\phi,\qquad w_1=2,\qquad w_2=3\phi-2,\qquad w_3=6-\phi,\qquad w_4=8\phi-5.$$
Именно поэтому реализация хранит для каждой позиции один коэффициент рациональной части и один коэффициент при \(\phi\).
Сумма выбранных весов имеет вид
$$x=\sum_{i=0}^{n-1} d_i(u_i+v_i\phi)=U+V\phi,$$
где
$$U=\sum_{i=0}^{n-1} d_i u_i,\qquad V=\sum_{i=0}^{n-1} d_i v_i.$$
Так как \(1\) и \(\phi\) линейно независимы над \(\mathbb{Q}\), число \(x\) является целым тогда и только тогда, когда
$$V=0.$$
В этом случае само целое число равно
$$x=U.$$
Значит, задача сводится к поиску всех легальных наборов цифр, для которых иррациональный коэффициент зануляется, а оставшийся целый коэффициент удовлетворяет условию
$$1\le U\le L.$$
Для фиксированной длины \(n\) позиции делятся по середине. Нижняя половина даёт пару \((U_{\ell},V_{\ell})\) и запоминает последний бит у разреза. Верхняя половина даёт \((U_h,V_h)\) и запоминает первый бит у того же разреза.
Склейка допустима тогда и только тогда, когда выполняются три условия:
$$V_{\ell}+V_h=0,$$
$$1\le U_{\ell}+U_h\le L,$$
и граничные биты по обе стороны разреза не равны одновременно \(1\).
Тем самым глобальный перебор заменяется двумя меньшими перечислениями и структурированным этапом слияния.
Все состояния верхней половины группируются по значению \(V_h\) и по первому граничному биту. Внутри каждой группы значения \(U_h\) сортируются, а для них строятся префиксные суммы.
Для фиксированного состояния нижней половины только группы с
$$V_h=-V_{\ell}$$
могут сократить иррациональную часть. Ограничение по диапазону принимает вид
$$1-U_{\ell}\le U_h\le L-U_{\ell}.$$
Два двоичных поиска находят допустимый интервал. Если в нём содержится \(c\) состояний, а сумма их значений \(U_h\) равна \(S\), то общий вклад данного нижнего состояния равен
$$c\,U_{\ell}+S.$$
Так суммируются сразу все подходящие пары, без явного перебора каждой совместимой склейки.
Легальный палиндром
$$100100.001001_{\phi}$$
использует позиции \(5\) и \(2\), поэтому
$$x=w_5+w_2=(13-3\phi)+(3\phi-2)=11.$$
Слагаемые с \(\phi\) сокращаются в точности, и остаётся целое число \(11\). Именно такое сокращение алгоритм и ищет в большом масштабе. Особый случай \(x=1\) добавляется отдельно в самом начале, потому что это однозначное phigital-число не входит в цикл по парным длинам.
Сначала реализация предвычисляет числа Фибоначчи и на их основе строит пары коэффициентов \((u_i,v_i)\) для всех позиций, которые могут понадобиться при данном ограничении. Затем ответ немедленно инициализируется значением \(1\), чтобы учесть отдельное phigital-число \(1\).
Для каждой кандидатной длины палиндрома программа вычисляет минимально и максимально возможное значение целочисленного коэффициента \(U\) при соблюдении правил для цифр. Если этот интервал не пересекается с \([1,L]\), такую длину можно отбросить ещё до запуска meet-in-the-middle.
Если длина потенциально полезна, рекурсивно перечисляются все легальные состояния нижней и верхней половин. Каждое состояние хранит вклад в рациональную часть, вклад в коэффициент при \(\phi\) и граничный бит, нужный для проверки условия отсутствия соседних единиц через разрез.
После этого состояния верхней половины перестраиваются в структуры поиска, индексированные коэффициентом при \(\phi\) и граничным битом. Внутри каждой ячейки целочисленные коэффициенты сортируются и снабжаются префиксными суммами. Нижняя половина запрашивает только те ячейки, которые могут занулить иррациональную часть, выполняет две двоичные поисковые операции по допустимому диапазону и добавляет соответствующий блоковый вклад в итоговую сумму.
Для длины \(n\) каждая половина перечисляет только легальные двоичные строки без соседних единиц, так что число состояний растёт по Фибоначчи-подобному закону. Удобную верхнюю оценку можно записать как
$$O\!\left(2^{n/2}\log 2^{n/2}\right),$$
поскольку после разбиения доминируют сортировка и двоичные поиски. На практике запрет соседних единиц делает реальное число состояний заметно меньше \(2^{n/2}\).
Память используется линейно по числу сохранённых состояний верхней половины для текущей длины. Поскольку рассматриваются только длины до фиксированной безопасной границы, метод легко справляется с \(L=10^{10}\), тогда как прямой перебор полных строк был бы безнадёжным.
لنأخذ \(\phi=\dfrac{1+\sqrt5}{2}\). المطلوب هو مجموع جميع الأعداد الصحيحة الموجبة التي لا تتجاوز \(L\) والتي يكون تمثيلها القانوني في الأساس \(\phi\) متناظرًا حول الفاصلة radix. تعتمد الخوارزمية على قواعد التمثيل phinary القياسية: كل خانة هي \(0\) أو \(1\)، ولا يجوز أن تكون خانتان متجاورتان كلتاهما \(1\).
إذا كان النصف الأيسر من التناظر هو \(d_{n-1}\dots d_1d_0\)، فإن التمثيل الكامل في الأساس \(\phi\) هو \(d_{n-1}\dots d_1d_0.d_0d_1\dots d_{n-1}\). أعلى خانة يجب أن تكون \(1\)، كما أن الزوج المركزي يفرض \(d_0=0\)، لأن الخانتين الملاصقتين للفاصلة متساويتان وبالتالي لا يمكن أن تكونا معًا \(1\).
الحد الحقيقي هو \(L=10^{10}\). وتوجد نقطة تحقق مدمجة هي
$$\sum_{\substack{x\le 1000\\ x\text{ phigital}}} x = 4345,$$
وهي القيمة التي تستخدمها تطبيقات C++ وPython وJava كاختبار سلامة أساسي.
الفكرة الأساسية هي أن السلسلة المتناظرة في الأساس \(\phi\) يمكن إعادة كتابتها على شكل مجموع أوزان مزدوجة من الصورة \(\phi^i+\phi^{-i-1}\). وبهذا تتحول المسألة من تعداد مباشر لسلاسل الخانات إلى بحث meet-in-the-middle على تراكيب خطية صحيحة.
لكل \(d_i\in\{0,1\}\) نعرّف
$$w_i=\phi^i+\phi^{-i-1}.$$
وعندئذ تكون قيمة أي تمثيل متناظر من الشكل السابق
$$x=\sum_{i=0}^{n-1} d_i w_i.$$
تصبح شروط الصلاحية شروطًا تركيبية بحتة:
$$d_{n-1}=1,\qquad d_0=0,\qquad d_i d_{i+1}=0,\qquad 0\le i\lt n-1.$$
إذن فضاء البحث ليس كل السلاسل الثنائية، بل فقط السلاسل القانونية الخالية من \(11\) المتجاورة مع تثبيت خانات الحافة.
لنفرض \(F_0=0\) و\(F_1=1\). عند \(k\ge 1\) لدينا
$$\phi^k = F_k\phi + F_{k-1}.$$
أما للقوى السالبة فنستخدم
$$\phi^{-m}=(-1)^m\left(F_{m+1}-F_m\phi\right).$$
ومن ثم يمكن كتابة كل وزن مزدوج على الصورة
$$w_i=u_i+v_i\phi,$$
حيث \(u_i\) و\(v_i\) عددان صحيحان يمكن حسابهما مسبقًا. أول القيم هي
$$w_0=\phi,\qquad w_1=2,\qquad w_2=3\phi-2,\qquad w_3=6-\phi,\qquad w_4=8\phi-5.$$
ولهذا تحتفظ الخوارزمية لكل موضع بخانتين عدديتين: واحدة للجزء الصحيح وواحدة لمعامل \(\phi\).
مجموع الأوزان المختارة يساوي
$$x=\sum_{i=0}^{n-1} d_i(u_i+v_i\phi)=U+V\phi,$$
حيث
$$U=\sum_{i=0}^{n-1} d_i u_i,\qquad V=\sum_{i=0}^{n-1} d_i v_i.$$
وبما أن \(1\) و\(\phi\) مستقلان خطيًا فوق \(\mathbb{Q}\)، فإن \(x\) يكون عددًا صحيحًا إذا وفقط إذا
$$V=0.$$
وعند تحقق ذلك تكون القيمة الصحيحة نفسها هي
$$x=U.$$
وبذلك تختزل المسألة إلى إيجاد جميع السلاسل القانونية التي يختفي فيها المعامل اللاعقلاني، ويقع فيها المعامل الصحيح المتبقي ضمن المجال
$$1\le U\le L.$$
لطول ثابت \(n\)، تُقسم المواضع عند المنتصف. يساهم النصف السفلي بزوج \((U_{\ell},V_{\ell})\) ويحتفظ بآخر خانة قرب نقطة الفصل، بينما يساهم النصف العلوي بزوج \((U_h,V_h)\) ويحتفظ بأول خانة عند نفس الحد.
يكون الدمج صالحًا فقط إذا تحققت الشروط الثلاثة التالية:
$$V_{\ell}+V_h=0,$$
$$1\le U_{\ell}+U_h\le L,$$
وألا تكون خانتا الحد عند نقطة الفصل كلتاهما \(1\).
وهكذا تتحول عملية البحث العالمية إلى تعدادين أصغر ثم خطوة دمج منظمة.
تُجمع كل حالات النصف العلوي بحسب قيمة \(V_h\) وبحسب خانة الحد الأولى. وداخل كل مجموعة تُرتب قيم \(U_h\) وتُبنى لها مجاميع بادئة.
بالنسبة إلى حالة سفلى ثابتة، لا يمكن حذف الجزء اللاعقلاني إلا مع المجموعات التي تحقق
$$V_h=-V_{\ell}.$$
ويصبح شرط المجال
$$1-U_{\ell}\le U_h\le L-U_{\ell}.$$
بحثان ثنائيان يحددان المقطع المسموح داخل القائمة المرتبة. فإذا احتوى هذا المقطع على \(c\) حالات، وكان مجموع قيم \(U_h\) فيها هو \(S\)، فإن المساهمة الكلية لهذه الحالة السفلى تساوي
$$c\,U_{\ell}+S.$$
وبذلك يمكن جمع جميع القيم الصحيحة الناتجة دفعة واحدة من دون المرور على كل زوج متوافق بشكل منفصل.
التمثيل المتناظر القانوني
$$100100.001001_{\phi}$$
يستخدم الموضعين \(5\) و\(2\)، ولذلك
$$x=w_5+w_2=(13-3\phi)+(3\phi-2)=11.$$
تلغى حدود \(\phi\) بعضها بعضًا بدقة، وتبقى القيمة الصحيحة \(11\). هذه هي الظاهرة الأساسية التي تبحث عنها الخوارزمية على نطاق واسع. أما الحالة الخاصة \(x=1\) فتُضاف منذ البداية بشكل منفصل، لأنها عدد phigital من خانة واحدة ولا تدخل في حلقة الأطوال المزدوجة.
تبدأ التطبيقات بحساب أعداد فيبوناتشي مسبقًا، ثم تستخرج منها الأزواج \((u_i,v_i)\) لكل المواضع التي قد تكون مؤثرة تحت الحد المعطى. بعد ذلك يُهيَّأ الجواب مباشرة بالقيمة \(1\) لاحتساب العدد phigital المنفرد \(1\).
لكل طول مرشح، يحسب التنفيذ أصغر وأكبر قيمة ممكنة للمعامل الصحيح \(U\) مع الالتزام بقيود الخانات. إذا كان هذا المجال لا يقطع \([1,L]\)، فإن ذلك الطول يُستبعد بالكامل قبل بدء خطوة meet-in-the-middle.
إذا كان الطول ما يزال قادرًا على الإسهام، تُعدَّد جميع الحالات القانونية في النصف السفلي والنصف العلوي بصورة عودية. كل حالة تخزن مساهمتها في الجزء الصحيح، ومساهمتها في معامل \(\phi\)، وخانة الحد اللازمة للتحقق من شرط منع التجاور عبر نقطة الفصل.
بعد ذلك تُعاد هيكلة حالات النصف العلوي في جداول بحث مفهرسة بمعامل \(\phi\) وبالبت الحدودي. وداخل كل خانة من الجدول تُرتب معاملات الجزء الصحيح وتُدعم بمجاميع بادئة. ثم يفحص تعداد النصف السفلي فقط المداخل القادرة على إلغاء الجزء اللاعقلاني، ويجري بحثين ثنائيين على المجال المسموح، ثم يضيف مساهمة الكتلة الناتجة إلى المجموع الكلي.
لطول \(n\)، كل نصف لا يعدد إلا السلاسل الثنائية القانونية الخالية من الواحدات المتجاورة، لذلك ينمو عدد الحالات بنمط شبيه بفibonacci. ويمكن إعطاء حد أعلى مريح بالشكل
$$O\!\left(2^{n/2}\log 2^{n/2}\right),$$
لأن الفرز والبحث الثنائي يصبحان التكلفة الغالبة بعد التقسيم. وعمليًا يكون عدد الحالات الحقيقي أصغر بوضوح من \(2^{n/2}\) بسبب منع \(11\) المتجاورة.
استهلاك الذاكرة خطي في عدد حالات النصف العلوي المخزنة للطول الحالي. وبما أن التنفيذ لا يستكشف إلا أطوالًا حتى حد آمن ثابت، فإن هذه الطريقة مناسبة تمامًا عندما يكون \(L=10^{10}\)، في حين أن التعداد المباشر لكل السلاسل الكاملة غير عملي.