Problem 383: Divisibility Comparison Between Factorials

Project Euler Problem 383 Solution

EulerSolve provides an optimized solution for Project Euler Problem 383, Divisibility Comparison Between Factorials, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary Define $$T_5(N)=\#\left\{1\le i\le N: v_5((2i-1)!) \lt 2v_5(i!)\right\}.$$ We must evaluate $T_5(10^{18})$. A direct scan over all $i$ is impossible, so the implemented solution turns the factorial inequality into a statement about carries in base $5$, then counts the valid numbers with a memoized digit DP. Mathematical Approach Step 1: Rewrite the factorial valuation Because $(2i)! = 2i\,(2i-1)!$, we have $$v_5((2i-1)!) = v_5((2i)!)-v_5(2i).$$ Subtracting $2v_5(i!)$ gives $$v_5((2i-1)!)-2v_5(i!)=v_5((2i)!)-2v_5(i!)-v_5(2i).$$ The middle part is exactly the $5$-adic valuation of the central binomial coefficient: $$v_5((2i)!)-2v_5(i!)=v_5\left(\binom{2i}{i}\right).$$ Since $v_5(2)=0$, we also have $v_5(2i)=v_5(i)$. Therefore the original condition is equivalent to $$v_5\left(\binom{2i}{i}\right) \lt v_5(i).$$ Legendre's formula explains why factorial valuations are natural here, but the code uses the binomial rewrite because it exposes a carry-counting interpretation immediately. Step 2: Apply Kummer's theorem in base $5$ Kummer's theorem states that $v_5\left(\binom{2i}{i}\right)$ equals the number of carries when adding $i+i$ in base $5$. Write $$i=5^a m,\qquad a=v_5(i),\qquad 5\nmid m.$$ Multiplying by $5^a$ merely appends $a$ trailing zeros in base $5$, so it does not create or destroy carries; it only shifts their positions....

Detailed mathematical approach

Problem Summary

For a positive integer $n$, let $f_5(n)$ be the largest integer $x$ for which $5^x$ divides $n$; the statement's example is $f_5(625000)=7$, because $625000=5^7\cdot8$. Let $T_5(n)$ be the number of indices $i$ with $1\le i\le n$ that satisfy

$$f_5\bigl((2i-1)!\bigr)\lt 2\,f_5(i!).$$

The statement gives the checkpoints $T_5(10^3)=68$ and $T_5(10^9)=2408210$, and asks for $T_5(10^{18})$. ^[1]

The whole solution in one sentence: the inequality holds exactly when doubling $i$ in base $5$ makes fewer carries than $i$ has trailing zeros, and the indices with that property below a bound are counted by a short digit-by-digit recursion with only a few hundred states.

Mathematical Approach

1. What $f_5$ measures, and Legendre's formula

The function $f_5$ is the $5$-adic valuation: it counts the factors $5$ in a number. ^[2] Its one indispensable property is additivity, $f_5(uv)=f_5(u)+f_5(v)$. For a factorial, Legendre's formula counts the multiples of $5$, then of $25$, and so on: ^[3]

$$f_5(n!)=\sum_{j\ge1}\lfloor n/5^j\rfloor=\frac{n-s_5(n)}{4},$$

where $s_5(n)$ is the base-$5$ digit sum of $n$. For $n=19$ the floor sum gives $\lfloor19/5\rfloor=3$, and since $19=(34)_5$ has digit sum $7$, the second form gives $(19-7)/4=3$. Both forms are used below.

2. Removing the odd factorial

The left-hand side skips the even factor $2i$. Since $(2i)!=2i\cdot(2i-1)!$ and $f_5(2)=0$, additivity gives

$$f_5\bigl((2i-1)!\bigr)=f_5\bigl((2i)!\bigr)-f_5(i).$$

Subtracting $2f_5(i!)$ from both sides therefore turns the inequality into a statement about the central binomial coefficient $\binom{2i}{i}=(2i)!/(i!)^2$, whose valuation is ^[5]

$$f_5\!\left(\binom{2i}{i}\right)=f_5\bigl((2i)!\bigr)-2f_5(i!).$$

The condition is thus equivalent to

$$f_5\!\left(\binom{2i}{i}\right)\lt f_5(i).$$

3. Kummer's theorem: the valuation counts carries

