Problem 417: Reciprocal Cycles II

Project Euler Problem 417 Solution

EulerSolve provides an optimized solution for Project Euler Problem 417, Reciprocal Cycles II, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary Define $L(n)$ as the length of the repeating part in the decimal expansion of $1/n$. The task is to compute $$S(N)=\sum_{n=3}^{N} L(n)$$ for a very large bound $N$. A direct simulation of long division for every denominator is much too slow, so the implementations reorganize the sum using multiplicative order and a grouping argument over powers of $2$ and $5$. Mathematical Approach Step 1: Remove the terminating part Every denominator can be written uniquely as $$n=2^a5^b m,\qquad \gcd(m,10)=1.$$ The powers of $2$ and $5$ only create the finite prefix of the decimal expansion. The recurring part depends entirely on the remaining factor $m$. If $m=1$, then $1/n$ is a terminating decimal and therefore $L(n)=0$. If $m>1$, the repetend length is the multiplicative order of $10$ modulo $m$: $$L(n)=\operatorname{ord}_m(10),$$ where $\operatorname{ord}_m(10)$ is the smallest positive integer $k$ such that $$10^k\equiv 1 \pmod m.$$ This is the standard number-theoretic description of repeating decimals. Step 2: Group denominators by the same odd core Fix an odd integer $m$ with $5 \nmid m$. Every denominator of the form $$n=m\,s,\qquad s=2^a5^b,$$ has exactly the same recurring-cycle length, namely $\operatorname{ord}_m(10)$, because multiplying by $2$ and $5$ changes only the terminating prefix....

Detailed mathematical approach

Problem Summary

Define $L(n)$ as the length of the repeating part in the decimal expansion of $1/n$. The task is to compute

$$S(N)=\sum_{n=3}^{N} L(n)$$

for a very large bound $N$. A direct simulation of long division for every denominator is much too slow, so the implementations reorganize the sum using multiplicative order and a grouping argument over powers of $2$ and $5$.

Mathematical Approach

Step 1: Remove the terminating part

Every denominator can be written uniquely as

$$n=2^a5^b m,\qquad \gcd(m,10)=1.$$

The powers of $2$ and $5$ only create the finite prefix of the decimal expansion. The recurring part depends entirely on the remaining factor $m$.

If $m=1$, then $1/n$ is a terminating decimal and therefore $L(n)=0$. If $m>1$, the repetend length is the multiplicative order of $10$ modulo $m$:

$$L(n)=\operatorname{ord}_m(10),$$

where $\operatorname{ord}_m(10)$ is the smallest positive integer $k$ such that

$$10^k\equiv 1 \pmod m.$$

This is the standard number-theoretic description of repeating decimals.

Step 2: Group denominators by the same odd core

Fix an odd integer $m$ with $5 \nmid m$. Every denominator of the form

$$n=m\,s,\qquad s=2^a5^b,$$

has exactly the same recurring-cycle length, namely $\operatorname{ord}_m(10)$, because multiplying by $2$ and $5$ changes only the terminating prefix.

For a given quotient $Q$, define the count of $2$-$5$-smooth multipliers by

$$C(Q)=\#\left\{(a,b)\in \mathbb{Z}_{\ge 0}^2:2^a5^b\le Q\right\}.$$

Then the denominators whose odd core is $m$ contribute

$$\operatorname{ord}_m(10)\,C\!\left(\left\lfloor\frac{N}{m}\right\rfloor\right).$$

Summing over all admissible cores gives the central identity used by the fast solver:

$$\boxed{S(N)=\sum_{\substack{m\le N\\ 2\nmid m,\, 5\nmid m}} \operatorname{ord}_m(10)\,C\!\left(\left\lfloor\frac{N}{m}\right\rfloor\right).}$$

The missing case $m=1$ can be ignored because its cycle length is $0$.

Step 3: Decompose the order over prime powers

Write the odd core as

$$m=\prod_{i=1}^{r} p_i^{e_i},\qquad p_i\neq 2,5.$$

Since the prime-power factors are pairwise coprime, the Chinese remainder theorem implies that the order modulo the product is the least common multiple of the orders modulo each prime power:

