This appears to be solved on mathoverlow: https://mathoverflow.net/questions/401272/bounds-for-an-an-1a-lfloor-n-2-rfloor The answer is something like a(n) ~ exp(log(n)^2)=n^log(n). To my surprise the same bound holds for the generalization: for 0 < A < 1 b(n)=b(n-1)+b(floor(A*n))