Detailed mathematical approach

Problem Summary

Define

$F(m,n)=\left|\left\{(a_1,\dots,a_n)\in \mathbb{Z}_{>0}^n:\prod_{i=1}^{n} a_i \le m\right\}\right|.$

The task is to evaluate \(F(10^9,10^9)\) modulo \(1234567891\). The published checkpoints are

$F(10,10)=571,\qquad F(10^6,10^6)\equiv 252903833 \pmod{1234567891}.$

A direct enumeration of \(10^9\)-tuples is impossible, so the solution has to exploit the multiplicative structure of the product bound.

Mathematical Approach

Step 1: Dynamic Programming on the Remaining Product Budget

For a fixed tuple length \(t\), let

$P_t(v)=F(v,t).$

When \(t=0\), there is exactly one admissible tuple: the empty tuple. Therefore

$P_0(v)=1\qquad (v\ge 1).$

For \(t\ge 1\), choose the first entry \(x=a_1\). Once \(x\) is fixed, the remaining \(t-1\) entries must satisfy

$a_2a_3\cdots a_t \le \left\lfloor \frac{v}{x}\right\rfloor.$

This gives the exact recurrence

$P_t(v)=\sum_{x=1}^{v} P_{t-1}\!\left(\left\lfloor \frac{v}{x}\right\rfloor\right).$

That identity is the backbone of all three implementations: the problem is transformed into repeated sums over floor quotients.

Step 2: Compress the State Space with Distinct Floor Quotients

For fixed \(m\), define the compressed state set

$\mathcal{V}(m)=\left\{\left\lfloor \frac{m}{i}\right\rfloor : 1\le i\le m\right\}.$

This set contains only \(O(\sqrt{m})\) distinct values. The usual reason is that quotients larger than \(\sqrt{m}\) can occur only for \(i\le \sqrt{m}\), while every quotient at most \(\sqrt{m}\) lies in the small tail. Hence \(|\mathcal{V}(m)|\le 2\sqrt{m}\).

The crucial closure property is that every transition in the recurrence stays inside the same compressed set. If \(v=\lfloor m/i\rfloor\), then

$\left\lfloor \frac{v}{x}\right\rfloor=\left\lfloor \frac{\lfloor m/i\rfloor}{x}\right\rfloor=\left\lfloor \frac{m}{ix}\right\rfloor \in \mathcal{V}(m).$

So the dynamic program never needs values outside \(\mathcal{V}(m)\).

For each state \(v\in\mathcal{V}(m)\), the terms \(\lfloor v/x\rfloor\) are constant on intervals. If

$q=\left\lfloor \frac{v}{\ell}\right\rfloor,$

then the same quotient persists for all \(x\) in

$\ell \le x \le r=\left\lfloor \frac{v}{q}\right\rfloor.$

Therefore the transition can be grouped by quotient blocks:

$P_t(v)=\sum_{[\ell,r]} (r-\ell+1)\,P_{t-1}\!\left(\left\lfloor \frac{v}{\ell}\right\rfloor\right).$

The implementation precomputes these blocks once and then reuses them for every DP layer.

Step 3: Why \(F(m,n)\) is a Polynomial in \(n\)

Remove every entry equal to \(1\) from an admissible tuple. The remaining ordered core tuple has length \(r\), every entry is at least \(2\), and its product is still at most \(m\). Hence

$2^r \le m,$

so

$r \le d=\left\lfloor \log_2 m \right\rfloor.$

Now let \(C_r(m)\) be the number of ordered \(r\)-tuples \((b_1,\dots,b_r)\) with each \(b_i\ge 2\) and \(b_1\cdots b_r\le m\). Once such a core tuple is fixed, we obtain an \(n\)-tuple by choosing which \(r\) of the \(n\) positions carry the non-1 entries. That contributes exactly \(\binom{n}{r}\) placements. Therefore

$F(m,n)=\sum_{r=0}^{d} C_r(m)\binom{n}{r}.$