$$\operatorname{ord}_m(10)=\mathrm{lcm}\!\left(\operatorname{ord}_{p_1^{e_1}}(10),\dots,\operatorname{ord}_{p_r^{e_r}}(10)\right).$$

So the problem reduces to computing $\operatorname{ord}_{p^e}(10)$ efficiently for each prime-power factor.

Step 4: Order modulo a prime

For an odd prime $p\neq 5$, Fermat's little theorem gives

$$10^{p-1}\equiv 1 \pmod p,$$

so $\operatorname{ord}_p(10)$ must divide $p-1$. The implementations therefore start from $p-1$, factor that number, and try to divide away each prime factor as long as the congruence test still succeeds. In other words, if $d$ is the current candidate order and $q\mid d$, then one checks whether

$$10^{d/q}\equiv 1 \pmod p.$$

If the test is true, the order was not minimal and the candidate can be reduced to $d/q$. Repeating this process yields the exact order modulo $p$.

Step 5: Lift from $p$ to $p^e$

Once the order modulo $p$ is known, the order modulo higher powers of $p$ is obtained incrementally. If

$$t=\operatorname{ord}_{p^{k-1}}(10),$$

then the next order satisfies

$$\operatorname{ord}_{p^k}(10)\in\{t,pt\}.$$

We distinguish the two cases by testing whether

$$10^t\equiv 1 \pmod{p^k}.$$

If that congruence already holds, the order stays equal to $t$; otherwise it grows by a factor $p$. This is exactly the lifting rule used by the implementations when building prime-power orders.

Only primes with $p\le \sqrt{N}$ need tables for exponents $e\ge 2$, because if $p>\sqrt{N}$ then $p^2>N$ and such a prime can appear only to the first power in any core $m\le N$.

Worked Example: $N=10$

The admissible odd cores are $m=3,7,9$. For $m=3$, the smooth multipliers satisfying $3s\le 10$ are $s=1,2$, so the multiplicity is $2$. Since $\operatorname{ord}_3(10)=1$, this contributes $2$.

For $m=7$, only $s=1$ is possible, and $\operatorname{ord}_7(10)=6$, so the contribution is $6$.

For $m=9$, again only $s=1$ is possible, and $10\equiv 1 \pmod 9$, so $\operatorname{ord}_9(10)=1$, contributing $1$.

Therefore

$$S(10)=2+6+1=9,$$

which matches the direct sum of cycle lengths for $1/3,1/4,\dots,1/10$.

How the Code Works

The C++, Python, and Java implementations follow the same arithmetic pipeline. They first build an odd-only smallest-prime-factor sieve, which is enough because only odd cores coprime to $10$ matter. They then enumerate all odd primes other than $5$, compute $\operatorname{ord}_p(10)$ by stripping factors from $p-1$, and precompute prime-power orders wherever higher powers can still occur below the bound.

In parallel, the implementation generates the sorted list of all numbers of the form $2^a5^b\le N$. For each odd core $m$ with $5\nmid m$, it reconstructs $\operatorname{ord}_m(10)$ from the prime-power factors using repeated $\mathrm{lcm}$, counts the valid smooth multipliers with a binary search in that list, and adds the product to the running total. The Python version serves as a thin launcher around the compiled fast solver, while the Java version reproduces the same number-theoretic computation directly.

Complexity Analysis

The preprocessing sieve is near-linear, usually summarized as $O(N\log\log N)$ time with $O(N)$ stored state, although the odd-only representation roughly halves the memory footprint. The list of $2^a5^b$ values has size only $O((\log N)^2)$, so it is negligible compared with the sieve.

After preprocessing, each admissible core is factorized quickly from the sieve and combined from only a few prime-power orders. The total work is dominated by the sieve construction, the prime-order precomputation, and the single pass over odd cores not divisible by $5$. This is dramatically faster than simulating decimal periods denominator by denominator, and it is practical for $N=10^8$.

Footnotes and References

Problem page: https://projecteuler.net/problem=417
Repeating decimal: Wikipedia — Repeating decimal
Multiplicative order: Wikipedia — Multiplicative order
Chinese remainder theorem: Wikipedia — Chinese remainder theorem
Fermat's little theorem: Wikipedia — Fermat's little theorem