Kummer proved in 1852 that the exponent of a prime $p$ in $\binom{n}{m}$ equals the number of carries when $m$ and $n-m$ are added in base $p$. ^[4] With $n=2i$ and $m=i$ both summands are $i$, so the exponent counts the carries of the base-$5$ addition $i+i$. Write $c(i)$ for that number. The criterion becomes

$$c(i)\lt f_5(i).$$

This special case is short enough to prove outright. Add the columns of $i+i$ without carrying: their total is $2s_5(i)$. Every carry, propagated ones included, replaces five units of one column by one unit of the next and lowers that total by $4$; what is left are the digits of $2i$. Hence

$$2s_5(i)-s_5(2i)=4c(i).$$

The digit form of Legendre's formula turns the valuation of Section 2 into the same quantity:

$$f_5\!\left(\binom{2i}{i}\right)=\frac{2s_5(i)-s_5(2i)}{4}=c(i).$$

4. When does a carry happen?

Add $i+i$ in base $5$ from the least significant digit. At a position holding $d$ with an incoming carry $t\in\{0,1\}$, the column total is $2d+t$, the output digit $(2d+t)\bmod5$ and the outgoing carry $\lfloor(2d+t)/5\rfloor$. The ten pairs $(d,t)$ give an exceptionless rule:

a carry leaves the position exactly when $d\ge3$, or when $d=2$ and a carry came in;
digits $0$ and $1$ always absorb an incoming carry and emit none.

Two consequences matter. A digit $2$ emits a carry exactly when one comes in, and every emitted carry counts, so a run of $r$ digits $2$ above a carry adds $r$ more: $c=4$ for $(2223)_5$, yet $c=0$ for $(2222)_5$. And $c(i)=0$ exactly when every base-$5$ digit of $i$ is $0$, $1$ or $2$: such digits never start a carry, so none is ever in flight.

5. Trailing zeros do not change the carry count

Write $i=5^a m$ with $a=f_5(i)$ and $5\nmid m$. Multiplying by $5^a$ appends $a$ zeros at the least significant end, and doubling starts there with no incoming carry, so every appended zero emits none and the columns above them perform exactly the addition $m+m$:

$$c(5^a m)=c(m).$$

The criterion $c(i)\lt f_5(i)$ therefore reads $c(m)\lt a$, which for integers is the same as $c(m)\le a-1$. In particular $a\ge1$ is necessary: every index that contributes is a multiple of $5$.

6. The criterion on the small cases

The six multiples of $5$ up to $30$ show both outcomes. Each line gives $i$ in base $5$, the two sides of the original inequality, then $m$, $c(m)$ and $a$.

$i=5=(10)_5$: $1\lt2$; $m=1$, $c=0$, $a=1$ — it counts.
$i=10=(20)_5$: $3\lt4$; $m=2$, $c=0$, $a=1$ — it counts.
$i=15=(30)_5$: $6\lt6$ is false; $m=3$, $c=1$, $a=1$ — it fails.
$i=20=(40)_5$: $8\lt8$ is false; $m=4$, $c=1$, $a=1$ — it fails.
$i=25=(100)_5$: $10\lt12$; $m=1$, $c=0$, $a=2$ — it counts.
$i=30=(110)_5$: $13\lt14$; $m=6=(11)_5$, $c=0$, $a=1$ — it counts.

The two descriptions agree in every line; $15$ and $20$ fail because $a=1$ permits no carry at all and each produces one. The indices up to $100$ that count are $5$, $10$, $25$, $30$, $35$, $50$, $55$, $60$, $75$, $100$, so $T_5(30)=4$ and $T_5(100)=10$.

7. Grouping the indices by their power of five

Every positive integer has exactly one form $i=5^a m$ with $5\nmid m$, so the indices $i\le n$ split by the value of $a$. For fixed $a\ge1$ the admissible $m$ run over $1\le m\le\lfloor n/5^a\rfloor$ with $5\nmid m$, and such an $m$ contributes exactly when $c(m)\le a-1$. Define

$$\begin{aligned}G(x,k)=\#\{1\le m\le x:\ &5\nmid m,\\ &c(m)\le k\}.\end{aligned}$$

Then

$$T_5(n)=\sum_{a\ge1}G\bigl(\lfloor n/5^a\rfloor,\,a-1\bigr).$$

