Problem 731: A Stoneham Number

Mathematical Foundation

Theorem 1 (Isolated Term Structure). For all $i \ge 1$, the $i$-th term $T_i = \frac{1}{3^i \cdot 10^{3^i}}$ contributes nonzero digits only at decimal positions $\ge 3^i + 1$. Moreover, for $i \ge 2$, the digit blocks of $T_i$ and $T_{i+1}$ do not overlap in positions $[3^i + 1,\, 3^{i+1}]$.

Proof. The term $T_i = 10^{-3^i} \cdot 3^{-i}$ has its first nonzero decimal digit at position $3^i + 1$ (the factor $10^{-3^i}$ shifts $1/3^i$ rightward by $3^i$ places). The decimal expansion of $1/3^i$ is purely periodic with period $\operatorname{ord}_{3^i}(10)$, which divides $\phi(3^i) = 2 \cdot 3^{i-1}$. Hence $T_i$ occupies digits in the range $[3^i+1, \, 3^i + 2 \cdot 3^{i-1}] = [3^i+1,\, 3^i + 2\cdot 3^{i-1}]$ before repeating. Since $3^i + 2 \cdot 3^{i-1} = 3^{i-1}(3+2) = 5 \cdot 3^{i-1} < 3^{i+1} = 3 \cdot 3^i$ for all $i \ge 1$, the repeating block of $T_i$ fits entirely before position $3^{i+1}+1$ where $T_{i+1}$ begins. Thus the blocks are isolated. $\square$

Lemma 1 (Digit Extraction). The $j$-th decimal digit (after the decimal point) of $1/3^i$ is

and $r_j$ is computable in $O(\log j)$ arithmetic operations via modular exponentiation.

Proof. Write $1/3^i = 0.d_1 d_2 d_3 \cdots$. By the standard long-division algorithm, $r_1 = 1$ and $r_{j+1} = 10 \, r_j \bmod 3^i$, with $d_j = \lfloor 10\, r_j / 3^i \rfloor$. By induction, $r_j = 10^{j-1} \bmod 3^i$. Computing $10^{j-1} \bmod 3^i$ uses repeated squaring in $O(\log j)$ multiplications modulo $3^i$. $\square$

Theorem 2 (Digit Block Summation). The 10-digit block $A(n)$ equals the last 10 digits of

where $B_i(n)$ is the integer formed by the 10 digits of $T_i$ at positions $n$ through $n+9$, and carries are propagated from right to left.

Proof. Since $A = \sum_{i=1}^{\infty} T_i$ and the digit blocks are isolated (Theorem 1), only finitely many terms $T_i$ contribute nonzero digits at any given position. Specifically, term $T_i$ can only contribute at position $n$ if $3^i \le n + 9$ (otherwise $T_i$‘s digits start after position $n+9$). The 10-digit block of $T_i$ at position $n$ is determined by extracting digits $n - 3^i$ through $n - 3^i + 9$ of $1/3^i$ via Lemma 1. Summing these integer blocks and propagating carries yields $A(n)$. $\square$

Editorial

A = sum_{i=1}^{inf} 1/(3^i * 10^{3^i}) A(n) = 10 digits of A starting at position n. Key: digits at position n come from terms with 3^i <= n+9. For each term, compute digits of 1/3^i at offset n - 3^i using modular exponentiation. We find contributing terms. We then compute 10-digit block for each contributing term. Finally, iterate over i in terms.

Pseudocode

Find contributing terms
Compute 10-digit block for each contributing term
for i in terms
Extract last 10 digits (handle carries)

Complexity Analysis

• Time: $O(\log_3 n \cdot \log n)$. There are $O(\log_3 n)$ contributing terms, each requiring $O(1)$ modular exponentiations of cost $O(\log n)$.
• Space: $O(\log n)$ for storing intermediate values in modular exponentiation.

Answer

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

/*
 * Problem 731: A Stoneham Number
 *
 * A = sum_{i=1}^{inf} 1/(3^i * 10^{3^i})
 * A(n) = 10 digits of A starting at decimal position n.
 *
 * For each term i with 3^i <= n+9, compute digits of 1/3^i at offset (n - 3^i)
 * using modular exponentiation: 10^offset mod 3^i.
 */

typedef unsigned long long ull;
typedef __int128 lll;