Problem 417 source code

C++

#include <algorithm>
#include <cmath>
#include <cstdint>
#include <iostream>
#include <numeric>
#include <string>
#include <thread>
#include <vector>

namespace {

using u32 = std::uint32_t;
using u64 = std::uint64_t;
using u128 = __uint128_t;
using i64 = std::int64_t;

struct Options {
    int limit = 100000000;
    int threads = 0;
    bool run_checkpoints = true;
};

bool parse_int_after_prefix(const std::string& arg, const std::string& prefix, int& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }
    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }
    try {
        value = std::stoi(tail);
    } catch (...) {
        return false;
    }
    return true;
}

bool parse_arguments(int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);
        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        if (parse_int_after_prefix(arg, "--limit=", options.limit) ||
            parse_int_after_prefix(arg, "--threads=", options.threads)) {
            continue;
        }
        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }
    return options.limit >= 3 && options.threads >= 0;
}

std::string to_string_u128(u128 value) {
    if (value == 0) {
        return "0";
    }
    std::string out;
    while (value > 0) {
        const int digit = static_cast<int>(value % 10);
        out.push_back(static_cast<char>('0' + digit));
        value /= 10;
    }
    std::reverse(out.begin(), out.end());
    return out;
}

u64 mod_pow(u64 base, u64 exp, u64 mod) {
    u64 result = 1 % mod;
    u64 cur = base % mod;
    u64 e = exp;
    while (e > 0) {
        if (e & 1ULL) {
            result = static_cast<u64>((static_cast<u128>(result) * cur) % mod);
        }
        cur = static_cast<u64>((static_cast<u128>(cur) * cur) % mod);
        e >>= 1ULL;
    }
    return result;
}

int choose_thread_count(int requested, std::size_t work_items) {
    if (work_items <= 1) {
        return 1;
    }
    int threads = requested;
    if (threads <= 0) {
        threads = static_cast<int>(std::thread::hardware_concurrency());
    }
    if (threads <= 0) {
        threads = 4;
    }
    if (threads > static_cast<int>(work_items)) {
        threads = static_cast<int>(work_items);
    }
    if (threads < 1) {
        threads = 1;
    }
    return threads;
}

std::vector<std::uint16_t> build_odd_spf(const int limit) {
    std::vector<std::uint16_t> spf(static_cast<std::size_t>(limit / 2 + 1), 0);
    const int root = static_cast<int>(std::sqrt(static_cast<double>(limit)));

    for (int i = 3; i <= root; i += 2) {
        if (spf[static_cast<std::size_t>(i >> 1)] != 0) {
            continue;
        }
        const i64 step = 2LL * i;
        for (i64 j = 1LL * i * i; j <= limit; j += step) {
            std::uint16_t& cell = spf[static_cast<std::size_t>(j >> 1)];
            if (cell == 0) {
                cell = static_cast<std::uint16_t>(i);
            }
        }
    }
    return spf;
}

std::vector<int> collect_primes(const int limit, const std::vector<std::uint16_t>& spf) {
    std::vector<int> primes;
    primes.reserve(static_cast<std::size_t>(limit / 12));
    for (int p = 3; p <= limit; p += 2) {
        if (p != 5 && spf[static_cast<std::size_t>(p >> 1)] == 0) {
            primes.push_back(p);
        }
    }
    return primes;
}

u32 multiplicative_order_prime(const int p, const std::vector<std::uint16_t>& spf) {
    u32 ord = static_cast<u32>(p - 1);
    u32 rem = ord;

    if ((rem & 1U) == 0U) {
        while ((rem & 1U) == 0U) {
            rem >>= 1U;
        }
        while ((ord & 1U) == 0U) {
            const u32 cand = ord >> 1U;
            if (mod_pow(10, cand, static_cast<u64>(p)) == 1ULL) {
                ord = cand;
            } else {
                break;
            }
        }
    }

    while (rem > 1U) {
        u32 q = static_cast<u32>(spf[static_cast<std::size_t>(rem >> 1U)]);
        if (q == 0U) {
            q = rem;
        }
        while (rem % q == 0U) {
            rem /= q;
        }
        while (ord % q == 0U) {
            const u32 cand = ord / q;
            if (mod_pow(10, cand, static_cast<u64>(p)) == 1ULL) {
                ord = cand;
            } else {
                break;
            }
        }
    }
    return ord;
}

