Project Euler

Nth Digit of Reciprocals

Let d_n(x) be the n -th decimal digit of the fractional part of x (or 0 if the fractional part has fewer than n digits). Examples: d_7(1/3) = 3 since 1/3 = 0.3333333333... d_7(1/6) = 6 since 1/6 =...

Source sync Apr 19, 2026

Problem #0820

Level Level 13

Solved By 1,324

Languages C++, Python

Answer 44967734

Length 197 words

modular_arithmeticbrute_forcesearch

Let $d(n)$ be the $n^{th}$ decimal digit of the fractional part of $x$, or $0$ if the fractional part has fewer than $n$ digits.

For example:

$d_7(1) = d_7(\frac {1}{2}) = d_7(\frac {1}{4}) = d_7(\frac {1}{5}) = 0$
$d_7(\frac {1}{3}) = 3$ since $\frac {1}{3} = 0.333333\textbf {\textcolor {red}{3}}333\ldots $
$d_7(\frac {1}{6}) = 6$ since $\frac {1}{6} = 0.666666\textbf {\textcolor {red}{6}}666\ldots $
$d_7(\frac {1}{7}) = 1$ since $\frac {1}{7} = 0.142857\textbf {\textcolor {red}{1}}428\ldots $

Let $S(n) = \sum _{k = 1}^{n} d_n(\frac {1}{k})$.

You are given:

$S(7) = 0 + 0 + 3 + 0 + 0 + 6 + 1 = 10$
$S(100) = 418$.

Find $S(10^7)$.

Problem 820: Nth Digit of Reciprocals

Mathematical Analysis

Key Observation

The $n$ -th decimal digit of $1/k$ can be computed via long division. After $n-1$ steps of long division, the remainder is $r = 10^{n-1} \bmod k$ . Then:

d_n(1/k) = \left\lfloor \frac{10r}{k} \right\rfloor = \left\lfloor \frac{10 \cdot (10^{n-1} \bmod k)}{k} \right\rfloor

Proof

We have $1/k = 0.d_1 d_2 d_3 \ldots$

The standard long division algorithm maintains a remainder $r_i$ :

$r_0 = 1$
$d_i = \lfloor 10 r_{i-1} / k \rfloor$
$r_i = 10 r_{i-1} \bmod k$

By induction, $r_{i} = 10^{i} \bmod k$ , so:

d_n = \left\lfloor \frac{10 \cdot (10^{n-1} \bmod k)}{k} \right\rfloor

Computation

For each $k$ from $1$ to $N = 10^7$ :

Compute $10^{N-1} \bmod k$ using binary exponentiation in $O(\log N)$ .
Compute the digit as $\lfloor 10r/k \rfloor$ .
Sum all digits.

Editorial

We use dynamic programming over the state space implied by the derivation, apply each admissible transition, and read the answer from the final table entry.

Pseudocode

total = 0
For k from 2 to N:
    r = modpow(10, N-1, k)
    digit = (10 * r) / k
    total += digit
Return total

Correctness

Theorem. The method described above computes exactly the quantity requested in the problem statement.

Proof. The preceding analysis identifies the admissible objects and derives the formula, recurrence, or exhaustive search carried out by the algorithm. The computation evaluates exactly that specification, so every valid contribution is included once and no invalid contribution is counted. Therefore the returned value is the required answer. $\square$

Complexity Analysis

Time: $O(N \log N)$ — for each of $N$ values of $k$ , binary exponentiation takes $O(\log N)$ .
Space: $O(1)$ .

Answer

\boxed{44967734}

C++ project_euler/problem_820/solution.cpp

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // S(n) = sum_{k=1}^{n} d_n(1/k)
    // d_n(1/k) = floor(10^n / k) mod 10
    // We need d_n(1/k): the n-th decimal digit of 1/k
    // 1/k = 0.d1 d2 d3 ... dn ...
    // d_n(1/k) = floor(10^n * (1/k)) mod 10 = floor(10^n / k) mod 10
    // But 10^n is huge for n=10^7. We use modular arithmetic:
    // 10^n mod k gives us the remainder, then floor(10^n/k) mod 10 = (10 * (10^{n-1} mod k)) / k ...
    // Actually: d_n(1/k) = floor(10 * r / k) where r = 10^{n-1} mod k
    // Because: 1/k has digits determined by long division.
    // After n-1 steps, the remainder is 10^{n-1} mod k, then d_n = floor(10*r/k)

    const int N = 10000000;

    // We need 10^{N-1} mod k for each k from 1 to N.
    // 10^{N-1} mod k can be computed using modular exponentiation for each k,
    // but that's O(N log N) total which should be feasible.

    // Alternative: use the fact that for the n-th digit of 1/k,
    // we need r = 10^{n-1} mod k, then digit = (10*r) / k.

    long long total = 0;

    for(int k = 1; k <= N; k++){
        if(k == 1){
            // 1/1 = 1.000..., fractional part = 0, so d_n = 0
            continue;
        }
        // Compute 10^{N-1} mod k using fast exponentiation
        long long exp = (long long)N - 1;
        long long base = 10 % k;
        long long r = 1;
        long long b = base;
        long long e = exp;
        while(e > 0){
            if(e & 1) r = r * b % k;
            b = b * b % k;
            e >>= 1;
        }
        // digit = (10 * r) / k
        int digit = (int)(10LL * r / k);
        total += digit;
    }

    cout << total << endl;

    return 0;
}

Python project_euler/problem_820/solution.py

def solve():
    N = 10**7

    total = 0
    for k in range(2, N + 1):
        r = pow(10, N - 1, k)
        digit = (10 * r) // k
        total += digit

    print(total)

if __name__ == "__main__":
    solve()