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
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