[seqfan] Asymptotics of a floor recurrence

Robert Dougherty-Bliss robert.w.bliss at gmail.com
Wed Nov 25 17:45:24 CET 2020

Dear SeqFans,

Happy Thanksgiving!

Consider a sequence recursively defined by

    a(n) = a(floor(n / p)) * (n mod p + 1)

where p is some fixed positive integer. Such a sequence is determined by
a(0), a(1), ..., a(p - 1). In words, the sequence is this: "multiply 1 +
all but the highest base p digits of n with a number determined by the
highest base p digit of n." Such a sequence arises in solving Problem
148 of Project Euler, and most of them (varying p and the initial terms)
are not in the OEIS.

Some things are not hard to see:

    limsup_n a(n) = oo if any of a(1), ..., a(p - 1) are positive.

    a(p^n) = a(1) for n >= 1, and there are similar results for the
    other initial terms.

I am interested in two questions:

1. Let P(n, K) be the number of terms with index <= n which exceed K.
   Does P(n, K) tend to a limit as n -> oo?

2. It is not hard to show that a(n) = O(n). (Note that n mod p + 1 <= p,
   then repeat.) Is this tight in any sense?
   (Perhaps limsup_n a(n) / n = c for a constant c?)


More information about the SeqFan mailing list