So for fixed \(m\), the answer is a polynomial in \(n\) of degree at most \(d\), written in the binomial basis. For \(m=10^9\), we have \(d=29\), which is why the implementation only needs the values for \(n=0,1,\dots,29\).

Step 4: Forward Differences and the Composite Modulus

Let \(Q(n)=F(m,n)\). Any polynomial of degree at most \(d\) has the Newton expansion

$Q(n)=\sum_{r=0}^{d} \Delta^r Q(0)\binom{n}{r},$

where \(\Delta\) denotes the forward-difference operator. In this problem the coefficients \(\Delta^r Q(0)\) coincide with the binomial-basis coefficients \(C_r(m)\).

The DP is used only to compute the sample values

$Q(0),Q(1),\dots,Q(d).$

After that, a short forward-difference table recovers the coefficients, and the polynomial is evaluated at the huge target \(n=10^9\).

The modulus \(1234567891\) is composite, so the program does not rely on Fermat-style modular inverses for \(\binom{n}{r}\). Instead it builds the numerator

$\frac{n(n-1)\cdots(n-r+1)}{r!}$

with exact integer cancellation by gcd, and only then reduces the result modulo \(1234567891\). Since \(r\le 29\), this step is tiny.

Worked Example: \(m=10\)

Here \(d=\lfloor \log_2 10\rfloor=3\). The dynamic program gives

$Q(0)=1,\qquad Q(1)=10,\qquad Q(2)=27,\qquad Q(3)=53.$

The forward differences are

$\Delta Q(0)=9,\qquad \Delta^2 Q(0)=8,\qquad \Delta^3 Q(0)=1.$

Hence

$F(10,n)=1+9\binom{n}{1}+8\binom{n}{2}+\binom{n}{3}.$

This also has a direct combinatorial meaning:

$C_0(10)=1,\quad C_1(10)=9,\quad C_2(10)=8,\quad C_3(10)=1.$

The eight ordered pairs with product at most \(10\) are \((2,2),(2,3),(2,4),(2,5),(3,2),(3,3),(4,2),(5,2)\), and the only ordered triple is \((2,2,2)\). Evaluating at \(n=10\) gives

$F(10,10)=1+9\binom{10}{1}+8\binom{10}{2}+\binom{10}{3}=571,$

which matches the checkpoint exactly.

How the Code Works

The implementation first builds the compressed list of distinct quotients \(\lfloor m/i\rfloor\). For every compressed state it precomputes the quotient blocks \([\ell,r]\) together with the target compressed state and the multiplicity \(r-\ell+1\). It then runs the recurrence for tuple lengths \(0\) through \(d\), keeping only the previous and current DP layers, and records the values at the state \(v=m\).

Those sampled values are converted into forward differences, and the final Newton series is evaluated at the requested \(n\). The C++, Python, and Java implementations all follow that same mathematical pipeline, so the checkpoints agree across languages.

Complexity Analysis

The compressed state count is \(S=|\mathcal{V}(m)|=O(\sqrt{m})\). For a state \(v\), the number of quotient blocks is \(O(\sqrt{v})\), so the total precomputed transition size is

$B=\sum_{v\in \mathcal{V}(m)} O(\sqrt{v})=O(m^{3/4}).$

Running the DP for \(d=\lfloor \log_2 m\rfloor\) layers therefore costs \(O(Bd)\) time after precomputation, and the memory usage is \(O(B+S)\). The forward-difference table and the final binomial evaluation are only \(O(d^2)\) and \(O(d)\), negligible here because \(d=29\) for \(m=10^9\).

References

1. Problem page: https://projecteuler.net/problem=452
2. Divisor summatory function and grouping equal floor quotients: Wikipedia - Divisor summatory function
3. Newton series: Wikipedia - Newton series
4. Finite differences: Wikipedia - Finite difference
5. Graham, Knuth, Patashnik, Concrete Mathematics, 2nd ed., Addison-Wesley, chapters on sums and finite differences.