Project Euler Problem 269
A root or zero of a polynomial P(x) is a solution to the equation P(x) = 0.
Solution
Answer: 1311109198529286
Let
$$P_n(x)=a_mx^m+a_{m-1}x^{m-1}+\cdots+a_0$$
where $a_ma_{m-1}\cdots a_0$ are the decimal digits of $n$.
We seek
$$Z(10^{16})$$
= the number of positive integers $n\le 10^{16}$ such that $P_n(x)$ has at least one integer root.
1. Mathematical analysis
Step 1: Restrict the possible integer roots
Since the coefficients are digits $0,\dots,9$, all coefficients are nonnegative and the leading coefficient is positive.
If $r>0$, then
$$P_n(r)>0$$
because every term is nonnegative and the leading term is positive.
So positive roots are impossible.
By the integer root theorem, any integer root must divide the constant term (last digit), hence any integer root must lie in
$${0,-1,-2,\dots,-9}.$$
So there are only 10 candidate roots.
Step 2: Reformulate polynomial evaluation
Suppose the decimal digits of $n$ are
$$d_1d_2\cdots d_L.$$
Then
$$P_n(r) = (((d_1r+d_2)r+d_3)\cdots)r+d_L.$$
This is a Horner recurrence.
We want:
$$P_n(r)=0.$$
For a fixed root $r$, define states backwards:
If after some suffix we need value $t$, then the previous state $p$ must satisfy
$$pr+d=t.$$
Thus
$$p=\frac{t-d}{r}.$$
For each digit $d\in{0,\dots,9}$, this predecessor is either uniquely determined or impossible.
This makes dynamic programming very efficient.
Step 3: Inclusion–exclusion
We need numbers whose polynomial has at least one integer root among
$$R={0,-1,-2,\dots,-9}.$$
For any subset $S\subseteq R$, let $N(S)$ be the number of integers whose polynomial vanishes at every root in $S$.
Then by inclusion–exclusion:
$$Z = \sum_{\emptyset\neq S\subseteq R} (-1)^{|S|+1}N(S).$$
There are only
$$2^{10}-1=1023$$
nonempty subsets, so this is feasible.
2. Python implementation
from functools import lru_cache
# Candidate integer roots:
# index 0 -> root 0
# index i -> root -i for i=1..9
ROOTS = [0] + [-i for i in range(1, 10)]
cache = {}
def count_subset(mask, length):
"""
Count length-digit numbers whose polynomial
vanishes at every root specified by 'mask'.
"""
key = (mask, length)
if key in cache:
return cache[key]
# Root 0 means last digit must be 0
need_zero_root = (mask & 1) != 0
# Negative roots included in this subset
roots = [-i for i in range(1, 10) if (mask >> i) & 1]
@lru_cache(None)
def dp(rem_digits, targets):
"""
rem_digits = number of digits still to place
targets = tuple of required evaluation states
for each root
"""
if rem_digits == 0:
return 1 if all(t == 0 for t in targets) else 0
total = 0
for d in range(10):
# Leading digit cannot be zero
if rem_digits == 1 and d == 0:
continue
# Root 0 condition: LSD must be zero
if need_zero_root and rem_digits == length and d != 0:
continue
prev_states = []
ok = True
# Backward transition:
# p * r + d = target
for r, t in zip(roots, targets):
numerator = t - d
if numerator % r != 0:
ok = False
break
prev_states.append(numerator // r)
if ok:
total += dp(rem_digits - 1, tuple(prev_states))
return total
result = dp(length, tuple([0] * len(roots)))
cache[key] = result
return result
def compute_Z(limit_power):
total = 0
# Count numbers < 10^limit_power
for length in range(1, limit_power + 1):
union_count = 0
for mask in range(1, 1 << 10):
c = count_subset(mask, length)
# Inclusion–exclusion
if mask.bit_count() % 2 == 1:
union_count += c
else:
union_count -= c
total += union_count
# Add 10^16 itself
# P_{10^16}(x) = x^16, root x=0
total += 1
return total
print(compute_Z(16))
3. Code walkthrough
Candidate roots
We only test
$$0,-1,-2,\dots,-9$$
because no other integer roots are possible.
count_subset(mask, length)
This counts $L$-digit numbers whose polynomial vanishes at all roots in a subset.
A bitmask encodes the subset.
Example:
- bit 0 → root $0$
- bit 1 → root $-1$
- bit 2 → root $-2$
etc.
Dynamic programming
We build the number backwards from the least significant digit.
Suppose we currently require:
$$P(r)=t.$$
Choosing digit $d$ forces the predecessor state:
$$p=\frac{t-d}{r}.$$
If not divisible, that digit is impossible.
Memoization makes repeated states extremely fast.
Inclusion–exclusion
We sum over all nonempty subsets:
$$\sum (-1)^{|S|+1}N(S).$$
This correctly counts numbers having at least one integer root.
4. Verification
The problem gives:
$$Z(100000)=14696.$$
Running the same algorithm for $10^5$ reproduces exactly:
$$14696.$$
So the implementation matches the provided check.
The final computation for $10^{16}$ gives:
$$1311109198529286.$$
This magnitude is sensible: among $10^{16}$ numbers, roughly $13%$ satisfy at least one integer-root condition.
Answer: 1311109198529286