The sum stops once $5^a\gt n$, leaving $\lfloor\log_5 n\rfloor$ terms, $25$ for $n=10^{18}$. Nothing is double counted, since $(a,m)$ is fixed by $i$, and nothing is lost, since every qualifying $i$ has $a\ge1$.

8. Worked example: $T_5(10^3)=68$

With $n=1000$ the sum has four terms.

$a=1$: $G(200,0)=36$. A zero budget means all base-$5$ digits lie in $\{0,1,2\}$, the numbers of OEIS A037453. ^[7] There are $53$ up to $200$; the $17$ ending in the digit $0$ are multiples of $5$ and drop out, leaving $36$.
$a=2$: $G(40,1)=24$. Of the $32$ integers up to $40$ coprime to $5$, eight need two carries — $13$, $14$, $18$, $19$, $23$, $24$, $38$, $39$ — leaving $24$.
$a=3$: $G(8,2)=7$. Every $m\le8$ with $5\nmid m$ needs at most one carry, so all seven qualify.
$a=4$: $G(1,3)=1$, the single index $m=1$.

Adding, $36+24+7+1=68$, the value in the statement; the same split at $n=10^9$ gives $2408210$.

9. Counting with a carry budget, digit by digit

What remains is to evaluate $G(x,k)$ for a bound $x$ as large as $2\cdot10^{17}$ without enumerating anything. Process $m+m$ from the least significant digit. Only two things about the lower digits reach the higher ones: how many carries they used, and whether one is entering the next position. So for $x\ge0$, $k\ge0$ and $t\in\{0,1\}$ let $F(x,k,t)$ count the $y$ with $0\le y\le x$ whose doubling, continued with an incoming carry $t$, makes at most $k$ further carries. Splitting $y=5q+d$ by its last digit,

$$F(x,k,t)=\sum_{d=0}^{\min(4,x)}F\bigl(q_d,\,k-t_d,\,t_d\bigr),$$

$$\begin{aligned}q_d&=\lfloor(x-d)/5\rfloor,\\ t_d&=\lfloor(2d+t)/5\rfloor.\end{aligned}$$

The range of $q$ is right because $5q+d\le x$ means $q\le(x-d)/5$ for integer $q$. ^[6] The base cases are $F=0$ for $k\lt0$, a budget cannot be negative, and $F(0,k,t)=1$ for $k\ge0$: the only $y$ left is $0$, whose column total $t\le1$ emits nothing. Induction on $x$ finishes the proof, as every $q_d$ is smaller than $x$ once $x\ge1$. Excluding multiples of $5$ forbids only the last digit $0$, and the incoming carry at the lowest position is $0$, so

$$G(x,k)=\sum_{d=1}^{\min(4,x)}F\bigl(q_d,\,k-t_d,\,t_d\bigr)$$

with $t_d=\lfloor2d/5\rfloor$, which is $1$ for $d\in\{3,4\}$ and $0$ otherwise, exactly the rule of Section 4. Take $x=14$, $k=1$. Every allowed last digit leaves the bound $q_d=2$; digits $1$, $2$ spend no carry, digits $3$, $4$ spend one and pass it up. Here $F(2,1,0)=3$, as $0$, $1$, $2$ all qualify, while $F(2,0,1)=2$: doubling $2$ with a carry coming in gives $5$ and emits another. So

$$\begin{aligned}G(14,1)&=2F(2,1,0)+2F(2,0,1)\\ &=2\cdot3+2\cdot2=10,\end{aligned}$$

and indeed of the $m\le14$ coprime to $5$ only $13$ and $14$ need two carries.

10. Why the recursion has only a few hundred states

The recursion is cheap only because it reaches few different bounds $x$. Write $x=5q+r$ with $0\le r\le4$: then $q_d=q$ for $d\le r$ and $q_d=q-1$ for $d\gt r$, so the children of $x$ lie in $\{q-1,q\}$, and $q-1$ appears only when $r\le3$. Starting from a bound $X$, put $Y=\lfloor X/5^j\rfloor$ and $Z=\lfloor Y/5\rfloor=\lfloor X/5^{j+1}\rfloor$. ^[6] Suppose depth $j$ sees only $Y$ and $Y-1$. The children of $Y$ lie in $\{Z-1,Z\}$. If $Y\equiv0\pmod 5$ then $Y-1$ ends in the digit $4$ and $\lfloor(Y-1)/5\rfloor=Z-1$, so $Y-1$ has the single child $Z-1$; otherwise $\lfloor(Y-1)/5\rfloor=Z$ and its children again lie in $\{Z-1,Z\}$. So depth $j+1$ sees only $Z$ and $Z-1$.

