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

Problem 269 source code

C++

#include <array>
#include <cstdint>
#include <iostream>
#include <map>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>

namespace {

using u64 = std::uint64_t;

struct Options {
    int max_power = 16;
    bool run_checkpoints = true;
};

bool parse_int_after_prefix(const std::string& arg, const std::string& prefix, int& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }
    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }
    int parsed = 0;
    for (char c : tail) {
        if (c < '0' || c > '9') {
            return false;
        }
        parsed = parsed * 10 + static_cast<int>(c - '0');
    }
    value = parsed;
    return true;
}

bool parse_arguments(int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);
        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        if (parse_int_after_prefix(arg, "--power=", options.max_power)) {
            continue;
        }
        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }
    return options.max_power >= 1;
}

u64 pow10i(const int exp) {
    u64 value = 1;
    for (int i = 0; i < exp; ++i) {
        value *= 10;
    }
    return value;
}

u64 count_subset_for_length(const int length, const int last_digit, const std::vector<int>& roots) {
    if (roots.empty()) {
        return 0;
    }

    const int even_slots = (length + 1) / 2;
    const int msd_pos = length - 1;

    const std::vector<int> zero_state(static_cast<std::size_t>(roots.size()), 0);
    std::map<std::vector<int>, u64> states;
    states[zero_state] = 1;

    for (int j = 0; j < even_slots; ++j) {
        const int even_pos = 2 * j;
        const int odd_pos = 2 * j + 1;

        std::vector<int> even_digits;
        if (j == 0) {
            even_digits.push_back(last_digit);
        } else {
            even_digits.reserve(10);
            for (int d = 0; d <= 9; ++d) {
                even_digits.push_back(d);
            }
        }
        if (even_pos == msd_pos) {
            std::vector<int> filtered;
            filtered.reserve(even_digits.size());
            for (int d : even_digits) {
                if (d != 0) {
                    filtered.push_back(d);
                }
            }
            even_digits.swap(filtered);
        }

        std::vector<int> odd_digits;
        if (odd_pos >= length) {
            odd_digits.push_back(0);
        } else {
            odd_digits.reserve(10);
            for (int d = 0; d <= 9; ++d) {
                odd_digits.push_back(d);
            }
            if (odd_pos == msd_pos) {
                std::vector<int> filtered;
                filtered.reserve(odd_digits.size());
                for (int d : odd_digits) {
                    if (d != 0) {
                        filtered.push_back(d);
                    }
                }
                odd_digits.swap(filtered);
            }
        }

        std::map<std::vector<int>, u64> next_states;
        for (const auto& kv : states) {
            const std::vector<int>& carry = kv.first;
            const u64 ways = kv.second;

            for (int ed : even_digits) {
                for (int od : odd_digits) {
                    std::vector<int> next(carry.size(), 0);
                    bool ok = true;
                    for (std::size_t idx = 0; idx < roots.size(); ++idx) {
                        const int t = roots[idx];
                        const int denom = t * t;
                        const long long num = static_cast<long long>(t) * od + carry[idx] - ed;
                        if (num % denom != 0) {
                            ok = false;
                            break;
                        }
                        next[idx] = static_cast<int>(num / denom);
                    }
                    if (!ok) {
                        continue;
                    }
                    next_states[next] += ways;
                }
            }
        }

        states.swap(next_states);
        if (states.empty()) {
            return 0;
        }
    }

    const auto it = states.find(zero_state);
    return (it == states.end()) ? 0 : it->second;
}

u64 count_for_length(const int length) {
    u64 total = 0;

    // Root x=0: exactly numbers ending in zero.
    if (length >= 2) {
        total += 9ULL * pow10i(length - 2);
    }

    for (int d0 = 1; d0 <= 9; ++d0) {
        std::vector<int> divisors;
        for (int t = 1; t <= 9; ++t) {
            if (d0 % t == 0) {
                divisors.push_back(t);
            }
        }

        const int m = static_cast<int>(divisors.size());
        long long union_count = 0;
        for (int mask = 1; mask < (1 << m); ++mask) {
            std::vector<int> roots;
            roots.reserve(static_cast<std::size_t>(m));
            for (int i = 0; i < m; ++i) {
                if (((mask >> i) & 1) != 0) {
                    roots.push_back(divisors[static_cast<std::size_t>(i)]);
                }
            }

            const u64 cnt = count_subset_for_length(length, d0, roots);
            if ((__builtin_popcount(static_cast<unsigned int>(mask)) & 1) != 0) {
                union_count += static_cast<long long>(cnt);
            } else {
                union_count -= static_cast<long long>(cnt);
            }
        }

        total += static_cast<u64>(union_count);
    }

    return total;
}

