Problem 175: Fractions Involving the Number of Different Ways a Number Can Be Expressed as a Sum of Powers of 2

Project Euler Problem 175 Solution

EulerSolve provides an optimized solution for Project Euler Problem 175, Fractions Involving the Number of Different Ways a Number Can Be Expressed as a Sum of Powers of 2, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary 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. Mathematical Approach 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. Hyperbinary Representations and the Basic Recurrence 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....

Detailed mathematical approach

Problem Summary

Let $f(0)=1$, and for $n\ge1$ let $f(n)$ be the number of ways to write $n$ as a sum of powers of $2$ in which no power occurs more than twice; as the example shows, the order of the parts does not matter. Thus $f(10)=5$, since $10$ can be written as $8+2$, $8+1+1$, $4+4+2$, $4+4+1+1$ and $4+2+2+1+1$. The statement notes that every fraction $p/q$ with $p,q\gt0$ equals $f(n)/f(n-1)$ for at least one integer $n$, and that the smallest such $n$ for $13/17$ is $241=11110001_2$. Read from the most significant digit, its binary digits form blocks of $4$ ones, $3$ zeros and $1$ one, and the block lengths $4,3,1$ are its Shortened Binary Expansion. We must find the Shortened Binary Expansion of the smallest $n$ with

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

written as integers separated by commas, without spaces. ^[1]

The whole solution in one sentence: reading the binary digits of $n$ from the left builds the pair $(f(n),f(n-1))$ out of $(1,0)$ by simple additions, and Euclid's algorithm on the reduced fraction undoes them, one whole block of equal digits per division, its quotients being the block lengths.

Mathematical Approach

We turn the definition into a rule along the binary digits of $n$, show that it runs backwards from every fraction in exactly one way, and then speed up the backward run.

1. Small values by hand

The number $4$ can be written as $4$, $2+2$ or $2+1+1$, so $f(4)=3$; for $5$ there are $4+1$ and $2+2+1$, so $f(5)=2$; for $6$ there are $4+2$, $4+1+1$ and $2+2+1+1$, so $f(6)=3$. Listing all representations of $n=0,1,\dots,10$ in this way gives

$$f(0),f(1),\dots,f(10)=1,1,2,1,3,2,3,1,4,3,5.$$

The values go up and down, and odd numbers repeat earlier values: $f(5)=f(2)$, $f(7)=f(3)=f(1)$ and $f(9)=f(4)$.

2. Splitting off the ones

Look at the part $1$, the only odd power of $2$. If $n=2m+1$ is odd, the part $1$ occurs exactly once, because all other parts are even and $1$ may occur at most twice. Removing it and halving the other parts matches the representations of $2m+1$ one-to-one with those of $m$; doubling the parts and adding a $1$ undoes it. If $n=2m$ with $m\ge1$, the part $1$ occurs zero or two times; halving all parts maps the first kind to the representations of $m$, and removing both ones and halving the rest maps the second kind to those of $m-1$. Hence

$$f(2m+1)=f(m),\qquad f(2m)=f(m)+f(m-1).$$

For example $f(10)=f(5)+f(4)=2+3=5$. With the convention $f(-1)=0$ both rules hold for every $m\ge0$, since $f(1)=f(0)$ and $f(0)=f(0)+f(-1)$. They are the rules of Stern's diatomic sequence: $f(n)$ is its term $a(n+1)$ in the numbering of the OEIS, where $a(0)=0$ matches $f(-1)=0$. ^[2]

3. A pair that follows the binary digits

Put $P(n)=(f(n),f(n-1))$ for $n\ge0$; then $P(0)=(1,0)$. If $P(m)=(a,b)$, the rules of Section 2, together with $f(2m-1)=f(m-1)$, give

$$P(2m)=(a+b,\;b),\qquad P(2m+1)=(a,\;a+b).$$

Appending the digit $0$ to the binary expansion of $m$ gives $2m$, and appending $1$ gives $2m+1$. So we can start from $(1,0)$ and read the binary digits of $n$ from the left: a $0$ adds the second number to the first, a $1$ adds the first number to the second. For $n=241=11110001_2$:

$$\begin{aligned}(1,0)&\to(1,1)\to(1,2)\to(1,3)\to(1,4)\\&\to(5,4)\to(9,4)\to(13,4)\to(13,17).\end{aligned}$$