ull power_mod(ull base, ull exp, ull mod) {
    ull result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = (lll)result * base % mod;
        base = (lll)base * base % mod;
        exp >>= 1;
    }
    return result;
}

// Get num_digits of 1/3^i starting at position 'start'
vector<int> digits_inv3i(int i, ull start, int num_digits) {
    // 3^i as big number - for i up to ~34, this fits in 128 bits
    // Use Python for the actual large computation; here demonstrate for small i
    ull mod = 1;
    for (int j = 0; j < i; j++) mod *= 3;

    ull r = power_mod(10, start, mod);
    vector<int> result;
    for (int k = 0; k < num_digits; k++) {
        ull nr = (lll)10 * r;
        result.push_back(nr / mod);
        r = nr % mod;
    }
    return result;
}

int main() {
    // Verify A(100)
    // Terms: i=1 (3^1=3), i=2 (9), i=3 (27), i=4 (81)
    int num_digits = 10;
    int extra = 20;
    ull n = 100;

    // For small cases, accumulate
    // (Full implementation needs arbitrary precision for large i)
    printf("A(10^16) requires Python/mpz for 3^34 modular arithmetic\n");

    return 0;
}

"""
Problem 731: A Stoneham Number

A = sum_{i=1}^{inf} 1/(3^i * 10^{3^i})
A(n) = 10 digits of A starting at position n.

Key: digits at position n come from terms with 3^i <= n+9.
For each term, compute digits of 1/3^i at offset n - 3^i using modular exponentiation.
"""

def digits_of_inv3i(i, start, count):
    """Get 'count' decimal digits of 1/3^i starting at position 'start' (0-indexed after decimal point).

    The j-th digit (0-indexed) of 1/3^i is floor(10^{j+1} / 3^i) mod 10.
    Equivalently, compute 10^{start+k} mod (10 * 3^i) for k = 0..count-1.
    """
    mod = 3 ** i
    result = 0
    for k in range(count):
        pos = start + k
        # digit at position pos (1-indexed) = floor(10^pos mod (10*mod)) / mod
        # = (10^pos mod (10*mod)) // mod ... no, simpler:
        # digit = (10^pos * 10 // mod) ... nah.
        # 1/3^i = 0.d1 d2 d3 ...
        # d_j (1-indexed) = floor(10^j / 3^i) - 10 * floor(10^{j-1} / 3^i)
        # = floor(10 * (10^{j-1} mod 3^i) / 3^i)
        # So: remainder r = 10^{j-1} mod 3^i, then digit = (10*r) // 3^i
        # and new remainder = (10*r) mod 3^i
        pass

    # Better approach: compute starting remainder, then iterate
    mod = 3 ** i
    r = pow(10, start, mod)  # 10^start mod 3^i
    digits = []
    for k in range(count):
        d = (10 * r) // mod
        r = (10 * r) % mod
        digits.append(d)
    return digits

def stoneham_A(n, num_digits=10):
    """Compute A(n) = 10 decimal digits of the Stoneham number starting at position n."""
    # Find all i with 3^i <= n + num_digits - 1
    max_i = 0
    power3 = 3
    while power3 <= n + num_digits - 1:
        max_i += 1
        power3 *= 3

    # Accumulate digit contributions
    # We work with a large integer: sum of contributions * 10^extra for carries
    extra = 20  # extra digits for carry safety
    total = 0

    power3 = 3
    for i in range(1, max_i + 1):
        offset = n - power3  # position in 1/3^i expansion
        if offset < 0:
            power3 *= 3
            continue
        digs = digits_of_inv3i(i, offset, num_digits + extra)
        # Convert to integer
        val = 0
        for d in digs:
            val = val * 10 + d
        total += val
        power3 *= 3

    # Extract top num_digits digits
    s = str(total)
    # The result is the first num_digits digits of the sum
    # But we need to handle carries: the sum might produce more digits
    result = s[:num_digits]
    return int(result)

# Verify
a100 = stoneham_A(100)
print(f"A(100) = {a100}")  # Expected: 4938271604
assert a100 == 4938271604, f"Got {a100}"

# A(10^8) - this works but takes a moment
a_1e8 = stoneham_A(10**8)
print(f"A(10^8) = {a_1e8}")  # Expected: 2584642393

# A(10^16)
a_1e16 = stoneham_A(10**16)
print(f"A(10^16) = {a_1e16}")