cp's OEIS Frontend

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

%I A054893 #28 Jan 08 2024 09:00:28
%S A054893 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,
%T A054893 10,10,10,11,11,11,11,12,12,12,12,13,13,13,13,15,15,15,15,16,16,16,16,
%U A054893 17,17,17,17,18,18,18,18,21,21,21,21,22,22,22,22,23,23,23,23,24,24,24,24
%N A054893 a(n) = Sum_{j > 0} floor(n/4^j).
%C A054893 Different from highest power of 4 dividing n! (see A090616).
%H A054893 Hieronymus Fischer, <a href="/A054893/b054893.txt">Table of n, a(n) for n = 0..10000</a>
%F A054893 a(n) = floor(n/4) + floor(n/16) + floor(n/64) + floor(n/256) + ...
%F A054893 a(n) = (n - A053737(n))/3.
%F A054893 From _Hieronymus Fischer_, Sep 15 2007: (Start)
%F A054893 a(n) = a(floor(n/4)) + floor(n/4).
%F A054893 a(4*n) = a(n) + n.
%F A054893 a(n*4^m) = a(n) + n*(4^m-1)/3.
%F A054893 a(k*4^m) = k*(4^m-1)/3, for 0 <= k < 4, m >= 0.
%F A054893 Asymptotic behavior:
%F A054893 a(n) = n/3 + O(log(n)),
%F A054893 a(n+1) - a(n) = O(log(n)); this follows from the inequalities below.
%F A054893 a(n) <= (n-1)/3; equality holds true for powers of 4.
%F A054893 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.
%F A054893 lim sup (n/3 - log_4(n) - a(n)) = 0, for n-->oo.
%F A054893 lim sup (a(n+1) - a(n) - log_4(n)) = 0, for n-->oo.
%F A054893 G.f.: (1/(1-x))*Sum_{k > 0} x^(4^k)/(1-x^(4^k)). (End)
%F A054893 Partial sums of A235127. - _R. J. Mathar_, Jul 08 2021
%e A054893   a(10^0) = 0.
%e A054893   a(10^1) = 2.
%e A054893   a(10^2) = 32.
%e A054893   a(10^3) = 330.
%e A054893   a(10^4) = 3331.
%e A054893   a(10^5) = 33330.
%e A054893   a(10^6) = 333330.
%e A054893   a(10^7) = 3333329.
%e A054893   a(10^8) = 33333328.
%e A054893   a(10^9) = 333333326.
%t A054893 Table[t=0; p=4; While[s=Floor[n/p]; t=t+s; s>0, p *= 4]; t, {n,0,100}]
%t A054893 Table[Total[Floor/@(n/NestList[4#&,4,6])],{n,0,80}] (* _Harvey P. Dale_, Jun 12 2022 *)
%o A054893 (Magma)
%o A054893 function A054893(n)
%o A054893   if n eq 0 then return n;
%o A054893   else return A054893(Floor(n/4)) + Floor(n/4);
%o A054893   end if; return A054893;
%o A054893 end function;
%o A054893 [A054893(n): n in [0..103]]; // _G. C. Greubel_, Feb 09 2023
%o A054893 (SageMath)
%o A054893 def A054893(n):
%o A054893     if (n==0): return 0
%o A054893     else: return A054893(n//4) + (n//4)
%o A054893 [A054893(n) for n in range(104)] # _G. C. Greubel_, Feb 09 2023
%o A054893 (PARI) a(n) = (n - sumdigits(n,4))/3; \\ _Kevin Ryde_, Jan 08 2024
%Y A054893 Cf. A053737, A235127 (first differences).
%Y A054893 Cf. A011371, A027868, A054861, A054899, A067080, A090616, A098844, A132028.
%K A054893 nonn,easy
%O A054893 0,9
%A A054893 _Henry Bottomley_, May 23 2000
%E A054893 Edited by _Hieronymus Fischer_, Sep 15 2007
%E A054893 Examples added by _Hieronymus Fischer_, Jun 06 2012