Sequence-Counting Sequences: Variants of A008934

[Brendan McKay]

* Paul D. Hanna <pauldhanna at juno.com> [050917 18:48]:
> Seqfans,
>       Would someone wish to extend the following sequence-counting
> sequences?
> For positive integer values of m, they are defined by:
>  
> "Number of sequences (a_1, a_2,..., a_n) with a_1 = 1 
> such that a_i < a_{i+1} <= m*a_i for all i."
  
To get a bit further than where your counts end, you can use
a recurrence noting that the inequality above does not depend
on a_j for j < i.

Let a(i,x) be the number of sequences such that a_i = x.
Then   a(i+1,y) = sum of a(i,x) for x from ceiling(y/m) to y-1.
Moreover, a(i+1,y+1) = a(i+1,y) + a(i,y) - a(i,ceiling(y/m)) 
                       where the last term is only present if
                       y is a multiple of m.

Obviously a(i,x)=0 if x > m^i, so this gives running time
of i * m^i for finding a_i.

I'll leave it to you to check this and determine the boundary
conditions.

Brendan.