Solution

Answer: 44967734

Let the decimal expansion of $1/k$ be

$$\frac1k = 0.a_1a_2a_3\cdots$$

Then the $n$-th decimal digit is $d_n(1/k)=a_n$.

We need

$$S(n)=\sum_{k=1}^n d_n!\left(\frac1k\right)$$

and specifically $S(10^7)$.

1. Mathematical analysis

Step 1: Extracting decimal digits

Recall the standard long-division fact:

$$a_n=\left\lfloor \frac{10,r_n}{k}\right\rfloor$$

where

$$r_n = 10^{n-1} \bmod k$$

is the remainder obtained before producing the $n$-th digit.

Indeed,

$$\frac{10^{n-1}}{k} = q+\frac{r_n}{k}$$

with $0\le r_n<k$. Multiplying by $10$,

$$\frac{10^n}{k} = 10q+\frac{10r_n}{k}$$

and the integer part of the fractional term is exactly the $n$-th decimal digit.

Therefore,

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

$$\boxed{ S(n)=\sum_{k=1}^n \left\lfloor \frac{10(10^{n-1}\bmod k)}{k} \right\rfloor }$$

This immediately gives an efficient algorithm.

Step 2: Verify on the example $n=7$

We compute:

$$d_7!\left(\frac13\right) = \left\lfloor \frac{10(10^6\bmod 3)}{3} \right\rfloor = \left\lfloor\frac{10\cdot1}{3}\right\rfloor =3$$

$$d_7!\left(\frac16\right) = \left\lfloor \frac{10(10^6\bmod 6)}{6} \right\rfloor = \left\lfloor\frac{10\cdot4}{6}\right\rfloor =6$$

$$d_7!\left(\frac17\right) = \left\lfloor \frac{10(10^6\bmod 7)}{7} \right\rfloor = \left\lfloor\frac{10\cdot1}{7}\right\rfloor =1$$

Summing all $k=1,\dots,7$ gives

$$S(7)=10$$

matching the statement.

2. Python implementation

def S(n: int) -> int:
    total = 0

    for k in range(1, n + 1):
        # r = 10^(n-1) mod k
        r = pow(10, n - 1, k)

        # nth decimal digit of 1/k
        digit = (10 * r) // k

        total += digit

    return total

# Check the examples
print(S(7))      # 10
print(S(100))    # 418

# Final answer
print(S(10**7))

3. Code walkthrough

total = 0

Accumulates the sum $S(n)$.

for k in range(1, n + 1):

Iterate through all denominators $1 \le k \le n$.

r = pow(10, n - 1, k)

Python’s 3-argument pow computes modular exponentiation efficiently:

$$r = 10^{n-1} \bmod k$$

using fast exponentiation in $O(\log n)$ time.

digit = (10 * r) // k

Using the derived formula

$$d_n(1/k)=\left\lfloor\frac{10r}{k}\right\rfloor$$

we obtain the $n$-th decimal digit directly.

total += digit

Add the digit to the running total.

The verification outputs are:

S(7)   = 10
S(100) = 418

which agree with the problem statement.

4. Final verification

The sum has $10^7$ terms, each between $0$ and $9$, so:

$$0 \le S(10^7) \le 9\times10^7$$

Our computed result:

$$44,967,734$$

lies comfortably in this range and is consistent with the average digit being about $4.5$, which is reasonable for recurring decimal expansions.

Therefore the computation is consistent.

Answer: 44967734

Project Euler Problem 820