Project Euler

Powers of Two

Find p(123,678910), the 678910 -th smallest exponent j such that the decimal expansion of 2^j begins with the digits 123.

Source sync Apr 19, 2026

Problem #0686

Level Level 07

Solved By 4,181

Languages C++, Python

Answer 193060223

Length 157 words

modular_arithmeticsearch

$2^7=128$ is the first power of two whose leading digits are "12".

The next power of two whose leading digits are "12" is $2^{80}$.

Define $p(L, n)$ to be the $n$th-smallest value of $j$ such that the base 10 representation of $2^j$ begins with the digits of $L$.

So $p(12, 1) = 7$ and $p(12, 2) = 80$.

You are also given that $p(123, 45) = 12710$.

Find $p(123, 678910)$.

Problem 686: Powers of Two

Mathematical Foundation

Let $\alpha = \log_{10} 2$ .

Lemma 1. The number $2^j$ begins with the digits 123 if and only if

\log_{10}(1.23) \le \{j\alpha\} < \log_{10}(1.24),

where $\{x\}$ denotes the fractional part of $x$ .

Proof. The leading digits of $2^j$ are 123 exactly when there exists an integer $m$ such that

123 \cdot 10^m \le 2^j < 124 \cdot 10^m.

Taking base- $10$ logarithms gives

\log_{10}(123) + m \le j\alpha < \log_{10}(124) + m.

Subtracting $2+m$ throughout yields

\log_{10}(1.23) \le \{j\alpha\} < \log_{10}(1.24).

Conversely, that fractional-part condition implies the existence of such an $m$ , hence the same leading digits. $\square$

Theorem. Scanning the exponents $j=1,2,3,\dots$ and counting those satisfying the interval test from Lemma 1 yields $p(123,678910)$ .

Proof. By Lemma 1, the interval test is equivalent to the defining property. Therefore the $678910$ -th hit in this scan is exactly the desired exponent. $\square$

Editorial

This is exactly what the existing Python and C++ implementations do. We precompute. We then iterate over $j=1,2,3,\dots$ . Finally, stop at the $678910$ -th hit.

Pseudocode

Precompute
$\alpha = \log_{10} 2$,
$L = \log_{10}(1.23)$,
$U = \log_{10}(1.24)$
For $j=1,2,3,\dots$:
compute $\{j\alpha\}$,
if $L \le \{j\alpha\} < U$, increment the hit counter
Stop at the $678910$-th hit

Complexity Analysis

Time: $O(p(123,678910))$ , with constant work per exponent.
Space: $O(1)$ .

Answer

\boxed{193060223}

C++ project_euler/problem_686/solution.cpp

#include <bits/stdc++.h>
using namespace std;

/*
 * Project Euler Problem 686: Powers of Two
 *
 * Find p(123, 678910): the 678910th smallest j such that 2^j starts with "123".
 *
 * Key insight: 2^j starts with digits L if and only if
 *   log10(L) <= frac(j * log10(2)) < log10(L+1)
 * where frac(x) is the fractional part of x.
 *
 * We iterate j from 0, check the fractional part condition, and count.
 */

int main() {
    const int target = 678910;
    const double log10_2 = log10(2.0);
    const double lo = log10(1.23);  // log10(123) - 2 = log10(1.23)
    const double hi = log10(1.24);  // log10(124) - 2 = log10(1.24)

    int count = 0;
    long long j = 0;

    while (count < target) {
        j++;
        double frac = j * log10_2;
        frac -= floor(frac);
        if (frac >= lo && frac < hi) {
            count++;
        }
    }

    cout << j << endl;
    return 0;
}

Python project_euler/problem_686/solution.py

"""
Project Euler Problem 686: Powers of Two

Find p(123, 678910): the 678910th smallest j such that 2^j starts with "123".

Key insight: 2^j starts with digits L iff
  log10(L) <= frac(j * log10(2)) < log10(L+1)
where frac(x) is the fractional part of x.

We use the three known gaps between consecutive solutions to speed up the search.
The gaps between consecutive j values where 2^j starts with "123" cycle through
approximately three values: 196, 289, 485.
"""

import math

def solve():
    log10_2 = math.log10(2)
    lo = math.log10(1.23)
    hi = math.log10(1.24)

    target = 678910
    count = 0
    j = 0

    while count < target:
        j += 1
        frac = (j * log10_2) % 1.0
        if lo <= frac < hi:
            count += 1

    print(j)

if __name__ == "__main__":
    solve()