So $f(241)=13$ and $f(240)=17$, and the ratio is $13/17$, as the statement says. For the ratio $r(n)=f(n)/f(n-1)$, the two rules send a fraction $x=a/b$ to $x+1=(a+b)/b$ and to $x/(x+1)=a/(a+b)$, the two children of $x$ in the Calkin–Wilf tree. ^[3] The indices $n$ with the same number of binary digits give one level of that tree, in mirror order:

$n=1$: $1$;
$n=2,3$: $2$, $1/2$;
$n=4,\dots,7$: $3$, $2/3$, $3/2$, $1/3$;
$n=8,\dots,15$: $4$, $3/4$, $5/3$, $2/5$, $5/2$, $3/5$, $4/3$, $1/4$.

4. Blocks of equal digits

Inside a block of equal digits the same number is added again and again, since that number does not change. A block of $k$ zeros therefore turns $(a,b)$ into $(a+kb,b)$, and a block of $k$ ones turns it into $(a,b+ka)$. The binary expansion starts with a block of ones, and the blocks alternate. For $241$ the blocks $4,3,1$ give $(1,0)\to(1,4)\to(13,4)\to(13,17)$, the same result in three steps instead of eight. The Shortened Binary Expansion of $n$ thus determines $P(n)$; the task is to go the other way.

5. Every fraction appears exactly once

Three facts make the rules reversible.

The pair is in lowest terms. Adding one number to the other keeps their greatest common divisor, as $\gcd(a+b,b)=\gcd(a,b)$, and the start $(1,0)$ has greatest common divisor $1$. So $f(n)$ and $f(n-1)$ are always coprime, and for a reduced fraction $p/q$ the equation $f(n)/f(n-1)=p/q$ means exactly $P(n)=(p,q)$.
The last digit can be seen. For $m\ge1$ both numbers of $P(m)$ are positive, so $n=2m$ gives a pair whose first number is larger, and $n=2m+1$ a pair whose first number is smaller. The only other index $n\ge1$ is $n=1$, with $P(1)=(1,1)$.
The pair before is determined. It is $(p-q,q)$ after a final $0$ and $(p,q-p)$ after a final $1$.

Now let $p,q\ge1$ be coprime and use induction on $p+q$. If $p=q$, then $p=q=1$, and $n=1$ is the only index with $P(n)=(1,1)$. If $p\gt q$, every solution is even, $n=2m$, with $P(m)=(p-q,q)$; this pair is coprime with a smaller sum, so by induction exactly one $m\ge1$ has it, and $n=2m$ is the only solution. The case $p\lt q$ is the same with $(p,q-p)$ and $n=2m+1$. So every positive fraction equals $f(n)/f(n-1)$ for exactly one $n\ge1$: the "smallest" $n$ of the statement is in fact the only one. This is the classical fact that every positive rational number appears exactly once in the Calkin–Wilf tree. ^[2] ^[3]

6. Undoing a whole block with one division

Undoing the digits one at a time subtracts the smaller number from the larger again and again: this is Euclid's algorithm in its original, subtractive form. ^[4] Euclidean division does all subtractions of the same number in one step, and here such a step removes a whole block. Let $p$ and $q$ be coprime and positive.

If $p\gt q$, the last block consists of zeros: we subtract $q$ from the first number while it is larger than $q$. The smallest $k$ with $p-kq\le q$ is $\lceil p/q\rceil-1$, so

$$k=\left\lfloor\frac{p-1}{q}\right\rfloor,\qquad p'=p-kq\in\{1,\dots,q\},$$

