Open Source · 7 Languages · 900+ Problems

Project Euler Solutions

Complete solutions in C++, Python & Java — with step-by-step mathematical explanations

All Problems

Problem 322: Binomial Coefficients Divisible by 10

Project Euler Problem 322 Solution

EulerSolve provides an optimized solution for Project Euler Problem 322, Binomial Coefficients Divisible by 10, with C++, Python, Java, and a step-by-step mathematical explanation.

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$....

Detailed mathematical approach

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