Detailed mathematical approach

Problem Summary

For a decimal prefix \(L\), let \(p(L,n)\) denote the exponent \(j\) of the \(n\)-th power of two whose leading decimal digits are exactly \(L\). Problem 686 asks for \(p(123,678910)\).

A direct search by forming huge powers of two is unnecessary. The decisive observation is that leading digits depend only on the fractional part of a base-10 logarithm, so the whole task becomes an interval-hitting problem on \([0,1)\).

Mathematical Approach

Write

$\theta=\log_{10}2.$

For each exponent \(j\), the decimal size of \(2^j\) is governed by \(j\theta\).

Step 1: Turn the Prefix Condition into a Logarithmic Window

Assume \(L\) has \(d\) decimal digits. Saying that \(2^j\) begins with the digits \(L\) means that for some integer \(m\),

$L\cdot 10^m \le 2^j \lt (L+1)\cdot 10^m.$

Taking \(\log_{10}\) gives

$\log_{10}L + m \le j\theta \lt \log_{10}(L+1) + m.$

Because \(L\) has \(d\) digits, the relevant normalization is obtained by subtracting \(d-1\). Therefore the condition is equivalent to

$a \le \{j\theta\} \lt b,$

where

$a=\log_{10}L-(d-1), \qquad b=\log_{10}(L+1)-(d-1),$

and \(\{x\}\) denotes the fractional part of \(x\). So the leading-digit question has been reduced to testing whether \(\{j\theta\}\) lands inside one fixed half-open interval.

Step 2: View the Exponents as a Rotation Modulo 1

Define

$r_j=\{j\theta\}.$

Then

$r_{j+1}=\{r_j+\theta\}, \qquad r_0=0.$

This is just repeated rotation by the constant angle \(\theta\) on the unit interval. Each time \(r_j\) falls in \([a,b)\), the power \(2^j\) starts with \(L\). Hence \(p(L,n)\) is exactly the index of the \(n\)-th visit of this orbit to that interval.

Step 3: Why Fractional Parts Are Enough

The integer part of \(j\theta\) only tells us how many digits \(2^j\) has. The first few digits come from the mantissa \(10^{\{j\theta\}}\). In fact,

$2^j = 10^{\lfloor j\theta \rfloor + \{j\theta\}} = 10^{\lfloor j\theta \rfloor}\cdot 10^{\{j\theta\}}.$

Therefore the prefix is determined entirely by the number \(10^{\{j\theta\}}\in[1,10)\). For the target prefix \(123\), the interval used by the implementations is

$a=\log_{10}(123)-2 \approx 0.08990511143939792,$

$b=\log_{10}(124)-2 \approx 0.09342168516225026.$

Whenever \(\{j\theta\}\) falls inside that window, the mantissa lies in \([1.23,1.24)\), which means the decimal expansion of \(2^j\) begins with \(123\).

Step 4: Worked Example with \(L=12\)

For \(L=12\), we have \(d=2\), so

$a=\log_{10}(12)-1 \approx 0.07918124604762482,$

$b=\log_{10}(13)-1 \approx 0.11394335230683678.$

Now check a few exponents. For \(j=7\),

$7\theta \approx 2.1072099696478683,$

so

$\{7\theta\}\approx 0.1072099696478683 \in [a,b).$

That predicts that \(2^7\) begins with \(12\), and indeed \(2^7=128\).

For \(j=80\),

$80\theta \approx 24.082399653118495,$

hence

$\{80\theta\}\approx 0.082399653118495 \in [a,b).$

So the second hit occurs at \(j=80\), matching the small checkpoints used by the implementation.

Step 5: Apply the Same Mechanism to the Target Query

Nothing changes for \(L=123\) except the interval endpoints. We keep iterating the orbit \(r_{j+1}=\{r_j+\theta\}\), count how many times it enters the window for prefix \(123\), and stop at the \(678910\)-th hit. No large integer powers need to be constructed, because the logarithmic window already captures the leading digits exactly.

How the Code Works

The C++, Python, and Java implementations all follow the same mathematical plan: convert the prefix condition into a logarithmic interval, iterate the fractional parts of successive multiples of \(\log_{10}2\), and count interval hits until the requested occurrence is reached.

The C++ implementation computes the number of digits of the prefix and the two interval endpoints at runtime, then advances one exponent at a time using extended floating-point precision. It also checks small benchmark cases such as \(p(12,1)=7\), \(p(12,2)=80\), and \(p(123,45)=12710\) before producing the final answer.

The Python implementation uses the same floating-point recurrence but is specialized directly to the target query \(L=123\), \(n=678910\). The Java implementation is more specialized still: it stores scaled integer approximations of \(\log_{10}2\) and of the two interval endpoints for prefix \(123\). Since the upper endpoint for \(123\) is smaller than \(\log_{10}2\), every successful hit must occur immediately after a wraparound, so the integer-based version only needs to test wrapped updates.

Complexity Analysis

Each iteration performs a constant number of additions, comparisons, and at most one wraparound reduction. Therefore the running time is \(O(p(L,n))\), because we advance through exponents until the desired hit is found. The memory usage is \(O(1)\), since only a few scalar values are maintained throughout the search.

Footnotes and References

1. Project Euler problem page: https://projecteuler.net/problem=686
2. Common logarithm: Wikipedia - Common logarithm
3. Fractional part: Wikipedia - Fractional part
4. Equidistribution theorem: Wikipedia - Equidistribution theorem
5. Benford's law: Wikipedia - Benford's law