[reformulación que podría ser útil]
La siguiente matriz indica si el número $j$ puede ser el término $i$-ésimo de la secuencia ($1$ significa 'verdadero', $0$ significa 'falso'). El término general es $M_{ij}$ y el índice comienza en $1$.
$$M = \begin{bmatrix}[1] & [1] & [1] & [1] & [1] & [1] & [1] & [1] & [1] & \cdots \\ (1) & [1 & 0] & [1 & 0] & [1 & 0] & [1 & 0] & \cdots\\ (1) & 0 & [1 & 0 & 0] & [1 & 0 & 0] & [1 & \cdots\\ (1) & (1) & 0 & [1 & 0 & 0 & 0] & [1 & 0 & \cdots\\ (1) & 0 & 0 & 0 & [1 & 0 & 0 & 0 & 0] & \cdots\\ (1) & (1) & (1) & 0 & 0 & [1 & 0 & 0 & 0 & \cdots\\ (1) & 0 & 0 & 0 & 0 & 0 & [1 & 0 & 0 & \cdots\\ (1) & (1) & 0 & (1) & 0 & 0 & 0 & [1 & 0 & \cdots\\ (1) & 0 & (1) & 0 & 0 & 0 & 0 & 0 & [1 & \cdots\\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \end{bmatrix}$$
Debajo de la diagonal principal, cada valor $(1)$ indica que $j$ divide a $i$. En el resto de cada fila, tenemos un patrón para los múltiplos de $i$, que es un 'uno' seguido de $i-1$ 'ceros': $\begin{bmatrix}1&0&0&\cdots&0\end{bmatrix}$.
¡Note que $M$ es $\textbf{simétrica}$! Por lo tanto, el patrón para los múltiplos también se puede observar en las columnas, incluso para los valores debajo de la diagonal principal:
$$M = \begin{bmatrix}\color{blue}{1} & \color{blue}{1} & \color{blue}{1} & \color{blue}{1} & \color{blue}{1} & \color{blue}{1} & \color{blue}{1} & \color{blue}{1} & \color{blue}{1} & \color{blue}{\cdots} \\ \color{blue}{1} & \color{green}{1} & \color{green}{0} & \color{green}{1} & \color{green}{0} & \color{green}{1} & \color{green}{0} & \color{green}{1} & \color{green}{0} & \color{green}{\cdots}\\ \color{blue}{1} & \color{green}{0} & \color{red}{1} & \color{red}{0} & \color{red}{0} & \color{red}{1} & \color{red}{0} & \color{red}{0} & \color{red}{1} & \color{red}{\cdots}\\ \color{blue}{1} & \color{green}{1} & \color{red}{0} & \color{orange}{1} & \color{orange}{0} & \color{orange}{0} & \color{orange}{0} & \color{orange}{1} & \color{orange}{0} & \color{orange}{\cdots}\\ \color{blue}{1} & \color{green}{0} & \color{red}{0} & \color{orange}{0} & \color{magenta}{1} & \color{magenta}{0} & \color{magenta}{0} & \color{magenta}{0} & \color{magenta}{0} & \color{magenta}{\cdots}\\ \color{blue}{1} & \color{green}{1} & \color{red}{1} & \color{orange}{0} & \color{magenta}{0} & \color{brown}{1} & \color{brown}{0} & \color{brown}{0} & \color{brown}{0} & \color{brown}{\cdots}\\ \color{blue}{1} & \color{green}{0} & \color{red}{0} & \color{orange}{0} & \color{magenta}{0} & \color{brown}{0} & \color{gray}{1} & \color{gray}{0} & \color{gray}{0} & \color{gray}{\cdots}\\ \color{blue}{1} & \color{green}{1} & \color{red}{0} & \color{orange}{1} & \color{magenta}{0} & \color{brown}{0} & \color{gray}{0} & \color{cyan}{1} & \color{cyan}{0} & \color{cyan}{\cdots}\\ \color{blue}{1} & \color{green}{0} & \color{red}{1} & \color{orange}{0} & \color{magenta}{0} & \color{brown}{0} & \color{gray}{0} & \color{cyan}{0} & \color{teal}{1} & \color{teal}{\cdots}\\ \color{blue}{\vdots} & \color{green}{\vdots} & \color{red}{\vdots} & \color{orange}{\vdots} & \color{magenta}{\vdots} & \color{brown}{\vdots} & \color{gray}{\vdots} & \color{cyan}{\vdots} & \color{teal}{\vdots} & \ddots \end{bmatrix}$$
Una vez que tenemos esta matriz, el problema se puede reformular como:
- ¿cuál es el número de permutaciones de filas (o columnas) que mantienen la diagonal llena de 'unos'?
Lo cual creo que equivale a lo que Andrew Szymczak dijo en los comentarios: "necesitamos contar el número de particiones de ciclos del grafo de divisibilidad no dirigido (arista si i|j o j|i). Esto es equivalente a calcular el permanente de la matriz de adyacencia, que en general es NP-difícil".
Como un pequeño desarrollo al problema, podríamos definir un límite superior para el número de secuencias válidas.
Observe que cualquier número primo $p$ tal que $\frac{N}{2} < p \leq N$ tiene solo dos posibles posiciones ($i=1$ e $i=p$). Y, si uno de estos números primos se usa como el primer término, entonces el término $p$-ésimo debe ser $1$.
Por lo tanto, si $m$ es el número de números primos en $\left]\frac{N}{2},N\right]$, el número de secuencias válidas puede ser, como máximo, $\boxed{[N-m]! + m\,[N-m-1]!}$.
Para $N$ comprendido entre $2$ y $10$, este límite superior es $\{2,3,8,10,144,168,960,6\,480,403\,200\}$. Corresponde al número exacto de secuencias válidas solo para $N\leq 5$, luego, rápidamente se vuelve mucho más grande que el número exacto. Evidentemente, para tener límites superiores más bajos, deben considerarse más términos en el análisis (no solo unos pocos números primos).
