Detailed mathematical approach

Problem Summary

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.

Mathematical Approach

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.

Step 1: Encode the Palindrome with Paired Weights

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.

Step 2: Rewrite Each Weight in the Basis \(\{1,\phi\}\)

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.

Step 3: An Integer Appears Exactly When the \(\phi\)-Part Cancels

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.$

Step 4: Split the Digit Positions into Two Independent Halves

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.

Step 5: Use Sorted Buckets to Sum All Compatible Merges Quickly

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.

Worked Example

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.

How the Code Works

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.

Complexity Analysis

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.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=473
2. Golden ratio: Wikipedia — Golden ratio
3. Fibonacci number: Wikipedia — Fibonacci number
4. Zeckendorf-style non-adjacent representations: Wikipedia — Zeckendorf's theorem
5. Meet-in-the-middle: Wikipedia — Meet-in-the-middle