u64 solve(const int max_power) {
    u64 total = 0;
    for (int len = 1; len <= max_power; ++len) {
        total += count_for_length(len);
    }

    // Add 10^max_power itself, which always has root x=0.
    total += 1;
    return total;
}

bool has_integer_root(u64 n) {
    std::vector<int> digits;
    while (n > 0) {
        digits.push_back(static_cast<int>(n % 10ULL));
        n /= 10ULL;
    }
    std::reverse(digits.begin(), digits.end());

    const int d0 = digits.back();
    std::vector<int> roots;
    if (d0 == 0) {
        roots.push_back(0);
    }
    for (int t = 1; t <= 9; ++t) {
        if (d0 % t == 0) {
            roots.push_back(-t);
        }
    }

    for (int r : roots) {
        long long value = 0;
        for (int d : digits) {
            value = value * static_cast<long long>(r) + d;
        }
        if (value == 0) {
            return true;
        }
    }
    return false;
}

u64 brute_count(const u64 limit) {
    u64 count = 0;
    for (u64 n = 1; n <= limit; ++n) {
        if (has_integer_root(n)) {
            ++count;
        }
    }
    return count;
}

bool run_checkpoints() {
    if (solve(3) != brute_count(1000)) {
        std::cerr << "Checkpoint failed for limit 1000" << '\n';
        return false;
    }
    if (solve(4) != brute_count(10000)) {
        std::cerr << "Checkpoint failed for limit 10000" << '\n';
        return false;
    }
    if (solve(5) != 14696ULL) {
        std::cerr << "Checkpoint failed for Z(100000)" << '\n';
        return false;
    }
    return true;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }
    if (options.run_checkpoints && !run_checkpoints()) {
        return 2;
    }
    std::cout << solve(options.max_power) << '\n';
    return 0;
}

Python

def pow10i(exp):
    return 10**exp

