A054897 a(n) = Sum_{k>0} floor(n/8^k).

0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12

Offset: 0

Author

Henry Bottomley, May 23 2000

Keywords

• nonn

Comments

Different from the highest power of 8 dividing n!, A090617.

Examples

			a(100) = 13.
a(10^3) = 141.
a(10^4) = 1427.
a(10^5) = 14284.
a(10^6) = 142855.
a(10^7) = 1428569.
a(10^8) = 14285710.
a(10^9) = 142857138.
		

Links

• Hieronymus Fischer, Table of n, a(n) for n = 0..10000

Crossrefs

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

Cf. A054899, A067080, A098844, A132032.

Programs

Magma

m:=8;
function a(n) // a = A054897
  if n eq 0 then return n;
  else return a(Floor(n/m)) + Floor(n/m);
  end if;
end function;
[a(n): n in [0..103]]; // G. C. Greubel, Apr 28 2023

Mathematica

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

Python

def A054897(n): return (n-sum(int(d) for d in oct(n)[2:]))//7 # Chai Wah Wu, Jul 09 2022

SageMath

m=8 # a = A054897
def a(n): return 0 if (n==0) else a(n//m) + (n//m)
[a(n) for n in range(104)] # G. C. Greubel, Apr 28 2023

Formula

a(n) = floor(n/8) + floor(n/64) + floor(n/512) + floor(n/4096) + ....

a(n) = (n - A053829(n))/7.

From Hieronymus Fischer, Aug 14 2007: (Start)

Recurrence:

a(n) = floor(n/8) + a(floor(n/8));

a(8*n) = n + a(n);

a(n*8^m) = n*(8^m-1)/7 + a(n).

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

Asymptotic behavior:

a(n) = n/7 + O(log(n)),

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

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

a(n) >= (n-7)/7 - floor(log_8(n)); equality holds for n=8^m-1, m>0.

lim inf (n/7 - a(n)) = 1/7, for n -> oo.

lim sup (n/7 - log_8(n) - a(n)) = 0, for n -> oo.

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

G.f.: g(x) = ( Sum_{k>0} x^(8^k)/(1-x^(8^k)) )/(1-x). (End)

Partial sums of A244413. - R. J. Mathar, Jul 08 2021

Extensions

Examples added by Hieronymus Fischer, Jun 06 2012