std::vector<u32> compute_prime_orders_parallel(const std::vector<int>& primes,
                                               const std::vector<std::uint16_t>& spf,
                                               const int limit,
                                               const int requested_threads) {
    std::vector<u32> ord_prime(static_cast<std::size_t>(limit / 2 + 1), 0U);
    ord_prime[0] = 1U;  // order(10 mod 1)

    const int thread_count = choose_thread_count(requested_threads, primes.size());
    std::vector<std::thread> workers;
    workers.reserve(static_cast<std::size_t>(thread_count));

    for (int t = 0; t < thread_count; ++t) {
        const std::size_t begin = primes.size() * static_cast<std::size_t>(t) /
                                  static_cast<std::size_t>(thread_count);
        const std::size_t end = primes.size() * static_cast<std::size_t>(t + 1) /
                                static_cast<std::size_t>(thread_count);
        workers.emplace_back([&, begin, end]() {
            for (std::size_t i = begin; i < end; ++i) {
                const int p = primes[i];
                ord_prime[static_cast<std::size_t>(p >> 1)] = multiplicative_order_prime(p, spf);
            }
        });
    }
    for (auto& worker : workers) {
        worker.join();
    }
    return ord_prime;
}

std::vector<std::vector<u32>> build_small_prime_power_orders(
    const int limit, const std::vector<int>& primes, const std::vector<u32>& ord_prime) {
    const int root = static_cast<int>(std::sqrt(static_cast<double>(limit)));
    std::vector<std::vector<u32>> prime_power_orders(static_cast<std::size_t>(root + 1));

    for (const int p : primes) {
        if (p > root) {
            break;
        }
        auto& table = prime_power_orders[static_cast<std::size_t>(p)];
        int emax = 1;
        u64 pp = static_cast<u64>(p);
        while (pp <= static_cast<u64>(limit / p)) {
            pp *= static_cast<u64>(p);
            ++emax;
        }

        table.assign(static_cast<std::size_t>(emax + 1), 0U);
        table[1] = ord_prime[static_cast<std::size_t>(p >> 1)];

        pp = static_cast<u64>(p);
        for (int e = 2; e <= emax; ++e) {
            pp *= static_cast<u64>(p);
            const u32 prev = table[static_cast<std::size_t>(e - 1)];
            u32 cur = prev;
            if (mod_pow(10, prev, pp) != 1ULL) {
                cur = static_cast<u32>(prev * static_cast<u32>(p));
            }
            table[static_cast<std::size_t>(e)] = cur;
        }
    }
    return prime_power_orders;
}

std::vector<int> build_smooth_numbers(const int limit) {
    std::vector<int> smooth;
    for (u64 p2 = 1ULL; p2 <= static_cast<u64>(limit); p2 *= 2ULL) {
        for (u64 p5 = 1ULL; p2 * p5 <= static_cast<u64>(limit); p5 *= 5ULL) {
            smooth.push_back(static_cast<int>(p2 * p5));
        }
    }
    std::sort(smooth.begin(), smooth.end());
    smooth.erase(std::unique(smooth.begin(), smooth.end()), smooth.end());
    return smooth;
}

u32 multiplicative_order_from_factorization(
    int n, const std::vector<std::uint16_t>& spf, const std::vector<u32>& ord_prime,
    const std::vector<std::vector<u32>>& prime_power_orders) {
    u32 ord = 1U;
    int x = n;
    while (x > 1) {
        int p = static_cast<int>(spf[static_cast<std::size_t>(x >> 1)]);
        if (p == 0) {
            p = x;
        }
        int e = 1;
        int pp = p;
        x /= p;
        while (x % p == 0) {
            x /= p;
            pp *= p;
            ++e;
        }

        u32 part = 0U;
        if (e == 1) {
            part = ord_prime[static_cast<std::size_t>(p >> 1)];
        } else if (p < static_cast<int>(prime_power_orders.size()) &&
                   e < static_cast<int>(prime_power_orders[static_cast<std::size_t>(p)].size())) {
            part = prime_power_orders[static_cast<std::size_t>(p)][static_cast<std::size_t>(e)];
        } else {
            part = ord_prime[static_cast<std::size_t>(p >> 1)];
            u64 mod = static_cast<u64>(p);
            for (int k = 2; k <= e; ++k) {
                mod *= static_cast<u64>(p);
                if (mod_pow(10, part, mod) != 1ULL) {
                    part = static_cast<u32>(part * static_cast<u32>(p));
                }
            }
        }

        const u32 g = std::gcd(ord, part);
        ord = static_cast<u32>((static_cast<u64>(ord) / g) * part);
    }
    return ord;
}