and the pair before the block is $(p',q)$. If $p\le q$, the last block consists of ones: we subtract $p$ from the second number while it is at least $p$, so

$$k=\left\lfloor\frac{q}{p}\right\rfloor,\qquad q'=q-kp=q\bmod p,$$

and the pair before the block is $(p,q')$. Equality is treated differently in the two cases because of $P(1)=(1,1)$: its digit is the leading $1$, and the pair before it is $(1,0)$, not $(0,1)$, which is no pair $P(n)$ at all since $f(n)\ge1$. That is why the first remainder lies in $1,\dots,q$ rather than $0,\dots,q-1$; the two differ only when $q$ divides $p$, that is, for $q=1$.

Every quotient $k$ is at least $1$. After a block of zeros the first number is at most the second, so ones come next; after a block of ones either $q'=0$, which happens only for $p=1$ and means that we have reached the start $(1,0)$, or $1\le q'\lt p$, and zeros come next. So the blocks alternate, the process stops exactly at $(1,0)$, and the quotients, in the reverse order of their discovery, are the Shortened Binary Expansion of $n$.

7. Worked example: 13/17

Start with $(13,17)$. Since $13\le17$, the last block consists of $\lfloor17/13\rfloor=1$ one, and $17\bmod13=4$ leaves $(13,4)$. Now $13\gt4$: the block before consists of $\lfloor12/4\rfloor=3$ zeros, leaving $(13-12,4)=(1,4)$. Finally $\lfloor4/1\rfloor=4$ ones lead to $(1,0)$. The blocks were found from right to left as $1,3,4$, so the Shortened Binary Expansion is $4,3,1$ and $n=11110001_2=241$, as the statement and Section 3 say.

8. Worked example: 5/3, where the adjusted remainder matters

From $(5,3)$ we remove $\lfloor4/3\rfloor=1$ zero and reach $(2,3)$; then $\lfloor3/2\rfloor=1$ one, reaching $(2,1)$; then $\lfloor1/1\rfloor=1$ zero, reaching $(1,1)$; then $1$ one, reaching $(1,0)$. The expansion is $1,1,1,1$, so $n=1010_2=10$, and indeed $f(10)/f(9)=5/3$ by Section 1. The ordinary remainder would have removed $\lfloor2/1\rfloor=2$ zeros from $(2,1)$ and reached $(0,1)$, a pair that never occurs, and a program would then divide by zero in the next step.

9. Continued fractions

The continued fraction $[a_0;a_1,\dots,a_k]$, with an integer $a_0\ge0$ and positive integers $a_1,\dots,a_k$, stands for

$$a_0+\cfrac{1}{a_1+\cfrac{1}{\ddots+\cfrac{1}{a_k}}},$$

for example $[1;1,2]=1+1/(1+1/2)=5/3$. A block of $k$ zeros that turns $(p',q)$ into $(p,q)$ means $p/q=k+p'/q$, and a block of $k$ ones that turns $(p,q')$ into $(p,q)$ means $p/q=1/(k+q'/p)$. Hence the blocks $c_1,\dots,c_L$ of $n$, from left to right, give the continued fraction of $r(n)$ read from the right: $r(n)=[c_L;c_{L-1},\dots,c_1]$ for even $n$ and $r(n)=[0;c_L,\dots,c_1]$ for odd $n$; for example $13/17=[0;1,3,4]$ and $5/3=[1;1,1,1]$. Counting the $0$, these expansions have an even number of terms, because their terms count zeros and ones alternately, from zeros to the leading ones. Every positive rational number has exactly two expansions: the one produced by Euclid's algorithm, whose last term is at least $2$ unless it is the only term, and the one in which that last term $t$ is split into $t-1,1$. ^[5] Their lengths differ by one, as in $5/3=[1;1,2]=[1;1,1,1]$. So the Shortened Binary Expansion is found by taking the expansion of $p/q$ with an even number of terms, removing its first term if that is $0$, and reversing the rest. Wikipedia gives the same rule for $q_i=f(i-1)/f(i)=1/r(i)$, with the digits exchanged; ^[3] for instance $1081=10000111001_2$ has the blocks $1,4,3,2,1$ and $r(1081)=37/53=[0;1,2,3,4,1]$.

10. The target fraction

Since $\gcd(123456789,987654321)=9$, the target ratio is $13717421/109739369$ in lowest terms, and by Section 5 the unknown $n$ is the only index with $P(n)=(13717421,109739369)$. The main computation therefore finds its blocks directly, without constructing $n$ or scanning candidate indices, since $n$ can be enormous even when $p$ and $q$ are small. Undoing one digit lowers the sum of the two numbers by the smaller of them, which is at least $1$, and the sum falls from $p+q$ to $1$, so $n$ has at most $p+q-1$ binary digits, with equality exactly when $p=1$ or $q=1$; for $1/q$, for instance, $n=2^q-1$ consists of $q$ ones.

How the Code Works

The C++ program ^[7] keeps the target $123456789$, $987654321$ as defaults in Options. parse_arguments accepts --p= and --q= followed by decimal digits, and --skip-checkpoints; an unknown argument or a zero value gives exit code $1$. The digits are converted by parse_u64_after_prefix without an overflow check, so a value above $2^{64}-1$ silently wraps around modulo $2^{64}$. Unless the checkpoints are skipped, run_checkpoints, described below, runs first, and a failed check gives exit code $2$. Then main prints the result of shortened_expansion, joined with commas by as_csv.

shortened_expansion divides $p$ and $q$ by std::gcd, so that the pair is $P(n)$ itself (Section 5); without it every pair would carry the common factor, with the same quotients. shortened_expansion_dfs carries out Section 6 recursively, with the base case q == 0, the start pair $(1,0)$. If $p\gt q$ it sets next_p = (p - 1) % q + 1, the remainder from $1,\dots,q$, recurses with next_p in place of $p$ and appends the number of zeros (p - next_p) / q; otherwise it sets next_q = q % p, recurses with next_q in place of $q$ and appends the number of ones (q - next_q) / p. The blocks go into a std::vector of u64, each one after the recursive call returns, so the leading block comes first and the list is already in left-to-right order.

Before the target is computed, run_checkpoints tests both directions on the example of the statement. build_f_values fills a table by Section 2, an odd index $i$ copying entry $\lfloor i/2\rfloor$ and an even one adding entries $i/2$ and $i/2-1$, and must give $f(10)=5$; shortened_expansion(13, 17) must return $4,3,1$. smallest_n_for_ratio(13, 17, 2000) scans $n=1,2,\dots$ for the first $n$ with $17\,f(n)=13\,f(n-1)$, comparing the ratios without fractions; it must find $241$, whose blocks, counted by shortened_binary_of, must again be $4,3,1$. The table uses the arbitrary-precision type cpp_int of Boost.Multiprecision, ^[6] although no value up to $n=2000$ exceeds the Fibonacci number $144$, first reached at $n=1364$. ^[2]

In Python, solve reduces the fixed target with gcd from math and calls its nested function expansion, which runs Section 6 as a loop while q != 0, collects the blocks in a list from right to left and reverses it once before printing. Java's expansion does the same with its own gcd loop, an ArrayList of Long values and Collections.reverse, and main joins the blocks with a StringBuilder. Neither has options or checkpoints. Every step replaces the larger number by a smaller one, so the unsigned 64-bit u64 of C++, the signed 64-bit long of Java and Python's unbounded integers hold every value exactly.

Complexity and Verification

Each loop pass, or each recursive call except the last, removes one block with one remainder and one exact division. Read from right to left, the block lengths are the quotients of the ordinary Euclidean algorithm on $p$ and $q$, except that a leading quotient $0$ is dropped and the final quotient may be split in two (Section 9), so there is at most one block more than there are divisions ($13/8$ needs $5$ divisions and has $6$ blocks). By Lamé's theorem the number of divisions is at most $5d$, where $d$ is the number of decimal digits of $\min(p,q)$, ^[4] so there are at most $5d+1$ blocks. The time is therefore $O(1+\log\min(p,q))$ operations on 64-bit numbers, and the list of blocks, with the recursion in C++, needs memory of the same order; 64-bit inputs have at most $20$ digits and hence at most $101$ blocks, so the recursion stays shallow. The C++ checkpoints add a fixed amount of work: tables of $11$ and $2001$ entries and a scan that stops after $241$ comparisons.

All three programs print the same line, and the C++ checkpoints pass. Independent checks, not part of the published solutions: an enumeration of the representations agrees with Section 2 for every $n\le300$; for $1\le n\lt2^{16}$ the pairs $P(n)$ are coprime, the $65535$ ratios are distinct, and a ratio exceeds $1$ exactly for even $n$; for all $2203$ coprime pairs with $p,q\le60$, the blocks of Section 6 match the digits found one at a time, map back to $(p,q)$ by Section 4 and, reversed and preceded by $0$ when their number is odd, form the even-length continued fraction of Section 9; for all $144$ pairs with $p,q\le12$, a direct scan for the smallest $n$ with $q\,f(n)=p\,f(n-1)$ finds the same $n$, at most $4095=2^{12}-1$, for $1/12$. Applying the printed blocks forwards from $(1,0)$ gives exactly $(13717421,109739369)$, so the printed expansion belongs to the only $n$ with the required ratio.

Footnotes and References

The references below supply the background facts; the pair rule of Section 3, the block divisions of Section 6 and the bounds are derived in this article.

Project Euler 175 — Fractions and Sum of Powers of Two. The official statement defines f with no power of 2 used more than twice, gives f(10) = 5, states that every positive fraction p/q equals f(n)/f(n − 1) for some n, defines the Shortened Binary Expansion with the example 241 for 13/17, and asks for that of the smallest n for 123456789/987654321.
OEIS A002487 — Stern's diatomic series. Here a(0) = 0, a(1) = 1, a(2n) = a(n) and a(2n + 1) = a(n) + a(n + 1); a(n + 1) counts the ways of writing n as a sum of powers of 2, each used at most twice; a(n)/a(n + 1) runs through all reduced nonnegative rationals exactly once; and the largest term between a(2ᵏ) and a(2ᵏ⁺¹) is the Fibonacci number F(k + 2).
Wikipedia — Calkin–Wilf tree. The tree, named after Neil Calkin and Herbert Wilf (2000), is rooted at 1, the children of a/b are a/(a + b) and (a + b)/b, and every positive rational appears in it exactly once. Its sequence qᵢ = fusc(i)/fusc(i + 1), here f(i − 1)/f(i), is read off as a continued fraction from the blocks of binary digits of i, starting with the ones at the least significant end: q₁₀₈₁ = [1; 2, 3, 4, 1] = 53/37.
Wikipedia — Euclidean algorithm. Euclid found quotient and remainder by repeated subtraction, and Euclidean division merges these steps into one. Lamé showed in 1844 that the algorithm never needs more steps than five times the number of decimal digits of the smaller number.
Wikipedia — Simple continued fraction. The terms of the expansion of a rational number are the successive quotients of the Euclidean algorithm, and every rational number has exactly two expansions, since [a₀; …, aₙ] = [a₀; …, aₙ − 1, 1].
Boost.Multiprecision — cpp_int. cpp_int, from boost/multiprecision/cpp_int.hpp, is an arbitrary-precision integer type.
C++ — Euler175.cpp. The linked immutable revision contains shortened_expansion_dfs, smallest_n_for_ratio and run_checkpoints; it is the implementation record for this article.

Problem 175 source code

C++

#include <boost/multiprecision/cpp_int.hpp>

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <numeric>
#include <string>
#include <vector>

namespace {

using u64 = std::uint64_t;
using BigInt = boost::multiprecision::cpp_int;

struct Options {
    u64 p = 123456789ULL;
    u64 q = 987654321ULL;
    bool run_checkpoints = true;
};

bool parse_u64_after_prefix(const std::string& arg, const std::string& prefix, u64& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }

    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }

    u64 parsed = 0;
    for (char c : tail) {
        if (c < '0' || c > '9') {
            return false;
        }
        parsed = parsed * 10ULL + static_cast<u64>(c - '0');
    }
    value = parsed;
    return true;
}

bool parse_arguments(int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);
        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        if (parse_u64_after_prefix(arg, "--p=", options.p) ||
            parse_u64_after_prefix(arg, "--q=", options.q)) {
            continue;
        }

        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }
    return options.p > 0 && options.q > 0;
}

