A054893 a(n) = Sum_{j > 0} floor(n/4^j).

0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 5, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8, 10, 10, 10, 10, 11, 11, 11, 11, 12, 12, 12, 12, 13, 13, 13, 13, 15, 15, 15, 15, 16, 16, 16, 16, 17, 17, 17, 17, 18, 18, 18, 18, 21, 21, 21, 21, 22, 22, 22, 22, 23, 23, 23, 23, 24, 24, 24, 24

Offset

0,9

Comments

Different from highest power of 4 dividing n! (see A090616).

Links

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

Formula

a(n) = floor(n/4) + floor(n/16) + floor(n/64) + floor(n/256) + ...

a(n) = (n - A053737(n))/3.

From Hieronymus Fischer, Sep 15 2007: (Start)

a(n) = a(floor(n/4)) + floor(n/4).

a(4*n) = a(n) + n.

a(n*4^m) = a(n) + n*(4^m-1)/3.

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

Asymptotic behavior:

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

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

a(n) <= (n-1)/3; equality holds true for powers of 4.

a(n) >= (n-3)/3 - floor(log_4(n)); equality holds true for n = 4^m - 1, m>0. lim inf (n/3 - a(n)) = 1/3, for n-->oo.

lim sup (n/3 - log_4(n) - a(n)) = 0, for n-->oo.

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

G.f.: (1/(1-x))*Sum_{k > 0} x^(4^k)/(1-x^(4^k)). (End)

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

Example

  a(10^0) = 0.
  a(10^1) = 2.
  a(10^2) = 32.
  a(10^3) = 330.
  a(10^4) = 3331.
  a(10^5) = 33330.
  a(10^6) = 333330.
  a(10^7) = 3333329.
  a(10^8) = 33333328.
  a(10^9) = 333333326.

Mathematica

Table[t=0; p=4; While[s=Floor[n/p]; t=t+s; s>0, p *= 4]; t, {n, 0, 100}]
Table[Total[Floor/@(n/NestList[4#&, 4, 6])], {n, 0, 80}] (* Harvey P. Dale, Jun 12 2022 *)

Prog

(Magma)
function A054893(n)
  if n eq 0 then return n;
  else return A054893(Floor(n/4)) + Floor(n/4);
  end if; return A054893;
end function;
[A054893(n): n in [0..103]]; // G. C. Greubel, Feb 09 2023
(SageMath)
def A054893(n):
    if (n==0): return 0
    else: return A054893(n//4) + (n//4)
[A054893(n) for n in range(104)] # G. C. Greubel, Feb 09 2023
(PARI) a(n) = (n - sumdigits(n, 4))/3; \\ Kevin Ryde, Jan 08 2024

Crossrefs

Cf. A053737, A235127 (first differences).

Cf. A011371, A027868, A054861, A054899, A067080, A090616, A098844, A132028.

Sequence in context: A209628 A132011 A363822 * A090617 A053693 A330324

Adjacent sequences: A054890 A054891 A054892 * A054894 A054895 A054896

Keyword

nonn,easy

Author

Henry Bottomley, May 23 2000

Extensions

Edited by Hieronymus Fischer, Sep 15 2007

Examples added by Hieronymus Fischer, Jun 06 2012

Status

approved