u128 solve_fast(const int limit, const int requested_threads) {
    const std::vector<std::uint16_t> spf = build_odd_spf(limit);
    const std::vector<int> primes = collect_primes(limit, spf);
    const std::vector<u32> ord_prime =
        compute_prime_orders_parallel(primes, spf, limit, requested_threads);
    const std::vector<std::vector<u32>> prime_power_orders =
        build_small_prime_power_orders(limit, primes, ord_prime);
    const std::vector<int> smooth = build_smooth_numbers(limit);

    const std::size_t odd_count =
        static_cast<std::size_t>((static_cast<u64>(limit) - 3ULL) / 2ULL + 1ULL);
    const int thread_count = choose_thread_count(requested_threads, odd_count);
    std::vector<u128> partial(static_cast<std::size_t>(thread_count), 0);
    std::vector<std::thread> workers;
    workers.reserve(static_cast<std::size_t>(thread_count));

    for (int t = 0; t < thread_count; ++t) {
        const std::size_t begin = odd_count * static_cast<std::size_t>(t) /
                                  static_cast<std::size_t>(thread_count);
        const std::size_t end = odd_count * static_cast<std::size_t>(t + 1) /
                                static_cast<std::size_t>(thread_count);
        workers.emplace_back([&, begin, end, t]() {
            u128 local = 0;
            for (std::size_t idx = begin; idx < end; ++idx) {
                const int n = static_cast<int>(3 + 2 * idx);
                if (n % 5 == 0) {
                    continue;
                }
                const u32 ord =
                    multiplicative_order_from_factorization(n, spf, ord_prime, prime_power_orders);
                const int quotient = limit / n;
                const int multiplicity =
                    static_cast<int>(std::upper_bound(smooth.begin(), smooth.end(), quotient) -
                                     smooth.begin());
                local += static_cast<u128>(ord) * static_cast<u128>(multiplicity);
            }
            partial[static_cast<std::size_t>(t)] = local;
        });
    }
    for (auto& worker : workers) {
        worker.join();
    }

    u128 total = 0;
    for (const u128 value : partial) {
        total += value;
    }
    return total;
}

u64 recurring_cycle_length_bruteforce(int n) {
    while ((n % 2) == 0) {
        n /= 2;
    }
    while ((n % 5) == 0) {
        n /= 5;
    }
    if (n == 1) {
        return 0;
    }

    int r = 10 % n;
    u64 len = 1;
    while (r != 1) {
        r = static_cast<int>((static_cast<i64>(r) * 10LL) % n);
        ++len;
    }
    return len;
}

u128 solve_bruteforce(const int limit) {
    u128 total = 0;
    for (int n = 3; n <= limit; ++n) {
        total += recurring_cycle_length_bruteforce(n);
    }
    return total;
}

bool run_checkpoints(const int requested_threads) {
    if (solve_bruteforce(10) != 9) {
        std::cerr << "Checkpoint failed: sum_{n=3..10} L(n)\n";
        return false;
    }

    if (solve_fast(1000, requested_threads) != solve_bruteforce(1000)) {
        std::cerr << "Checkpoint failed: fast solver vs brute force at limit=1000\n";
        return false;
    }

    if (solve_fast(1000000, requested_threads) != static_cast<u128>(55535191115ULL)) {
        std::cerr << "Checkpoint failed: sum_{n=3..1000000} L(n)\n";
        return false;
    }
    return true;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }
    if (options.run_checkpoints && !run_checkpoints(options.threads)) {
        return 2;
    }

    const u128 answer = solve_fast(options.limit, options.threads);
    std::cout << to_string_u128(answer) << '\n';
    return 0;
}