std::vector<BigInt> build_f_values(const int limit) {
    std::vector<BigInt> f(static_cast<std::size_t>(limit + 1), 0);
    f[0] = 1;
    for (int i = 1; i <= limit; ++i) {
        if ((i & 1) == 1) {
            f[static_cast<std::size_t>(i)] = f[static_cast<std::size_t>(i / 2)];
        } else {
            f[static_cast<std::size_t>(i)] = f[static_cast<std::size_t>(i / 2)] +
                                             f[static_cast<std::size_t>(i / 2 - 1)];
        }
    }
    return f;
}

int smallest_n_for_ratio(const int p, const int q, const int search_limit) {
    const std::vector<BigInt> f = build_f_values(search_limit);
    for (int n = 1; n <= search_limit; ++n) {
        if (f[static_cast<std::size_t>(n)] * q == f[static_cast<std::size_t>(n - 1)] * p) {
            return n;
        }
    }
    return -1;
}

void shortened_expansion_dfs(const u64 p, const u64 q, std::vector<u64>& out) {
    if (q == 0) {
        return;
    }

    if (p > q) {
        const u64 next_p = (p - 1) % q + 1;
        shortened_expansion_dfs(next_p, q, out);
        out.push_back((p - next_p) / q);
    } else {
        const u64 next_q = q % p;
        shortened_expansion_dfs(p, next_q, out);
        out.push_back((q - next_q) / p);
    }
}

