Detailed mathematical approach

Problem Summary

For fixed integers \(N\) and \(K\), the task is to count all factorisations whose product is at most \(N\) and whose total length is at most \(K\), with the factors written in nondecreasing order. Factors equal to \(1\) are allowed, so each factorisation consists of some leading ones followed by a nondecreasing block of factors at least \(2\). The final total is taken modulo \(10^9+7\).

Mathematical Approach

It is useful to separate the trivial factors \(1\) from the genuinely multiplicative part. For integers \(L \ge 1\), \(m \ge 2\), and \(p \ge 0\), define

$C(L,m,p)=\#\left\{(a_1,\dots,a_p)\in \mathbb{Z}_{\ge 2}^p : m \le a_1 \le \cdots \le a_p,\ \prod_{i=1}^{p} a_i \le L\right\}.$

When \(m=2\), this counts the core factorisations with exactly \(p\) nontrivial factors.

Step 1: Bound the Number of Nontrivial Factors

Every nontrivial factor is at least \(2\). Therefore any factorisation with \(p\) such factors has product at least \(2^p\). If \(2^p>N\), no such factorisation can contribute.

Hence the largest relevant value of \(p\) is

$P=\left\lfloor \log_2 N \right\rfloor.$

This explains why the implementations only need to compute counts up to that depth.

Step 2: Derive the Recurrence

Fix \(p \ge 2\), and choose the first factor \(a_1=x\). Because the sequence is nondecreasing, every remaining factor is at least \(x\). Thus the remaining product is at least \(x^{p-1}\), and the whole product is at least \(x^p\). So we must have

$x^p \le L,$

which gives the sharp upper bound

$x \le \left\lfloor L^{1/p} \right\rfloor.$

After fixing \(x\), the remaining \(p-1\) factors must still be nondecreasing, each at least \(x\), and their product must be at most \(\lfloor L/x \rfloor\). Therefore

$C(L,m,p)=\sum_{x=m}^{\left\lfloor L^{1/p} \right\rfloor} C\!\left(\left\lfloor \frac{L}{x} \right\rfloor, x, p-1\right).$

The base cases are immediate:

$C(L,m,0)=1,$

because the empty tail contributes one valid completion, and

$C(L,m,1)=\max\!\bigl(0,\,L-m+1\bigr),$

because a single remaining factor can be any integer from \(m\) up to \(L\).

Step 3: Why This Counts Each Core Factorisation Exactly Once

The condition \(m \le a_1 \le \cdots \le a_p\) fixes a canonical order, so no permutation duplicates appear. Every valid core factorisation has one and only one first factor \(x\), and once \(x\) is chosen, the rest of the sequence is described by the smaller problem with limit \(\lfloor L/x \rfloor\), lower bound \(x\), and one fewer position.

Thus the recursion is exact, not heuristic. Two different branches cannot represent the same factorisation, and every valid factorisation belongs to one branch.

Step 4: Reintroduce the Factors Equal to \(1\)

Let

$A_p=C(N,2,p)$

for \(1 \le p \le P\). This counts the nondecreasing factorizations whose nontrivial part has exactly \(p\) factors, all at least \(2\).

If such a core factorisation has length \(p\), then for any total length \(t\) with \(p \le t \le K\), it extends uniquely to

$(\underbrace{1,\dots,1}_{t-p\text{ times}},a_1,\dots,a_p),$

because in nondecreasing order all ones must appear at the front. Therefore each core factorisation contributes exactly

$K-p+1$

times to the final answer.

There is also the purely trivial family consisting only of ones. For each length \(t=1,2,\dots,K\), the factorisation \((1,\dots,1)\) has product \(1\le N\), so these contribute another \(K\) in total.

Step 5: Final Formula

Combining the previous steps gives

$D(N,K)=K+\sum_{p=1}^{\min(P,K)} A_p\,(K-p+1)\pmod{10^9+7},$

where \(P=\lfloor \log_2 N \rfloor\) and \(A_p=C(N,2,p)\). This is exactly the quantity accumulated by the implementations.

Worked Example: \(N=10,\ K=10\)

Here \(P=\lfloor \log_2 10 \rfloor=3\), because \(2^3 \le 10 \lt 2^4\).

For \(p=1\), the nontrivial core factorisations are simply \((2),(3),\dots,(10)\), so

$A_1=9.$

For \(p=2\), the valid nondecreasing pairs are

$ (2,2),\ (2,3),\ (2,4),\ (2,5),\ (3,3), $

so

$A_2=5.$

For \(p=3\), only

$ (2,2,2) $

works, hence

$A_3=1.$

No longer core factorisation is possible. Therefore

$D(10,10)=10 + 9 \cdot 10 + 5 \cdot 9 + 1 \cdot 8 = 153,$

which matches the built-in checkpoint.

How the Code Works

The C++, Python, and Java implementations first determine the maximum relevant depth \(P\) by repeatedly doubling until the product would exceed \(N\). They then evaluate \(C(N,2,p)\) for each \(p=1,2,\dots,P\) using the same memoized recursion described above.

Each cached state is determined by three mathematical parameters: the remaining product limit, the minimum allowed next factor, and the number of factors still to place. An exact integer \(p\)-th root is used to compute \(\lfloor L^{1/p} \rfloor\) safely, so the loop bounds remain correct even near perfect powers.

After all core counts are known, the implementation adds the \(K\) all-one factorizations, applies the multiplicity \(K-p+1\) to each core count, and performs every arithmetic step modulo \(10^9+7\).

Complexity Analysis

Let \(\mathcal{S}\) be the set of distinct states reached by the memoized recursion. A state with parameters \((L,m,p)\) performs

$\max\!\left(0,\left\lfloor L^{1/p} \right\rfloor - m + 1\right)$

transitions. Therefore the total running time is

$O\!\left(\sum_{(L,m,p)\in\mathcal{S}} \max\!\left(0,\left\lfloor L^{1/p} \right\rfloor - m + 1\right)\right).$

The recursion depth is at most \(\lfloor \log_2 N \rfloor\), because every nontrivial factor is at least \(2\). Memory usage is \(O(|\mathcal{S}|)\) for the memo table. In practice, many branches collapse to the same subproblem, so memoization removes a large amount of repeated work.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=738
2. Multiplicative partitions: MathWorld - Multiplicative Partition
3. Integer \(n\)-th root: Wikipedia - Integer nth root
4. Dynamic programming: Wikipedia - Dynamic programming
5. Memoization: Wikipedia - Memoization