Project Euler Problem 473

Solution

Answer: 35856681704365

Let

$$\varphi=\frac{1+\sqrt5}{2},\qquad \varphi^2=\varphi+1.$$

Every positive integer has a unique finite representation using powers of $\varphi$ with no consecutive exponents used.

For a palindromic phigital representation, the digit string must satisfy

$$d_i=d_{-i-1}.$$

Hence every palindromic value is of the form

$$N=\sum_{i\ge0} d_i\left(\varphi^i+\varphi^{-i-1}\right).$$

Define

$$T_i=\varphi^i+\varphi^{-i-1}.$$

Using the standard identities

$$\varphi^n=\frac{L_n+F_n\sqrt5}{2},$$

(where $F_n$ and $L_n$ are Fibonacci and Lucas numbers), one finds:

$T_1=2$ is already an integer,
for $k\ge1$,

$$T_{2k}=\frac{a_k+b_k\sqrt5}{2},\qquad T_{2k+3}=\frac{c_k-b_k\sqrt5}{2},$$

so the irrational parts cancel only in the pairs

$$T_{2k}+T_{2k+3}.$$

These integer blocks are

$$14,36,94,246,644,\dots$$

and satisfy the recurrence

$$B_n=3B_{n-1}-B_{n-2},$$

with $B_1=14,\ B_2=36$.

Because the original representation forbids consecutive exponents, these blocks cannot be adjacent; in fact chosen blocks must be separated by at least two unused blocks.

Thus every palindromic phigital integer is obtained from:

optionally adding the isolated value $2$,
plus any sum of non-conflicting blocks $B_n$.

The small case ($\le1000$) gives

$$1,2,14,36,38,94,96,246,248,260,644,646,658,680,682$$

whose sum is indeed

$$4345.$$

Python implementation

LIMIT = 10**10

# Generate the integer blocks:
# 14, 36, 94, 246, ...
blocks = [14, 36]
while True:
    nxt = 3 * blocks[-1] - blocks[-2]
    if nxt > LIMIT:
        break
    blocks.append(nxt)

# Generate all valid sums of blocks.
# If block i is used, then i+1 and i+2 are forbidden.
base_sums = set()

def dfs(start, total):
    base_sums.add(total)

    for i in range(start, len(blocks)):
        dfs(i + 3, total + blocks[i])

dfs(0, 0)

# Build the final set of palindromic phigital integers.
vals = set(base_sums)

# Optional isolated value 2.
# It conflicts only with the first block (14),
# so we only combine it with sums generated from blocks[1:].
with_two = set()

def dfs_two(start, total):
    with_two.add(total)

    for i in range(start, len(blocks)):
        dfs_two(i + 3, total + blocks[i])

dfs_two(1, 2)

vals |= with_two

# The special one-digit palindrome "1"
vals.add(1)

answer = sum(v for v in vals if v <= LIMIT)

print(answer)

Code walkthrough

1. Generate the block sequence

blocks = [14, 36]
while True:
    nxt = 3 * blocks[-1] - blocks[-2]

This produces the integer cancellation blocks

$$14,36,94,246,\dots$$

which are exactly the allowed building blocks for palindromic phigital integers.

2. Recursive generation

dfs(i + 3, total + blocks[i])

Choosing block i forbids blocks i+1 and i+2, so the next allowed index is i+3.

This exactly encodes the “no consecutive exponents” rule.

3. Optional isolated value $2$

The value $2$ corresponds to the standalone term $T_1$.

It conflicts only with the first block $14$, so we generate those combinations separately.

4. Verification on the example

For numbers $\le 1000$, the generated set is:

$$1,2,14,36,38,94,96,246,248,260,644,646,658,680,682$$

whose sum is

$$4345,$$

matching the problem statement exactly.

Final verification

The search space is tiny because the block sequence grows roughly like $\varphi^2\approx2.618$, so only a few dozen blocks are needed below $10^{10}$.

The recursive generation produces all valid non-overlapping combinations exactly once.

The computed total is:

$$35856681704365$$

Answer: 35856681704365