A054898 - OEIS

%I #21 Jul 10 2024 12:49:00

%S 0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,3,3,3,3,3,3,3,

%T 3,3,4,4,4,4,4,4,4,4,4,5,5,5,5,5,5,5,5,5,6,6,6,6,6,6,6,6,6,7,7,7,7,7,

%U 7,7,7,7,8,8,8,8,8,8,8,8,8,10,10,10,10,10,10,10,10,10,11,11,11,11,11,11,11

%N a(n) = Sum_{k>0} floor(n/9^k).

%C Different from the highest power of 9 dividing n!, A090618.

%H Hieronymus Fischer, <a href="/A054898/b054898.txt">Table of n, a(n) for n = 0..10000</a>

%F a(n) = floor(n/9) + floor(n/81) + floor(n/729) + floor(n/6561) + ....

%F a(n) = (n-A053830(n))/8.

%F From _Hieronymus Fischer_, Aug 14 2007: (Start)

%F Recurrence:

%F a(n) = floor(n/9) + a(floor(n/9));

%F a(9*n) = n + a(n);

%F a(n*9^m) = n*(9^m-1)/8 + a(n).

%F a(k*9^m) = k*(9^m-1)/8, for 0<=k<9, m>=0.

%F Asymptotic behavior:

%F a(n) = n/8 + O(log(n)),

%F a(n+1) - a(n) = O(log(n)); this follows from the inequalities below.

%F a(n) <= (n-1)/8; equality holds for powers of 9.

%F a(n) >= (n-8)/8 - floor(log_9(n)); equality holds for n=9^m-1, m>0.

%F lim inf (n/8 - a(n)) =1/8, for n-->oo.

%F lim sup (n/8 - log_9(n) - a(n)) = 0, for n-->oo.

%F lim sup (a(n+1) - a(n) - log_9(n)) = 0, for n-->oo.

%F G.f.: g(x) = sum{k>0, x^(9^k)/(1-x^(9^k))}/(1-x). (End)

%e a(100)=12.

%e a(10^3)=124.

%e a(10^4)=1248.

%e a(10^5)=12498.

%e a(10^6)=124996.

%e a(10^7)=1249997.

%e a(10^8)=12499996.

%e a(10^9)=124999997.

%t Table[t = 0; p = 9; While[s = Floor[n/p]; t = t + s; s > 0, p *= 9]; t, {n, 0, 100} ]

%t Table[Sum[Floor[n/9^k],{k,n}],{n,0,100}] (* _Harvey P. Dale_, Jul 10 2024 *)

%Y Cf. A011371 and A054861 for analogs involving powers of 2 and 3.

%Y Cf. A054899, A067080, A098844, A132033.

%K nonn

%O 0,19

%A _Henry Bottomley_, May 23 2000

%E Examples added by _Hieronymus Fischer_, Jun 06 2012