Count non-decreasing sequences of a given length N made from multiples under a limit M

Question

Given integers N and M, count how many sequences A of N integers satisfy the following conditions?

$1 ≤ A_i​ ≤ M(i=1,2,…,N)$

$A_{i+1}$ is a multiple of $A_i$. $(i=1,2,…,N−1)$

For example for N=3 and M=4, these are the sequences: $(1,1,1), (1,1,2), (1,2,2), (2,2,2), (1,1,3), (1,3,3), (3,3,3), (1,4,4), (2,4,4), (4,4,4), (2,2,4), (1,2,4), (1,1,4) $ Hence the answer is 13

Since this is a problem where I don't expect to find a closed form, So all computational answers are welcome but more efficient answers are more appreciated. My hunch says we can compute it in something like $O(N\ log M)$ or $O(M\ log N)$ time.

Answer 1

Here is a dynamic-programming approach.

Let $f(N,M)$ be the answer. I claim $f(N,M)=\sum\limits_{j\ge 1} f(N-1, \lfloor \frac Mj \rfloor)$. To see this, if $A_1$ is known, the sequence $(\frac{A_2}{A_1}, \cdots, \frac{A_N}{A_1})$ is a sequence that satisfies the conditions for $(N-1, \lfloor \frac{A_N}{M} \rfloor)$

How many distinct values for $\lfloor \frac Mj \rfloor$ exists? Approximately $2\sqrt{M}$. Note $\lfloor \frac Mj \rfloor$ is distinct for $j<\sqrt{M}$ and we can count the number of solutions to $\lfloor \frac Mj\rfloor=k$ in $O(1)$ as this is simply $\lfloor \frac {M}{k} \rfloor - \lfloor \frac {M}{k+1} \rfloor$

This is an $O(NM^{1.5})$ approach. I am wondering if there is a faster approach.

Answer 2

Here is a different approach that may or may not be better.

Let $V_k$ be a column matrix with $M$ rows, namely

$\begin{bmatrix} f(k,1)\\ f(k,2)\\ \cdots \\ f(k,M)\\ \end{bmatrix}$

Then there exists a $M\times M$ matrix, call $A$ such that $AV_{k-1}=V_k$ for all integers $k$. $A$ satisfies $A_{k, \lfloor \frac kj \rfloor}=1$ and all other entries are 0. This implies that $V_n=A^nV_0$.

We need to multiply a matrix $O(\log N)$ times, but what is the time complexity of multiplying by a matrix? At first glance, it appears to be $O(M^3)$, so this is $O(\log N M^3)$. However, if $A$ is diagonalizable, then we have

$V_n = (XD^nX^{-1})V_0 $ and we can compute this in $O(\log N + M^3)$