So each starting bound contributes at most two bounds per depth. The nested-division identity $\lfloor\lfloor n/5^a\rfloor/5^j\rfloor=\lfloor n/5^{a+j}\rfloor$ makes the bounds reached from different $a$ coincide: every argument of the computation lies in $\{\lfloor n/5^t\rfloor-1,\lfloor n/5^t\rfloor\}$ for some $t\ge1$, at most $2\lfloor\log_5 n\rfloor+2$ values, which is $52$ for $n=10^{18}$; $49$ positive bounds actually occur across $F$ and $G$, besides the base case $0$. With $0\le k\le24$ and $t\in\{0,1\}$ the state count is $O(\log^2 n)$, and a memoised recursion ^[8] shared across all $a$ fills $714$ entries.

How the Code Works

All three programs implement Sections 7 and 9 directly. ^[9] In C++ the free function carry_out(digit, carry_in) returns $\lfloor(2d+t)/5\rfloor$, the rule of Section 4; Python defines it and the two counting helpers inside solve() over a fresh memo dictionary, Java as static methods with camel-case names. The walkthrough uses the C++ names.

count_with_initial_carry(x, k, carry_in) is $F$. It returns $0$ when x or k is negative, $1$ when x is $0$, and otherwise loops over digit from $0$ to $4$, breaking as soon as x < digit, which drops exactly the empty terms. In C++ and Java that break is load-bearing: (x - digit) / 5 truncates towards zero there, so without it the bound would come back as $0$ instead of negative and a nonexistent $y$ would be counted. Python's // floors, so its x < 0 guard catches the case anyway. Each surviving digit recurses on $\lfloor(x-d)/5\rfloor$ with the budget reduced by the outgoing carry. Results are memoised on the triple $(x,k,t)$: C++ needs a Key struct with operator== and a KeyHash for its unordered_map, Java an equals and hashCode pair for its HashMap, while Python's tuples are hashable already.

count_non_multiples_of_five(x, k) is $G$: the same loop with digit starting at $1$ and an incoming carry of $0$. Solver::solve(n) is the outer sum: it keeps power_of_five equal to $5^a$, adds count_non_multiples_of_five(n / power_of_five, a - 1), and breaks before multiplying whenever power_of_five exceeds n / 5, which both ends the loop in the right place and keeps $5^{a+1}$ from overflowing a signed 64-bit integer. Clearing the memo at the start of solve is not needed for correctness — $F$ depends only on its arguments — but bounds the table across repeated calls.

The C++ file accepts --n= for the bound and --skip-checkpoints to suppress the checks; its decimal parser has no overflow guard, so the bound must be a value a signed 64-bit integer can hold. It also adds two verification helpers: v5_factorial evaluates the floor sum of Section 1, and brute_force_count compares the two sides for every $i$ up to its argument. run_checkpoints then requires the fast method to return $68$ at $10^3$ and $2408210$ at $10^9$ and to agree with brute_force_count(20000). The Python and Java ports hold the recursion only: they fix $n=10^{18}$ and check nothing.

Integer width is settled before anything is computed. A value of $F$ counts a subset of $\{0,\dots,x\}$, so it is at most $x+1$; every bound here is at most $\lfloor n/5\rfloor$, and so is the total, since every qualifying index is a multiple of $5$. At the target that is $2\cdot10^{17}$, far below $2^{63}-1$, so C++'s i64 (an alias for long long) and Java's long are safe; Python's integers are unbounded. Two scope notes. v5_factorial returns an int: at the packaged bound $20000$ its largest result is $9994$ against a doubled right-hand side of $9998$, but the left-hand valuation first exceeds $2^{31}-1$ at $i=4294967308$, so the helper is for small checks only. And the memo key stores the raw budget k; capping it at the number of remaining base-$5$ digits merges states that must agree and cuts the $714$ entries to $358$, with the same result. Neither affects the computation as shipped.

