Sequences where each number is a divisor of one less than the next 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.

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$.
