Solution

Answer: 1137174208

Let

$$F(x)=\prod_{k\ge 0}(1+x^{2^k}+x^{2^{k+1}})$$

so that the coefficient of $x^n$ is exactly $f(n)$, the number of ways to write $n$ as a sum of powers of $2$ with each power used at most twice.

We seek the smallest $n$ such that

$$\frac{f(n)}{f(n-1)}=\frac{123456789}{987654321}.$$

1. Recurrence for $f(n)$

Split according to parity.

Odd arguments

If $n=2m+1$, then the $2^0$ term must appear exactly once. Removing it and dividing by $2$ gives a bijection with representations of $m$. Hence

$$f(2m+1)=f(m).$$

Even arguments

If $n=2m$, then the number of $1$'s is either $0$ or $2$.

If there are $0$ ones, divide everything by $2$: $f(m)$ possibilities.
If there are $2$ ones, remove them and divide by $2$: $f(m-1)$ possibilities.

Therefore

$$f(2m)=f(m)+f(m-1).$$

2. Ratios and binary construction

Define

$$R(n)=\frac{f(n)}{f(n-1)}.$$

Using the recurrences:

If $n=2m$

$$R(2m)=\frac{f(m)+f(m-1)}{f(m)} =1+\frac{1}{R(m)}.$$

If $n=2m+1$

$$R(2m+1)=\frac{f(m)}{f(m)+f(m-1)} =\frac{R(m)}{R(m)+1}.$$

These correspond exactly to appending binary digits:

append $0$: $x \mapsto 1+\frac1x$
append $1$: $x \mapsto \frac{x}{x+1}$

Starting from $R(1)=1$, every positive rational is reached uniquely by a path in the Stern–Brocot/Calkin–Wilf tree.

Thus, to recover the smallest $n$ from a fraction $p/q$, we work backwards:

if $p<q$, the last bit was $1$, and we replace

$$\frac pq \mapsto \frac p{q-p};$$

if $p>q$, the last bit was $0$, and we replace

$$\frac pq \mapsto \frac{p-q}q.$$

This is simply the Euclidean algorithm.

3. Apply to the given fraction

First reduce:

$$\frac{123456789}{987654321} = \frac{13717421}{109739369}.$$

Now perform the Euclidean process.

Since

$$109739369 = 8\cdot 13717421 + 1,$$

we subtract $13717421$ eight times:

$$\frac{13717421}{109739369} \to \frac{13717421}{1}.$$

This contributes eight trailing $1$-bits.

Next,

$$13717421 = 13717420\cdot 1 + 1,$$

so we subtract $1$ a total of $13717420$ times:

$$\frac{13717421}{1} \to \frac11.$$

This contributes $13717420$ trailing $0$-bits.

Finally we arrive at the root $1/1$, corresponding to the leading binary digit $1$.

Hence the binary expansion is

$$1\underbrace{00\cdots0}{13717420} \underbrace{11\cdots1}{8}.$$

Its shortened binary expansion is therefore

$$1,13717420,8.$$

4. Python implementation

from math import gcd

p = 123456789
q = 987654321

# Reduce fraction
g = gcd(p, q)
p //= g
q //= g

runs_reversed = []

while not (p == 1 and q == 1):

    if p < q:
        # We are undoing an appended '1'
        k = (q - 1) // p
        q -= k * p
        runs_reversed.append(("1", k))

    else:
        # We are undoing an appended '0'
        k = (p - 1) // q
        p -= k * q
        runs_reversed.append(("0", k))

# Reconstruct binary string
binary = "1"
for bit, count in reversed(runs_reversed):
    binary += bit * count

# Convert to shortened binary expansion
sbe = []
count = 1

for i in range(1, len(binary) + 1):
    if i < len(binary) and binary[i] == binary[i - 1]:
        count += 1
    else:
        sbe.append(count)
        count = 1

print(",".join(map(str, sbe)))

5. Code walkthrough

Reduce the target fraction first.
Work backwards using the Euclidean algorithm.
Each block of repeated subtractions corresponds to repeated identical binary digits.
Reconstruct the binary expansion from those runs.
Compress consecutive equal bits into the shortened binary expansion.

For the sample $13/17$:

$17 = 1\cdot 13 + 4$ → one trailing $1$
$13 = 3\cdot 4 + 1$ → three trailing $0$'s
$4 = 3\cdot 1 + 1$ → three trailing $1$'s

giving binary

$$11110001_2 = 241,$$

whose shortened form is

$$4,3,1,$$

exactly as stated.

6. Final verification

The Euclidean algorithm terminates at $(1,1)$, guaranteeing minimality.

The binary pattern consists of:

one leading $1$,
$13717420$ zeros,
$8$ ones,

so the shortened binary expansion is consistent and complete.

Answer: 1,13717420,8

Project Euler Problem 175