Open Source · 7 Languages · 900+ Problems

Project Euler Solutions

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

All Problems

Problem 269: Polynomials with at Least One Integer Root

Project Euler Problem 269 Solution

EulerSolve provides an optimized solution for Project Euler Problem 269, Polynomials with at Least One Integer Root, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary Write a positive integer $n$ in decimal as $d_{L-1}d_{L-2}\dots d_1d_0$, with $d_{L-1}\neq0$. The problem associates to $n$ the polynomial $P_n(x)=d_{L-1}x^{L-1}+d_{L-2}x^{L-2}+\cdots+d_1x+d_0.$ We must count how many integers $1\le n\le10^{16}$ have the property that $P_n(x)$ has at least one integer root. Mathematical Approach 1. Candidate Integer Roots Are Extremely Limited Because every coefficient is a decimal digit, all coefficients are nonnegative and the leading coefficient is positive. Therefore $P_n(r)>0$ for every positive integer $r$. So positive roots are impossible. By the rational-root theorem, any integer root must divide the constant term $d_0$. Since $d_0\in\{0,1,\dots,9\}$, the only possibilities are: 1. $r=0$, which can happen only when $d_0=0$, 2. $r=-t$, where $t$ is a positive divisor of $d_0$, so $1\le t\le 9$. This is the first major reduction: the code never searches an unbounded root range. 2. The Root Condition for $r=-t$ Fix a candidate $t\ge1$. The condition $P_n(-t)=0$ is $\sum_{i=0}^{L-1} d_i(-t)^i=0.$ Group digits in pairs from the least significant side: $e_j=d_{2j},\qquad o_j=d_{2j+1},$ where a missing top odd digit is treated as $0$. Then $P_n(-t)=\sum_{j\ge0}(e_j-to_j)t^{2j}.$ The whole task is now to make those pair contributions cancel exactly. 3....

Detailed mathematical approach

Problem Summary

Write a positive integer $n$ in decimal as $d_{L-1}d_{L-2}\dots d_1d_0$, with $d_{L-1}\neq0$. The problem associates to $n$ the polynomial

$P_n(x)=d_{L-1}x^{L-1}+d_{L-2}x^{L-2}+\cdots+d_1x+d_0.$

We must count how many integers $1\le n\le10^{16}$ have the property that $P_n(x)$ has at least one integer root.

Mathematical Approach

1. Candidate Integer Roots Are Extremely Limited

Because every coefficient is a decimal digit, all coefficients are nonnegative and the leading coefficient is positive. Therefore $P_n(r)>0$ for every positive integer $r$. So positive roots are impossible.

By the rational-root theorem, any integer root must divide the constant term $d_0$. Since $d_0\in\{0,1,\dots,9\}$, the only possibilities are:

1. $r=0$, which can happen only when $d_0=0$,

2. $r=-t$, where $t$ is a positive divisor of $d_0$, so $1\le t\le 9$.

This is the first major reduction: the code never searches an unbounded root range.

2. The Root Condition for $r=-t$

Fix a candidate $t\ge1$. The condition $P_n(-t)=0$ is

$\sum_{i=0}^{L-1} d_i(-t)^i=0.$

Group digits in pairs from the least significant side:

$e_j=d_{2j},\qquad o_j=d_{2j+1},$

where a missing top odd digit is treated as $0$. Then

$P_n(-t)=\sum_{j\ge0}(e_j-to_j)t^{2j}.$

The whole task is now to make those pair contributions cancel exactly.

3. The Carry Recurrence Used by the Code

The implementation introduces carry values $c_j$ and enforces

$e_j-to_j=c_j-t^2c_{j+1},\qquad c_0=0.$

Solving for the next carry gives the exact transition used in C++:

$c_{j+1}=\frac{to_j+c_j-e_j}{t^2}.$

This transition is valid only if the numerator is divisible by $t^2$. That divisibility check is the key filter in the DP.

Why does this work? Summing over all processed pairs gives a telescoping identity:

$\sum_{j=0}^{s-1}(e_j-to_j)t^{2j} =\sum_{j=0}^{s-1}(c_j-t^2c_{j+1})t^{2j} =c_0-t^{2s}c_s.$

Since $c_0=0$, we obtain $P_n(-t)=0$ exactly when the final carry also returns to zero. So the DP only needs to remember the current carry, not the whole partial polynomial value.

