Problem Summary

Let \(T(m,n)\) be the number of binomial coefficients

$$\binom{i}{n}$$

that are divisible by \(10\), for

$$n\le i\lt m.$$

We are given

$$T(10^9,10^7-10)=989697000,$$

and we must compute

$$T(10^{18},10^{12}-10).$$

Mathematical Approach

1) Shift from \(i\) to \(x=i-n\).

Write

$$i=n+x,$$

so \(x\) runs through

$$0\le x\lt L,\qquad L=m-n.$$

Then the problem is to count how many values of

$$\binom{n+x}{n}$$

are divisible by \(10\).

2) Divisible by \(10\) means divisible by both \(2\) and \(5\).

So we study the prime valuations

$$v_2\!\left(\binom{n+x}{n}\right),\qquad v_5\!\left(\binom{n+x}{n}\right).$$

The coefficient is divisible by \(10\) exactly when both are positive.

3) Kummer's theorem turns valuations into carry counts.

For a prime \(p\), Kummer says

$$v_p\!\left(\binom{n+x}{n}\right)=\text{number of carries when adding }n\text{ and }x\text{ in base }p.$$

Therefore

$$\binom{n+x}{n}\not\equiv0\pmod p$$

if and only if the base-\(p\) addition \(n+x\) has no carry at all.

4) No-carry condition as a digit inequality.

Let the base-\(p\) digits be

$$n=\sum n_j p^j,\qquad x=\sum x_j p^j.$$

No carry is equivalent to

$$n_j+x_j\le p-1\qquad\text{for every }j,$$

or, equivalently,

$$x_j\le p-1-n_j\qquad\text{for every digit }j.$$

This is the Lucas-style digit condition used by the code.

5) Inclusion-exclusion for divisibility by \(10\).

Among the \(L\) candidates \(x\in[0,L)\), define:

$$A_2=\#\{x : \binom{n+x}{n}\not\equiv0\pmod2\},$$

$$A_5=\#\{x : \binom{n+x}{n}\not\equiv0\pmod5\},$$

$$A_{2,5}=\#\{x : \binom{n+x}{n}\text{ is coprime to }10\}.$$

Then the number divisible by \(10\) is

$$T(m,n)=L-A_2-A_5+A_{2,5}.$$

So the hard part is to count the non-divisible cases efficiently.

6) Counting \(A_p\) with digit DP.

To count \(A_p\), we must count numbers \(x\) with

$$0\le x\lt L$$

such that every base-\(p\) digit satisfies

$$x_j\le p-1-n_j.$$

This is a standard digit-DP with two states:

tight: the prefix of \(x\) already matches the upper bound \(L-1\),

loose: the prefix is already smaller, so later digits are free up to their carry cap.

The code performs exactly this DP for \(p=2\) and \(p=5\).

7) Special simplification in base \(2\).

In base \(2\), the digit condition becomes:

if a bit of \(n\) is \(1\), the corresponding bit of \(x\) must be \(0\). Hence no-carry in base \(2\) is equivalent to the bitwise condition

$$(x\ \&\ n)=0.$$

The overlap stage of the program uses this extremely cheap test.

8) Counting the overlap \(A_{2,5}\).

This is the set of \(x\lt L\) that satisfy both:

1) no carry in base \(5\),

2) no carry in base \(2\).

The code chooses base \(5\) as the primary generator. It enumerates exactly those \(x\) whose base-5 digits respect

$$x_j\le 4-n_j^{(5)},$$

and then filters them using

$$(x\ \&\ n)=0.$$

To keep this feasible at huge bounds, the base-5 digits are split into low and high blocks, generating two smaller lists whose combinations cover all candidates under \(x\lt L\).

9) Small sanity check.

For small values, the code compares the fast method against a brute-force valuation computation using

$$v_p\!\left(\binom{i}{n}\right)=v_p(i!)-v_p(n!)-v_p((i-n)!).$$

This confirms that the carry-based counting and the inclusion-exclusion formula agree exactly.

Algorithm

1) Set \(L=m-n\) and count all \(x\in[0,L)\).

2) Compute \(A_2\) by digit-DP in base \(2\).

3) Compute \(A_5\) by digit-DP in base \(5\).

4) Compute \(A_{2,5}\) by generating base-5-valid candidates and filtering them with \((x\&n)=0\).

5) Return

$$T(m,n)=L-A_2-A_5+A_{2,5}.$$

Complexity Analysis

The single-prime counts \(A_2\) and \(A_5\) are essentially linear in the number of digits. The expensive part is \(A_{2,5}\), but the split-by-block strategy avoids scanning the full interval \([0,L)\), which would be impossible for \(10^{18}\)-scale bounds.

Checks And Final Result

The implementation checks the given sample

$$T(10^9,10^7-10)=989697000,$$

and also cross-checks several smaller cases against brute force.

The final answer is

$$T(10^{18},10^{12}-10)=999998760323313995.$$

Further Reading

1. Problem page: https://projecteuler.net/problem=322
2. Kummer's theorem: https://en.wikipedia.org/wiki/Kummer's_theorem
3. Lucas's theorem: https://en.wikipedia.org/wiki/Lucas's_theorem