Python

from __future__ import annotations

import re
import shutil
import subprocess
from pathlib import Path

ANSWER_RE = re.compile(r"answer\s*:\s*(.+)$", re.IGNORECASE)
EQUAL_RE = re.compile(r"=\s*(.+)$")


def parse_output(stdout: str) -> str:
    lines = [line.strip() for line in stdout.splitlines() if line.strip()]
    if not lines:
        return ""
    answers = []
    equals = []
    for line in lines:
        m1 = ANSWER_RE.search(line)
        if m1:
            answers.append(m1.group(1).strip())
        m2 = EQUAL_RE.search(line)
        if m2:
            equals.append(m2.group(1).strip())
    if answers:
        return answers[-1]
    if equals:
        return equals[-1]
    return lines[-1]


def should_skip_cpp_checkpoints(src: Path) -> bool:
    try:
        text = src.read_text(encoding="utf-8", errors="ignore")
    except OSError:
        return False
    return "--skip-checkpoints" in text


def run_cpp(binary: Path, src: Path, root: Path) -> str:
    cmd = [str(binary)]
    if should_skip_cpp_checkpoints(src):
        cmd.append("--skip-checkpoints")

    try:
        return subprocess.check_output(cmd, text=True, cwd=root)
    except subprocess.CalledProcessError:
        return subprocess.check_output(cmd, text=True, cwd=src.parent)


def solve() -> str:
    problem_id = __file__.split("Euler")[-1].split(".")[0]
    root = Path(__file__).resolve().parent.parent
    src = root / "solutionsCpp" / f"Euler{problem_id}.cpp"
    binary = root / "solutionsCpp" / f".euler{problem_id}_py_bridge"

    if not binary.exists() or src.stat().st_mtime > binary.stat().st_mtime:
        compiler = shutil.which("clang++") or shutil.which("g++")
        if not compiler:
            raise RuntimeError("No C++ compiler found (clang++/g++).")
        subprocess.check_call([compiler, "-std=c++17", "-O2", str(src), "-o", str(binary)])

    output = run_cpp(binary=binary, src=src, root=root)
    parsed = parse_output(output)
    if not parsed:
        raise RuntimeError(f"Euler{problem_id} bridge produced empty output.")
    return parsed


if __name__ == "__main__":
    print(solve())

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.IntStream;

public class Euler417 {
    static long modPow(long base, long exp, long mod) {
        long result = 1 % mod;
        long cur = base % mod;
        long e = exp;
        while (e > 0) {
            if ((e & 1) != 0) {
                result = (result * cur) % mod;
            }
            cur = (cur * cur) % mod;
            e >>= 1;
        }
        return result;
    }

    static short[] buildOddSpf(int limit) {
        short[] spf = new short[limit / 2 + 1];
        int root = (int) Math.sqrt(limit);

        for (int i = 3; i <= root; i += 2) {
            if (spf[i >> 1] != 0)
                continue;
            int step = 2 * i;
            for (long j = (long) i * i; j <= limit; j += step) {
                if (spf[(int) (j >> 1)] == 0) {
                    spf[(int) (j >> 1)] = (short) i;
                }
            }
        }
        return spf;
    }

    static int[] collectPrimes(int limit, short[] spf) {
        int[] primes = new int[limit / 12 + 1000];
        int count = 0;
        for (int p = 3; p <= limit; p += 2) {
            if (p != 5 && spf[p >> 1] == 0) {
                if (count == primes.length) {
                    primes = Arrays.copyOf(primes, primes.length * 2);
                }
                primes[count++] = p;
            }
        }
        return Arrays.copyOf(primes, count);
    }

    static int multiplicativeOrderPrime(int p, short[] spf) {
        int ord = p - 1;
        int rem = ord;

        if ((rem & 1) == 0) {
            while ((rem & 1) == 0)
                rem >>= 1;
            while ((ord & 1) == 0) {
                int cand = ord >> 1;
                if (modPow(10, cand, p) == 1) {
                    ord = cand;
                } else {
                    break;
                }
            }
        }

        while (rem > 1) {
            int q = spf[rem >> 1];
            if (q == 0)
                q = rem;
            while (rem % q == 0)
                rem /= q;
            while (ord % q == 0) {
                int cand = ord / q;
                if (modPow(10, cand, p) == 1) {
                    ord = cand;
                } else {
                    break;
                }
            }
        }
        return ord;
    }