4. A Small Worked Example

Take $n=121$. Then

$P_n(x)=x^2+2x+1=(x+1)^2,$

so $r=-1$ is a root. Here $t=1$, and the digit pairs from the right are

$ (e_0,o_0)=(1,2),\qquad (e_1,o_1)=(1,0). $

Starting from $c_0=0$, the recurrence gives

$c_1=\frac{1\cdot2+0-1}{1^2}=1,\qquad c_2=\frac{1\cdot0+1-1}{1^2}=0.$

The final carry is $0$, so the root condition is satisfied.

An even shorter example is $n=24$, where $P_n(x)=2x+4$ and $r=-2$. With $t=2$, $(e_0,o_0)=(4,2)$, and

$c_1=\frac{2\cdot2+0-4}{2^2}=0.$

Again the final carry is zero, so the DP accepts the number.

5. Why Dynamic Programming Is Enough

For a fixed length $L$, fixed last digit $d_0$, and fixed candidate root $-t$, the next carry depends only on:

1. the current carry $c_j$,

2. the chosen even digit $e_j$,

3. the chosen odd digit $o_j$.

Therefore the number of valid prefixes can be counted with a finite-state DP over carry values. This replaces a brute-force scan over all $10^L$ numbers.

The code processes digits in pair-blocks. Whenever the most significant digit lies in the currently chosen even or odd slot, zero is removed from the allowed digit set so that leading zeros never occur.

6. Multiple Root Candidates and Inclusion-Exclusion

For a fixed last digit $d_0\neq0$, the possible positive divisors $t\mid d_0$ form a very small set. The largest cases are $d_0=6$ and $d_0=8$, each having only four divisors, so there are at most $2^4-1=15$ nonempty subsets to consider.

For each subset of candidate roots, the DP carries a whole vector

$\bigl(c_j^{(t_1)},c_j^{(t_2)},\dots\bigr)$

and counts numbers that satisfy all those root conditions simultaneously. Then inclusion-exclusion turns those intersection counts into the number of integers with at least one integer root.

A simple overlap example is $n=132$:

$P_n(x)=x^2+3x+2=(x+1)(x+2).$

So the number belongs to the count for root $-1$, also to the count for root $-2$, and once more to their intersection. Inclusion-exclusion makes sure it is counted only once in the final union.

7. Root $0$ Is Handled Separately

If $d_0=0$, then $x=0$ is automatically a root. The code handles this case directly instead of mixing it into the inclusion-exclusion over negative roots.

For length $L\ge2$, the count of positive $L$-digit numbers ending in $0$ is simply

$9\cdot10^{L-2},$

because the first digit has $9$ choices, the middle $L-2$ digits are free, and the last digit is fixed to $0$.

8. Length Handling and the Endpoint $10^{16}$

The function solve(max_power) sums over all decimal lengths $1,2,\dots,\texttt{max\_power}$. That counts exactly the integers from $1$ up to $10^{\texttt{max\_power}}-1$.

Then the code adds one more number:

$10^{\texttt{max\_power}},$

which always has root $x=0$, because its last digit is $0$.

9. Small Checkpoints

The implementation validates itself with three checkpoints:

1. solve(3) must equal the brute-force count up to $1000$, which is $172$,

2. solve(4) must equal the brute-force count up to $10000$, which is $1754$,

3. solve(5) must equal $14696$, the published value $Z(10^5)$.

These checks confirm all layers of the method: root restriction, carry DP, inclusion-exclusion, and length accounting.

How the Code Works

count_subset_for_length(length, last_digit, roots) runs the pairwise DP for one intersection of root conditions. Its state map stores vectors of current carries and the number of digit assignments reaching each state.

count_for_length(length) first adds the direct contribution from root $0$, then loops over last digits $1$ to $9$, builds the divisor list of $d_0$, iterates over all nonempty subsets of those divisors, and applies inclusion-exclusion.

solve(max_power) sums all lengths and finally adds $10^{\texttt{max\_power}}$ itself.

The command line accepts --power=<k> and --skip-checkpoints.

Complexity Analysis

The maximum number of decimal lengths is only $16$. For each last digit, the divisor set has size at most $4$, so subset enumeration is tiny. The real cost comes from how many carry states are reachable, but these state spaces stay small in practice.

That makes the algorithm vastly faster than any direct iteration over all numbers up to $10^{16}$.