Sequences where each number is a divisor of one less than the next

Question

Let $N,k$ be fixed. Call a sequence of positive integers $a_1,a_2,\dots,a_k$ good if for each $i$, $a_i$ is a divisor of $a_{i-1}-1$. Consider the set

$$S = \{x : \text{$x$ occurs in some good sequence of length $k$ that ends in $N$}\}$$

of numbers that appear in some good sequence of length $k$ ending in $N$.

Is it possible to get an estimate for $|S|$, as a function of $k,N$? Is it possible to get a reasonable upper bound on this? Is there any reason to expect that $|S|$ might be asymptotically much smaller than $N$, say $O((\log N)^c)$ or something like that?

---

Example: for $k=3$, $N=27$, we have $S=\{1,2,3,4,5,6,12,13,25,26,27\}$, so $|S|=11$. The set of good sequences of length 3 that end in 27 are:

1,2,27
1,13,27
1,26,27
2,13,27
3,13,27
4,13,27
5,26,27
6,13,27
12,13,27
25,26,27

So there does appear to be some structure here, but I'm not sure if there's anything that allows clean reasoning about it or about such sequences.

Answer 1

I'm sure sharper things can be said, but here are some estimates to calibrate thinking.

Let $f_k(N)$ be the function you describe. Note that $f_1$ is identically $1$, while $$f_k(N) = \sum_{d\mid(N-1)} f_{k-1}(d)$$ for all $k\ge2$. So for example, $f_2(N) = \tau(N-1)$ where $\tau$ is the number-of-divisors function.

Already this prohibits the possibility that $f_k(N) \ll (\log N)^c$ for any $c$, since there are integers $N-1$ (the primorials, for example) that have at least $\exp((\log2+o(1))\log N/\log\log N)$ divisors.

On the other hand, $\tau(N) \ll_\epsilon N^\epsilon$ for every $\epsilon>0$. From this fact and the recusrive formula for $f_k(N)$, it's easy to deduce that $f_k(N) \ll_{k,\epsilon} N^\epsilon$ by induction on $k$.