std::vector<u64> shortened_expansion(u64 p, u64 q) {
    const u64 g = std::gcd(p, q);
    p /= g;
    q /= g;

    std::vector<u64> out;
    shortened_expansion_dfs(p, q, out);
    return out;
}

std::vector<u64> shortened_binary_of(std::uint64_t n) {
    std::string bits;
    while (n > 0) {
        bits.push_back((n & 1ULL) != 0ULL ? '1' : '0');
        n >>= 1ULL;
    }
    std::reverse(bits.begin(), bits.end());

    std::vector<u64> out;
    if (bits.empty()) {
        return out;
    }

    u64 run = 1;
    for (std::size_t i = 1; i < bits.size(); ++i) {
        if (bits[i] == bits[i - 1]) {
            ++run;
        } else {
            out.push_back(run);
            run = 1;
        }
    }
    out.push_back(run);
    return out;
}

std::string as_csv(const std::vector<u64>& values) {
    std::string out;
    for (std::size_t i = 0; i < values.size(); ++i) {
        if (i != 0) {
            out.push_back(',');
        }
        out += std::to_string(values[i]);
    }
    return out;
}

bool run_checkpoints() {
    const std::vector<BigInt> f = build_f_values(10);
    if (f[10] != 5) {
        std::cerr << "Checkpoint failed for f(10)" << '\n';
        return false;
    }

    const std::vector<u64> expected{4, 3, 1};
    const std::vector<u64> got = shortened_expansion(13, 17);
    if (got != expected) {
        std::cerr << "Checkpoint failed for shortened expansion of 13/17" << '\n';
        return false;
    }

    const int n = smallest_n_for_ratio(13, 17, 2000);
    if (n != 241) {
        std::cerr << "Checkpoint failed for smallest n with f(n)/f(n-1)=13/17" << '\n';
        return false;
    }
    if (shortened_binary_of(static_cast<u64>(n)) != expected) {
        std::cerr << "Checkpoint failed for shortened binary expansion of 241" << '\n';
        return false;
    }

    return true;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }
    if (options.run_checkpoints && !run_checkpoints()) {
        return 2;
    }

    std::cout << as_csv(shortened_expansion(options.p, options.q)) << '\n';
    return 0;
}

