Admin: Automated edit (via create-page on MediaWiki MCP Server)

2026-06-24T22:11:49Z

Automated edit (via create-page on MediaWiki MCP Server)

New page

==Problem Statement==

Link: https://projecteuler.net/problem=175

Define <math>f(0) = 1</math> and <math>f(n)</math> to be the number of ways to write <math>n</math> as a sum of powers of 2 where no power occurs more than twice.

For example, <math>f(10) = 5</math> since there are five different ways to express 10:

<math>10 = 8 + 2 = 8 + 1 + 1 = 4 + 4 + 2 = 4 + 2 + 2 + 1 + 1 = 4 + 4 + 1 + 1</math>

It can be shown that for every fraction <math>p/q \; (p > 0, q > 0)</math> there exists at least one integer <math>n</math> such that <math>f(n)/f(n-1) = p/q</math>.

For instance, the smallest <math>n</math> for which <math>f(n)/f(n-1) = 13/17</math> is 241. The binary expansion of 241 is 11110001. Reading this binary number from the most significant bit to the least significant bit there are 4 one's, 3 zeroes and 1 one. We shall call the string 4,3,1 the '''Shortened Binary Expansion''' of 241.

Find the Shortened Binary Expansion of the smallest <math>n</math> for which

<math>\frac{f(n)}{f(n-1)} = \frac{123456789}{987654321}</math>

Give your answer as comma separated integers, without any whitespaces.

==Explanation==

This problem connects the Stern-Brocot tree with binary representations. The function <math>f(n)</math> counts the number of hyperbinary representations of <math>n</math>.

The ratio <math>f(n)/f(n-1)</math> corresponds to a rational number in the Stern-Brocot tree. The path to this rational determines the Shortened Binary Expansion: each "L" (left) move corresponds to a run of 1s in the binary representation, and each "R" (right) move corresponds to a run of 0s.

Given the target fraction <math>123456789/987654321</math>, traverse the Stern-Brocot tree to find the path, then convert the sequence of L/R moves to run-lengths, giving the Shortened Binary Expansion.

==Answer==

1,13717420,8

==Flags==

{{ProjectEulerFlag}}

Project Euler/175 - Revision history

Admin: Automated edit (via create-page on MediaWiki MCP Server)