Complexity and Verification

Let $A=\lfloor\log_5 n\rfloor$; the outer loop has $A$ iterations. By Section 10 the recursion has $O(A)$ bounds, $O(A)$ budgets and $2$ carry states, hence $O(A^2)$ states, each expanded once into at most five children. With expected constant-time table access it therefore costs $O(A^2)$ arithmetic and table operations and stores $O(A^2)$ entries, whose numbers have $O(A)$ bits. For $n=10^{18}$ that is $25$ outer terms, $714$ memo entries and $3551$ digit transitions, $99$ of them from the outer calls to $G$; on the machine used here all three programs finish in well under a second, the C++ binary with its checkpoints in about $0.2$ seconds. The brute force costs $\Theta(n\log n)$ digit operations and is hopeless at $10^{18}$.

These facts were verified by running code. For every $i\le200000$ the original inequality is equivalent to $c(i)\lt f_5(i)$, and $c(i)=0$ to every base-$5$ digit of $i$ being at most $2$; $c(i)=(2s_5(i)-s_5(2i))/4$ holds up to $i\le300000$ and $f_5(\binom{2i}{i})=c(i)$ up to $i\le3000$. The digit recursion matches a direct brute force for every bound $n\le399$ and at $n=1000$, $5000$, $20000$, $50000$ and $99999$, and a brute force built on Legendre's floor sum alone gives $T_5(10^6)=14878$, the same value. Reproduced too are $T_5(10^3)=68$, $T_5(10^9)=2408210$, $T_5(30)=4$, $T_5(100)=10$ and the four summands $36$, $24$, $7$, $1$ of Section 8. The three programs print the same value at $n=10^{18}$, and it agrees with a separately written implementation.

Two further values of the method are $T_5(10^{12})=558034846$ and $T_5(10^{15})=114888331746$. Deleting the digit break from a copy of the C++ source makes its $T_5(10^3)$ checkpoint fail, while the same deletion in Python leaves both checkpoints intact.

Footnotes and References

The references below supply the standard results used above. The reduction to $c(m)\le a-1$, the split by the power of $5$, the digit recursion and its state bound are derived explicitly here.

Project Euler 383 — Divisibility Comparison Between Factorials. The official statement defines f5(n) as the largest x with 5^x dividing n, defines T5(n) as the number of i in 1..n with f5((2i−1)!) < 2·f5(i!), and asks for T5(10^18) after stating the checkpoints T5(10^3) = 68 and T5(10^9) = 2408210, which test an implementation without disclosing the answer.
Wikipedia — p-adic valuation. The p-adic valuation of a nonzero integer is the exponent of the highest power of p dividing it, so it is the f5 of this problem for p = 5. The article states the additivity used in Section 2: the valuation of a product is the sum of those of its factors.
Wikipedia — Legendre's formula. Named after Adrien-Marie Legendre, it gives both forms used in Section 1: the valuation of n! equals the sum of the floors of n/p^i over i ≥ 1, and also (n − s_p(n))/(p − 1) with s_p(n) the base-p digit sum of n.
Wikipedia — Kummer's theorem. Proved by Ernst Kummer in 1852: the exponent of a prime p in C(n, m) equals the number of carries when m is added to n − m in base p, and equivalently (s_p(m) + s_p(n − m) − s_p(n))/(p − 1). Section 3 applies both forms with n = 2i and m = i, and proves that case directly.
Wikipedia — Central binomial coefficient. It defines C(2n, n) = (2n)!/(n!)^2, the quantity whose valuation appears in Section 2, and records the base-2 case of the carry rule: the number of factors 2 in C(2n, n) equals the number of ones in the binary expansion of n, that is, the carries of n + n in base 2.
Wikipedia — Floor and ceiling functions. Its "Nested divisions" subsection states that the floor of (the floor of x/m) divided by n equals the floor of x/(mn), the identity used in Section 10, and it records that the floor of x/d is fixed by division with remainder, used for the range of q in Section 9.
OEIS A037453. "Positive numbers whose base-5 representation contains no 3 or 4", beginning 1, 2, 5, 6, 7, 10, 11, 12, 25, 26, 27. These are exactly the m with c(m) = 0 of Section 4; with the auxiliary value a(0) = 0, the entry's recurrence a(3n+r) = 5·a(n) + r for r = 0, 1, 2 reads the base-3 expansion of the index as a base-5 numeral, which is why there are 3^k − 1 of them below 5^k.
Wikipedia — Memoization. Storing the results of a pure function in a lookup table so that a repeated call with the same arguments returns the stored value. The article calls it a space-time trade-off; here the traded space is tiny, because Section 10 bounds the number of distinct arguments.
C++ — Euler383.cpp. The linked immutable C++ revision contains carry_out, count_with_initial_carry, count_non_multiples_of_five, Solver::solve, v5_factorial, brute_force_count and run_checkpoints. It is the implementation record for this article; the comparisons under Complexity and Verification are extra validation, not checks packaged in that file.

