Problem Summary

Let \(S(n)\) denote the number of integers

$$0 \le x < 10^n$$

whose decimal digit sum is \(23\) and which are divisible by \(23\). Leading zeros are therefore allowed in the \(n\)-digit representation, which matches the code. The Project Euler target is \(S(11^{12}) \bmod 10^9\).

Mathematical Approach

1. Writing the two conditions in digit form

Write

$$x = \sum_{i=0}^{n-1} d_i 10^i,\qquad 0 \le d_i \le 9,$$

where \(d_0\) is the units digit. Then the problem imposes two simultaneous constraints:

$$\sum_{i=0}^{n-1} d_i = 23,$$

$$\sum_{i=0}^{n-1} d_i 10^i \equiv 0 \pmod{23}.$$

A direct dynamic program over all \(n\) positions would be impossible for \(n = 11^{12}\), so the key is to compress positions that behave identically modulo \(23\).

2. Why positions fall into 22 residue classes

Modulo \(23\), powers of \(10\) repeat with period \(22\), because

$$10^{22} \equiv 1 \pmod{23}.$$

Therefore, if two positions satisfy \(i \equiv j \pmod{22}\), then

$$10^i \equiv 10^j \pmod{23}.$$

So all digits sitting in the same residue class modulo \(22\) contribute to divisibility by the same weight. Define

$$w_c = 10^c \bmod 23,\qquad c=0,1,\ldots,21.$$

If \(n = 22q + r\) with \(0 \le r < 22\), then class \(c\) contains

$$u_c = \begin{cases} q+1, & c < r, \\ q, & c \ge r. \end{cases}$$

For example, if \(n=25\), then \(q=1\), \(r=3\), so classes \(0,1,2\) contain two positions each, while the other \(19\) classes contain one position each.

3. Reducing each class to its digit sum

Inside one class \(c\), suppose the digits in that class add up to \(k\). Then their total contribution modulo \(23\) is simply

$$k\,w_c \pmod{23},$$

because every position in that class carries the same weight \(w_c\). So we do not need the full digit pattern of the class; we only need to know how many assignments produce class sum \(k\).

For a class of size \(u\), the generating polynomial is

$$G_u(x) = (1+x+x^2+\cdots+x^9)^u.$$

The coefficient \([x^k]G_u(x)\) is exactly the number of ways to place \(u\) digits from \(0\) to \(9\) whose sum is \(k\).

Because the global digit sum is only \(23\), coefficients above degree \(23\) can never matter. So the code truncates every polynomial to degree \(23\), turning the huge exponent \(u\) into a manageable binary-exponentiation problem.

4. Why only two class polynomials are needed

Every class size is either \(q\) or \(q+1\). Therefore we only need the two truncated polynomials

$$G_q(x) = (1+x+\cdots+x^9)^q,$$

$$G_{q+1}(x) = (1+x+\cdots+x^9)^{q+1},$$

both computed modulo \(10^9\). The function poly_pow_digit_sum does this by repeated squaring, and the multiplication routine discards all terms above \(x^{23}\).

5. DP over classes: total digit sum and remainder mod 23

After compressing each residue class into “choose a class sum \(k\) with multiplicity \([x^k]G_{u_c}(x)\)”, the problem becomes a 22-step dynamic program. Let

$$DP[s][t]$$

be the number of ways, after processing some classes, to obtain total digit sum \(s\) and remainder \(t \pmod{23}\).

When processing class \(c\), choosing class sum \(k\) produces the transition

$$s' = s+k,\qquad t' = (t + w_c k) \bmod 23.$$

The multiplicity of this transition is \([x^k]G_{u_c}(x)\). After all \(22\) classes have been processed, the desired count is

$$DP[23][0].$$

This is the whole reason the huge value of \(n\) becomes harmless: the algorithm never iterates over all positions, only over the \(22\) residue classes.

6. Checks and interpretation

The implementation verifies itself with three checkpoints:

$$S(9)=263626,$$

$$S(42)=6377168878570056,$$

and a consistency check that the compressed class DP matches a direct position-by-position DP for

$$n=200.$$

The direct DP is only feasible for moderate \(n\), but it is an excellent validation tool: it confirms that grouping positions by residue modulo \(22\) loses no information.

How the Code Works

poly_mul_mod multiplies two digit-sum polynomials and truncates to degree \(23\). poly_pow_digit_sum raises \(1+x+\cdots+x^9\) to exponent \(q\) or \(q+1\) by binary exponentiation. count_via_classes_mod builds the \(22\) modular weights \(w_c\), runs the DP over \((\text{digit sum}, \text{remainder})\), and returns \(DP[23][0]\). The functions direct_count_exact and direct_count_mod are only for checkpoints on smaller \(n\).

Complexity Analysis

Polynomial multiplication is on vectors of length \(24\), so one multiplication costs \(O(23^2)\). Binary exponentiation therefore costs

$$O(23^2 \log n).$$

The class DP visits \(22\) classes, \(24\) digit-sum states, \(23\) remainders, and up to \(24\) class-sum choices, so its cost is

$$O(22 \cdot 23^3),$$

which is effectively constant for this fixed target sum. Memory usage is \(O(23^2)\).

Further Reading

1. Problem page: https://projecteuler.net/problem=294
2. Generating functions in combinatorics: https://en.wikipedia.org/wiki/Generating_function
3. Modular arithmetic and multiplicative order: https://en.wikipedia.org/wiki/Multiplicative_order