Python

# Problem 175: Fractions involving the number of different ways a number can be expressed as a sum of powers of 2.
# f(n)/f(n-1) = p/q  => shortened binary expansion of n = shortened expansion of p/q

from math import gcd

def solve():
    p, q = 123456789, 987654321
    g = gcd(p, q)
    p, q = p // g, q // g

    def expansion(p, q):
        result = []
        while q != 0:
            if p > q:
                nxt = (p - 1) % q + 1
                result.append((p - nxt) // q)
                p = nxt
            else:
                nxt = q % p
                result.append((q - nxt) // p)
                q = nxt
        result.reverse()
        return result

    print(','.join(str(x) for x in expansion(p, q)))

solve()

Java

import java.util.*;

public class Euler175 {
    static List<Long> expansion(long p, long q) {
        long g = gcd(p, q);
        p /= g;
        q /= g;
        List<Long> result = new ArrayList<>();
        while (q != 0) {
            if (p > q) {
                long nxt = (p - 1) % q + 1;
                result.add((p - nxt) / q);
                p = nxt;
            } else {
                long nxt = q % p;
                result.add((q - nxt) / p);
                q = nxt;
            }
        }
        Collections.reverse(result);
        return result;
    }

    static long gcd(long a, long b) {
        while (b != 0) {
            long t = b;
            b = a % b;
            a = t;
        }
        return a;
    }

    public static void main(String[] args) {
        List<Long> r = expansion(123456789L, 987654321L);
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < r.size(); i++) {
            if (i > 0)
                sb.append(',');
            sb.append(r.get(i));
        }
        System.out.println(sb);
    }
}