This is a follow up to my recent question on the [asymptotics of A003238][1]. [Lucia][2] gave a fine answer to that question, but as I hinted the 'real' problem I have in mind is slightly different, and I've not been able to massage that answer into a solution for this case. On the other hand it feels like it should be easier or known how to handle the resulting problem, so here we are again.

Consider rooted trees where all vertices at the same level have the same number of children *and this is $\geq 3$ except for leaves*. If we let $s(n)$ denote the number of such trees with $n$ nodes then we get a sequence for $n \geq 1$:

1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, ...

Note the first 2 occurs at $n = 13$ corresponding to either a root with 12 children, or a root with three children, each of which has three children. Obviously, the $s$ sequence doesn't have an asymptotic form (since e.g. $s(p+1) = 1$ for all odd primes $p$). However, letting
$$
S(x) = \sum_{n \leq x} s(n)
$$
and rearranging the order of summation as in Lucia's solution gives:
$$
S(n+1) = 1 + \sum_{d \geq 3} S(n/d)
$$
(plus the obvious extra conditions, $S(0) = 0$, $S(x) = S(\lfloor x \rfloor)$.)

So, *what are the asymptotics of $S$*?


  [1]: http://mathoverflow.net/questions/159991/are-the-asymptotics-of-a003238-known
  [2]: http://mathoverflow.net/users/38624/lucia