def count_subset_for_length(length, last_digit, roots):
    if not roots:
        return 0

    even_slots = (length + 1) // 2
    msd_pos = length - 1

    zero_state = tuple(0 for _ in roots)
    states = {zero_state: 1}

    for j in range(even_slots):
        even_pos = 2 * j
        odd_pos = 2 * j + 1

        if j == 0:
            even_digits = [last_digit]
        else:
            even_digits = list(range(10))

        if even_pos == msd_pos:
            even_digits = [d for d in even_digits if d != 0]

        if odd_pos >= length:
            odd_digits = [0]
        else:
            odd_digits = list(range(10))
            if odd_pos == msd_pos:
                odd_digits = [d for d in odd_digits if d != 0]

        next_states = {}
        for carry, ways in states.items():
            for ed in even_digits:
                for od in odd_digits:
                    next_carry = []
                    ok = True
                    for idx, t in enumerate(roots):
                        denom = t * t
                        num = t * od + carry[idx] - ed
                        if num % denom != 0:
                            ok = False
                            break
                        next_carry.append(num // denom)
                    
                    if not ok:
                        continue
                        
                    next_carry_tuple = tuple(next_carry)
                    next_states[next_carry_tuple] = next_states.get(next_carry_tuple, 0) + ways

        states = next_states
        if not states:
            return 0

    return states.get(zero_state, 0)

def count_for_length(length):
    total = 0
    if length >= 2:
        total += 9 * pow10i(length - 2)

    for d0 in range(1, 10):
        divisors = [t for t in range(1, 10) if d0 % t == 0]
        m = len(divisors)
        union_count = 0

        for mask in range(1, 1 << m):
            roots = []
            for i in range(m):
                if (mask >> i) & 1:
                    roots.append(divisors[i])

            cnt = count_subset_for_length(length, d0, roots)
            if mask.bit_count() & 1:
                union_count += cnt
            else:
                union_count -= cnt

        total += union_count

    return total

def solve_power(max_power):
    total = 0
    for length in range(1, max_power + 1):
        total += count_for_length(length)

    total += 1
    return total

def solve():
    ans = solve_power(16)
    return str(ans)

if __name__ == '__main__':
    print(solve())

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Euler269 {

    static long pow10i(int exp) {
        long value = 1;
        for (int i = 0; i < exp; i++)
            value *= 10;
        return value;
    }

    static class StateKey {
        int[] carry;

        StateKey(int[] c) {
            this.carry = c.clone();
        }

        @Override
        public boolean equals(Object o) {
            if (this == o)
                return true;
            if (o == null || getClass() != o.getClass())
                return false;
            StateKey stateKey = (StateKey) o;
            return Arrays.equals(carry, stateKey.carry);
        }

        @Override
        public int hashCode() {
            return Arrays.hashCode(carry);
        }
    }

    static long countSubsetForLength(int length, int lastDigit, List<Integer> roots) {
        if (roots.isEmpty())
            return 0;

        int evenSlots = (length + 1) / 2;
        int msdPos = length - 1;

        int[] zeroCarry = new int[roots.size()];
        StateKey zeroState = new StateKey(zeroCarry);
        Map<StateKey, Long> states = new HashMap<>();
        states.put(zeroState, 1L);

        for (int j = 0; j < evenSlots; j++) {
            int evenPos = 2 * j;
            int oddPos = 2 * j + 1;

            List<Integer> evenDigits = new ArrayList<>();
            if (j == 0) {
                evenDigits.add(lastDigit);
            } else {
                for (int d = 0; d <= 9; d++)
                    evenDigits.add(d);
            }
            if (evenPos == msdPos) {
                evenDigits.removeIf(d -> d == 0);
            }

            List<Integer> oddDigits = new ArrayList<>();
            if (oddPos >= length) {
                oddDigits.add(0);
            } else {
                for (int d = 0; d <= 9; d++)
                    oddDigits.add(d);
                if (oddPos == msdPos) {
                    oddDigits.removeIf(d -> d == 0);
                }
            }

            Map<StateKey, Long> nextStates = new HashMap<>();
            for (Map.Entry<StateKey, Long> entry : states.entrySet()) {
                int[] carry = entry.getKey().carry;
                long ways = entry.getValue();

                for (int ed : evenDigits) {
                    for (int od : oddDigits) {
                        int[] nextCarry = new int[roots.size()];
                        boolean ok = true;
                        for (int idx = 0; idx < roots.size(); idx++) {
                            int t = roots.get(idx);
                            int denom = t * t;
                            long num = (long) t * od + carry[idx] - ed;
                            if (num % denom != 0) {
                                ok = false;
                                break;
                            }
                            nextCarry[idx] = (int) (num / denom);
                        }
                        if (!ok)
                            continue;

                        StateKey nextKey = new StateKey(nextCarry);
                        nextStates.put(nextKey, nextStates.getOrDefault(nextKey, 0L) + ways);
                    }
                }
            }

            states = nextStates;
            if (states.isEmpty())
                return 0;
        }

        return states.getOrDefault(zeroState, 0L);
    }

    static long countForLength(int length) {
        long total = 0;
        if (length >= 2) {
            total += 9L * pow10i(length - 2);
        }

        for (int d0 = 1; d0 <= 9; d0++) {
            List<Integer> divisors = new ArrayList<>();
            for (int t = 1; t <= 9; t++) {
                if (d0 % t == 0)
                    divisors.add(t);
            }

            int m = divisors.size();
            long unionCount = 0;
            for (int mask = 1; mask < (1 << m); mask++) {
                List<Integer> roots = new ArrayList<>();
                for (int i = 0; i < m; i++) {
                    if (((mask >> i) & 1) != 0)
                        roots.add(divisors.get(i));
                }

                long cnt = countSubsetForLength(length, d0, roots);
                if ((Integer.bitCount(mask) & 1) != 0) {
                    unionCount += cnt;
                } else {
                    unionCount -= cnt;
                }
            }
            total += unionCount;
        }

        return total;
    }

    static long solve(int maxPower) {
        long total = 0;
        for (int len = 1; len <= maxPower; len++) {
            total += countForLength(len);
        }
        total += 1;
        return total;
    }

    public static void main(String[] args) {
        System.out.println(solve(16));
    }
}