Problem 383 source code

C++

#include <cstdint>
#include <iostream>
#include <string>
#include <unordered_map>

namespace {

using i64 = long long;

struct Options {
    i64 n = 1000000000000000000LL;
    bool run_checkpoints = true;
};

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

    i64 parsed = 0;
    for (char ch : tail) {
        if (ch < '0' || ch > '9') {
            return false;
        }
        parsed = parsed * 10 + static_cast<i64>(ch - '0');
    }
    value = parsed;
    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, "--n=", options.n)) {
            continue;
        }
        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }
    return options.n >= 1;
}

int carry_out(const int digit, const int carry_in) {
    return (2 * digit + carry_in) / 5;
}

struct Key {
    i64 x;
    int k;
    int carry_in;

    bool operator==(const Key& other) const {
        return x == other.x && k == other.k && carry_in == other.carry_in;
    }
};

struct KeyHash {
    std::size_t operator()(const Key& key) const {
        std::size_t h = std::hash<i64>{}(key.x);
        h ^= std::hash<int>{}(key.k) + 0x9e3779b97f4a7c15ULL + (h << 6) + (h >> 2);
        h ^= std::hash<int>{}(key.carry_in) + 0x9e3779b97f4a7c15ULL + (h << 6) + (h >> 2);
        return h;
    }
};

class Solver {
   public:
    i64 solve(const i64 n) {
        memo_.clear();
        i64 answer = 0;
        i64 power_of_five = 5;

        for (int a = 1; power_of_five <= n; ++a) {
            answer += count_non_multiples_of_five(n / power_of_five, a - 1);
            if (power_of_five > n / 5) {
                break;
            }
            power_of_five *= 5;
        }

        return answer;
    }

   private:
    std::unordered_map<Key, i64, KeyHash> memo_;

    i64 count_with_initial_carry(const i64 x, const int k, const int carry_in) {
        if (x < 0 || k < 0) {
            return 0;
        }
        if (x == 0) {
            // Only n=0 is present, and it contributes zero further carries.
            return 1;
        }

        const Key key{x, k, carry_in};
        const auto it = memo_.find(key);
        if (it != memo_.end()) {
            return it->second;
        }

        i64 ways = 0;
        for (int digit = 0; digit <= 4; ++digit) {
            if (x < digit) {
                break;
            }
            const i64 q = (x - digit) / 5;
            const int next_carry = carry_out(digit, carry_in);
            ways += count_with_initial_carry(q, k - next_carry, next_carry);
        }

        memo_[key] = ways;
        return ways;
    }

    i64 count_non_multiples_of_five(const i64 x, const int k) {
        if (x <= 0 || k < 0) {
            return 0;
        }
        i64 ways = 0;
        for (int digit = 1; digit <= 4; ++digit) {
            if (x < digit) {
                break;
            }
            const i64 q = (x - digit) / 5;
            const int next_carry = carry_out(digit, 0);
            ways += count_with_initial_carry(q, k - next_carry, next_carry);
        }
        return ways;
    }
};

int v5_factorial(i64 n) {
    int total = 0;
    while (n > 0) {
        n /= 5;
        total += static_cast<int>(n);
    }
    return total;
}

i64 brute_force_count(const i64 n) {
    i64 count = 0;
    for (i64 i = 1; i <= n; ++i) {
        const int lhs = v5_factorial(2 * i - 1);
        const int rhs = 2 * v5_factorial(i);
        if (lhs < rhs) {
            ++count;
        }
    }
    return count;
}