    static int[][] buildSmallPrimePowerOrders(int limit, int[] primes, int[] ordPrime) {
        int root = (int) Math.sqrt(limit);
        int[][] primePowerOrders = new int[root + 1][];

        for (int p : primes) {
            if (p > root)
                break;
            int emax = 1;
            long pp = p;
            while (pp <= limit / p) {
                pp *= p;
                emax++;
            }

            int[] table = new int[emax + 1];
            table[1] = ordPrime[p >> 1];

            pp = p;
            for (int e = 2; e <= emax; e++) {
                pp *= p;
                int prev = table[e - 1];
                int cur = prev;
                if (modPow(10, prev, pp) != 1) {
                    cur = prev * p;
                }
                table[e] = cur;
            }
            primePowerOrders[p] = table;
        }
        return primePowerOrders;
    }

    static int[] buildSmoothNumbers(int limit) {
        int[] temp = new int[2000];
        int count = 0;
        for (long p2 = 1; p2 <= limit; p2 *= 2) {
            for (long p5 = 1; p2 * p5 <= limit; p5 *= 5) {
                temp[count++] = (int) (p2 * p5);
            }
        }
        int[] res = Arrays.copyOf(temp, count);
        Arrays.sort(res);
        return res;
    }

    static long gcd(long a, long b) {
        while (b != 0) {
            long t = b;
            b = a % b;
            a = t;
        }
        return a;
    }

    static int multiplicativeOrderFromFactorization(int n, short[] spf, int[] ordPrime, int[][] primePowerOrders) {
        int ord = 1;
        int x = n;
        while (x > 1) {
            int p = spf[x >> 1];
            if (p == 0)
                p = x;
            int e = 1;
            int pp = p;
            x /= p;
            while (x % p == 0) {
                x /= p;
                pp *= p;
                e++;
            }

            int part = 0;
            if (e == 1) {
                part = ordPrime[p >> 1];
            } else if (p < primePowerOrders.length && primePowerOrders[p] != null && e < primePowerOrders[p].length) {
                part = primePowerOrders[p][e];
            } else {
                part = ordPrime[p >> 1];
                long mod = p;
                for (int k = 2; k <= e; k++) {
                    mod *= p;
                    if (modPow(10, part, mod) != 1) {
                        part *= p;
                    }
                }
            }

            long g = gcd(ord, part);
            ord = (int) (((long) ord / g) * part);
        }
        return ord;
    }

    static String solve() {
        int limit = 100000000;
        short[] spf = buildOddSpf(limit);
        int[] primes = collectPrimes(limit, spf);

        int[] ordPrime = new int[limit / 2 + 1];
        ordPrime[0] = 1;

        IntStream.range(0, primes.length).parallel().forEach(i -> {
            int p = primes[i];
            ordPrime[p >> 1] = multiplicativeOrderPrime(p, spf);
        });

        int[][] primePowerOrders = buildSmallPrimePowerOrders(limit, primes, ordPrime);
        int[] smooth = buildSmoothNumbers(limit);

        int oddCount = (limit - 3) / 2 + 1;

        long total = IntStream.range(0, oddCount).parallel().mapToLong(idx -> {
            int n = 3 + 2 * idx;
            if (n % 5 == 0)
                return 0;

            int ord = multiplicativeOrderFromFactorization(n, spf, ordPrime, primePowerOrders);
            int quotient = limit / n;

            int low = 0, high = smooth.length;
            while (low < high) {
                int mid = (low + high) >>> 1;
                if (smooth[mid] <= quotient) {
                    low = mid + 1;
                } else {
                    high = mid;
                }
            }
            int multiplicity = low;

            return (long) ord * multiplicity;
        }).sum();

        return Long.toString(total);
    }

    public static void main(String[] args) {
        System.out.println(solve());
    }
}