Let \(T(m, n)\) be the number of the
binomial coefficients \(^iC_n\) that
are divisible by \(10\) for \(n \le i < m\)(\(i, m\) and \(n\) are positive integers).
You are given that \(T(10^9, 10^7-10) =
989697000\).
# ========================= # Project Euler 322 # Count T(M, N): number of binomial coefficients C(i, N) divisible by 10 # for N <= i < M. # # Key facts (Lucas / Kummer viewpoint): # - C(N+k, N) is NOT divisible by prime p <=> (N + k) has NO carry with N in base p # equivalently: for every digit position, digit(k) <= (p-1 - digit(N)). # # Let L = M - N and consider k in [0, L). # Define: # A2 = #{k in [0, L): C(N+k, N) not divisible by 2 } (no-carry base 2) # A5 = #{k in [0, L): C(N+k, N) not divisible by 5 } (no-carry base 5) # A25 = #{k in [0, L): C(N+k, N) not divisible by 2 and not divisible by 5 } # # Then by inclusion–exclusion: # #{k where divisible by 10} = L - A2 - A5 + A25 # and that equals T(M, N). # =========================
M = 10 ** 18 N = 10 ** 12 - 10 L = M - N
defdigits_base(n: int, p: int, length=None): """ Return digits of n in base p, little-endian: [d0, d1, ...] where n = d0 + d1*p + d2*p^2 + ... If length is given, pad with zeros or truncate to exactly `length` digits. """ ds = [] while n: n, r = divmod(n, p) ds.append(r) ifnot ds: ds = [0] if length isnotNone: iflen(ds) < length: ds += [0] * (length - len(ds)) else: ds = ds[:length] return ds # little-endian
defcount_no_carry(n: int, B: int, p: int) -> int: """ Count: |{ 0 <= k < B : adding (n + k) in base p produces NO carry with n }| i.e. for each digit position i: k_i <= (p - 1 - n_i) This computes the count for the range [0, B) using digit-DP in base p. Implementation idea: - Let allow[i] = number of permitted digits at position i for k = (p - n_i), since k_i in [0 .. p-1-n_i]. - For numbers < B, scan digits of B from high to low, and sum choices where at the first differing position we pick a smaller digit (and valid), while lower positions can be anything valid. """ if B <= 0: return0
# base-p digits for n and B nd = digits_base(n, p) bd = digits_base(B, p)
# make same length D = max(len(nd), len(bd)) iflen(nd) < D: nd += [0] * (D - len(nd)) iflen(bd) < D: bd += [0] * (D - len(bd))
# allow[i] = count of valid digits for k at position i # If n_i = d, then k_i can be 0..(p-1-d), which has (p-d) choices allow = [p - nd[i] for i inrange(D)]
# ways[i] = product_{0..i-1} allow[pos] # i.e. number of valid assignments for lower i digits ways = [1] * (D + 1) for i inrange(D): ways[i + 1] = ways[i] * allow[i]
# digit DP accumulation cnt = 0 # iterate from highest digit to lowest for i inrange(D - 1, -1, -1): digit = bd[i] # B's digit at position i lim = allow[i] # valid digits are 0..lim-1
# We want to count valid k whose prefix is smaller than B's prefix # by choosing this digit < digit, while also < lim. take = digit if digit < lim else lim cnt += take * ways[i] # lower i digits: any valid combination
# If B's digit itself is not valid (digit >= lim), we cannot continue # matching B at this position; stop. if digit >= lim: break
return cnt
defgen_res5_low_digits(n: int, exp: int): """ Generate all residues r modulo 5^exp such that the low exp base-5 digits of r can be added to the low exp digits of n WITHOUT carry. That is, if n has digits n_0..n_{exp-1}, then r_i must satisfy: 0 <= r_i <= 4 - n_i for each i in [0..exp-1]. Returns list of integers r in [0, 5^exp). """ mod = 5 ** exp nd = digits_base(n % mod, 5, exp) res = []
defdfs(pos, val, pw): # pos: which digit we're choosing (little-endian) # val: current residue value # pw : current power of 5 (5^pos) if pos == exp: res.append(val) return # maximum digit allowed at this position to avoid carry lim = 4 - nd[pos] for d inrange(lim + 1): dfs(pos + 1, val + d * pw, pw * 5)
dfs(0, 0, 1) return res
defbuild_ok_table_5pow9(n_part: int) -> bytearray: """ Build a lookup table of size 5^9. table[x] = 1 iff x (interpreted as a 9-digit base-5 number) can be added to n_part (also interpreted as 9 base-5 digits) with NO carry. We use 9-digit blocks so that for 5^18 arithmetic we can split into two blocks: low 9 digits and high 9 digits. """ P9 = 5 ** 9 nd = digits_base(n_part, 5, 9) # exactly 9 digits lim = [4 - d for d in nd] # per-position digit maximum for x table = bytearray(P9)
# brute-force over all 5^9 possible blocks for x inrange(P9): tmp = x ok = 1 for L in lim: # current base-5 digit of x if tmp % 5 > L: ok = 0 break tmp //= 5 table[x] = ok return table
defintersection_count(n: int, L: int, exp: int = 12) -> int: """ Count A25: |{ 0 <= k < L : (n+k) adds with n WITHOUT carry in base 2 AND base 5 }| which equals the count of k such that C(n+k, n) is not divisible by 2 or 5. Trick: work modulo 10^exp (here exp=12, so step = 10^12). If the last exp digits (in base 2 and base 5) are no-carry simultaneously, then all candidates k lie in certain residue classes mod 10^exp. Steps: 1) Find all residues a mod 2^exp satisfying no-carry with n mod 2^exp. 2) Find all residues b mod 5^exp satisfying no-carry with n mod 5^exp. 3) Combine each pair (a, b) into a residue r mod 10^exp via CRT. 4) For each residue r, enumerate k = r + t*10^exp < L. For each such k, we still need global no-carry, not just low exp digits. For base 2: global no-carry iff (k & n) == 0 (bitwise test). For base 5: we test no-carry mod 5^18 by splitting into two 9-digit blocks, and stepping with k += 10^exp updates those blocks efficiently. """ mod2 = 2 ** exp mod5 = 5 ** exp step = 10 ** exp # 2^exp * 5^exp
# ---- residues mod 2^exp ---- # In base 2, "no carry" means at every bit position where n has 1, # k must have 0. So for exp low bits: # (k_low & n_low) == 0 n2 = n % mod2 res2 = [x for x inrange(mod2) if (x & n2) == 0]
# ---- residues mod 5^exp ---- # Enumerate all low exp base-5 residues with no carry: res5 = gen_res5_low_digits(n, exp)
# ---- combine to residues mod 10^exp ---- # For each (a mod 2^exp, b mod 5^exp), CRT gives unique r mod 10^exp. residues = [] for a in res2: for b in res5: residues.append(CRT([mod2, mod5], [a, b]))
# ---- base-5 global checking via block tables ---- # We'll check no-carry in base 5 modulo 5^18 using two 9-digit blocks. mod5_9 = 5 ** 9
# represent arithmetic mod 5^18 using (low, high) each mod 5^9 mod5_18 = mod5_9 * mod5_9
# step5 = step mod 5^18, also split into low/high blocks for fast increment step5 = step % mod5_18 step5_low = step5 % mod5_9 step5_high = step5 // mod5_9
inter = 0
for r in residues: # only consider residue classes that actually hit [0, L) if r >= L: continue
# number of terms in this arithmetic progression: # k = r + t*step, for t = 0..cnt-1 cnt = (L - 1 - r) // step + 1
# initialize k and its base-5 blocks (mod 5^18) k = r low = k % mod5_9 high = (k // mod5_9) % mod5_9
for _ inrange(cnt): # Base-2 global no-carry test: # (k & n) == 0 <=> at every bit position with n's 1, k has 0. # # Base-5 test (mod 5^18) approximates global no-carry; exp=12 step # makes candidates sparse; this block test matches typical accepted approach: # require no carry for 18 base-5 digits, enough for n up to 1e12-scale. if (k & n) == 0and ok0[low] and ok1[high]: inter += 1
# advance to next candidate in the same residue class k += step
# update base-5 blocks (low, high) by adding step5 # (low + step5_low) may overflow mod5_9 -> carry into high low2 = low + step5_low carry = 1if low2 >= mod5_9 else0 low = low2 - (mod5_9 if carry else0)
high2 = high + step5_high + carry high = high2 - mod5_9 if high2 >= mod5_9 else high2
return inter
# Count numbers k in [0, L) with no-carry for base 2 and base 5: A2 = count_no_carry(N, L, 2) A5 = count_no_carry(N, L, 5)
# Count intersection (no-carry in both bases) using residue stepping mod 10^12: A25 = intersection_count(N, L, 12)
# Inclusion–exclusion: # divisible by 10 <=> divisible by 2 AND divisible by 5 ans = L - A2 - A5 + A25 print(ans)