[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?)
Robert
More information about the SeqFan
mailing list