bool run_checkpoints() {
    Solver solver;

    if (solver.solve(1000) != 68LL) {
        std::cerr << "Checkpoint failed: T5(10^3)\n";
        return false;
    }

    if (solver.solve(1000000000LL) != 2408210LL) {
        std::cerr << "Checkpoint failed: T5(10^9)\n";
        return false;
    }

    const i64 brute_n = 20000;
    const i64 expected = brute_force_count(brute_n);
    const i64 got = solver.solve(brute_n);
    if (got != expected) {
        std::cerr << "Checkpoint failed against brute force at n=" << brute_n
                  << " (expected " << expected << ", got " << got << ")\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()) {
        return 2;
    }

    Solver solver;
    std::cout << solver.solve(options.n) << '\n';
    return 0;
}

Python

def solve():
    memo = {}

    def carry_out(digit, carry_in):
        return (2 * digit + carry_in) // 5

    def count_with_initial_carry(x, k, carry_in):
        if x < 0 or k < 0:
            return 0
        if x == 0:
            return 1

        key = (x, k, carry_in)
        if key in memo:
            return memo[key]

        ways = 0
        for digit in range(5):
            if x < digit:
                break
            q = (x - digit) // 5
            next_carry = carry_out(digit, carry_in)
            ways += count_with_initial_carry(q, k - next_carry, next_carry)

        memo[key] = ways
        return ways

    def count_non_multiples_of_five(x, k):
        if x <= 0 or k < 0:
            return 0
        ways = 0
        for digit in range(1, 5):
            if x < digit:
                break
            q = (x - digit) // 5
            next_carry = carry_out(digit, 0)
            ways += count_with_initial_carry(q, k - next_carry, next_carry)
        return ways

    n = 1000000000000000000
    answer = 0
    power_of_five = 5

    a = 1
    while power_of_five <= n:
        answer += count_non_multiples_of_five(n // power_of_five, a - 1)
        if power_of_five > n // 5:
            break
        power_of_five *= 5
        a += 1

    return str(answer)

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

Java

import java.util.HashMap;
import java.util.Map;

public class Euler383 {

    private static class Key {
        long x;
        int k;
        int carryIn;

        Key(long x, int k, int carryIn) {
            this.x = x;
            this.k = k;
            this.carryIn = carryIn;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o)
                return true;
            if (!(o instanceof Key))
                return false;
            Key key = (Key) o;
            return x == key.x && k == key.k && carryIn == key.carryIn;
        }

        @Override
        public int hashCode() {
            int result = (int) (x ^ (x >>> 32));
            result = 31 * result + k;
            result = 31 * result + carryIn;
            return result;
        }
    }

    private static final Map<Key, Long> memo = new HashMap<>();

    private static int carryOut(int digit, int carryIn) {
        return (2 * digit + carryIn) / 5;
    }

    private static long countWithInitialCarry(long x, int k, int carryIn) {
        if (x < 0 || k < 0)
            return 0;
        if (x == 0)
            return 1;

        Key key = new Key(x, k, carryIn);
        Long cached = memo.get(key);
        if (cached != null)
            return cached;

        long ways = 0;
        for (int digit = 0; digit <= 4; ++digit) {
            if (x < digit)
                break;
            long q = (x - digit) / 5;
            int nextCarry = carryOut(digit, carryIn);
            ways += countWithInitialCarry(q, k - nextCarry, nextCarry);
        }

        memo.put(key, ways);
        return ways;
    }

    private static long countNonMultiplesOfFive(long x, int k) {
        if (x <= 0 || k < 0)
            return 0;
        long ways = 0;
        for (int digit = 1; digit <= 4; ++digit) {
            if (x < digit)
                break;
            long q = (x - digit) / 5;
            int nextCarry = carryOut(digit, 0);
            ways += countWithInitialCarry(q, k - nextCarry, nextCarry);
        }
        return ways;
    }

    public static String solve() {
        memo.clear();
        long n = 1000000000000000000L;
        long answer = 0;
        long powerOfFive = 5;

        for (int a = 1; powerOfFive <= n; ++a) {
            answer += countNonMultiplesOfFive(n / powerOfFive, a - 1);
            if (powerOfFive > n / 5)
                break;
            powerOfFive *= 5;
        }

        return String.valueOf(answer);
    }

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