|
%I #82 Sep 08 2022 08:45:00
%S 0,1,2,3,1,2,3,4,2,3,4,5,3,4,5,6,1,2,3,4,2,3,4,5,3,4,5,6,4,5,6,7,2,3,
%T 4,5,3,4,5,6,4,5,6,7,5,6,7,8,3,4,5,6,4,5,6,7,5,6,7,8,6,7,8,9,1,2,3,4,
%U 2,3,4,5,3,4,5,6,4,5,6,7,2,3,4,5,3,4,5,6,4,5,6,7,5,6,7,8,3,4,5,6,4,5,6,7,5
%N Sum of digits of (n written in base 4).
%C Also the fixed point of the morphism 0->{0,1,2,3}, 1->{1,2,3,4}, 2->{2,3,4,5}, etc. - _Robert G. Wilson v_, Jul 27 2006
%H Donovan Johnson, <a href="/A053737/b053737.txt">Table of n, a(n) for n = 0..10000</a>
%H F. T. Adams-Watters and F. Ruskey, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL12/Ruskey2/ruskey14.html">Generating Functions for the Digital Sum and Other Digit Counting Sequences</a>, JIS Vol. 12 (2009), Article 09.5.6.
%H Steve Butler and Ron L. Graham, <a href="http://arxiv.org/abs/1003.4422">Shuffling with ordered cards</a>, arXiv 1003:4422 [math.CO], 2010.
%H Jeffrey O. Shallit, <a href="http://www.jstor.org/stable/2322179">Problem 6450</a>, Advanced Problems, The American Mathematical Monthly, Vol. 91, No. 1 (1984), pp. 59-60; <a href="http://www.jstor.org/stable/2322523">Two series, solution to Problem 6450</a>, ibid., Vol. 92, No. 7 (1985), pp. 513-514.
%H Robert Walker, <a href="http://robertinventor.com/ftswiki/Self_Similar_Sloth_Canon_Number_Sequences">Self Similar Sloth Canon Number Sequences</a>.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/DigitSum.html">Digit Sum</a>.
%F From _Benoit Cloitre_, Dec 19 2002: (Start)
%F a(0) = 0, a(4n+i) = a(n)+i for 0 <= i <= 3.
%F a(n) = n - 3*Sum_{k>0} floor(n/4^k) = n - 3*A054893(n). (End)
%F G.f.: (Sum_{k>=0} (x^(4^k) + 2*x^(2*4^k) + 3*x^(3*4^k))/(1 + x^(4^k) + x^(2*4^k) + x^(3*4^k))/(1-x). - _Franklin T. Adams-Watters_, Nov 03 2005
%F a(n) = A138530(n,4) for n > 3. - _Reinhard Zumkeller_, Mar 26 2008
%F a(n) = Sum_{k>=0} A030386(n,k). - _Philippe Deléham_, Oct 21 2011
%F a(n) = A007953(A007090(n)). - _Reinhard Zumkeller_, Mar 19 2015
%F a(0) = 0; a(n) = a(n - 4^floor(log_4(n))) + 1. - _Ilya Gutkovskiy_, Aug 23 2019
%F Sum_{n>=1} a(n)/(n*(n+1)) = 4*log(4)/3 (Shallit, 1984). - _Amiram Eldar_, Jun 03 2021
%e a(20) = 1+1+0 = 2 because 20 is written as 110 base 4.
%e From _Omar E. Pol_, Feb 21 2010: (Start)
%e This can be written as a triangle (cf. A000120):
%e 0,
%e 1,2,3,
%e 1,2,3,4,2,3,4,5,3,4,5,6,
%e 1,2,3,4,2,3,4,5,3,4,5,6,4,5,6,7,2,3,4,5,3,4,5,6,4,5,6,7,5,6,7,8,3,4,5,6,4,5,6,7,5,6,7,8,6,7,8,9,
%e 1,2,3,4,2,3,4,5,3,4,5,6,4,5,6,7,2,3,4,5,3,4,5,6,4,5,6,7,5,6,7,8,3,4,5,6,4,...
%e where the rows converge to A173524.
%e (End)
%p A053737 := proc(n)
%p add(d,d=convert(n,base,4)) ;
%p end proc: # _R. J. Mathar_, Oct 31 2012
%t Table[Plus @@ IntegerDigits[n, 4], {n, 0, 100}] (* or *)
%t Nest[ Flatten[ #1 /. a_Integer -> {a, a+1, a+2, a+3}] &, {0}, 4] (* _Robert G. Wilson v_, Jul 27 2006 *)
%o (PARI) a(n)=if(n<1,0,if(n%4,a(n-1)+1,a(n/4)))
%o (PARI) a(n) = sumdigits(n, 4); \\ _Michel Marcus_, Aug 24 2019
%o (Haskell)
%o a053737 n = if n == 0 then 0 else a053737 m + r where (m, r) = divMod n 4
%o -- _Reinhard Zumkeller_, Mar 19 2015
%o (Magma) [&+Intseq(n,4):n in [0..104]]; // _Marius A. Burtea_, Jan 17 2019
%o (MATLAB) for u=0:104; sol(u+1)=sum(dec2base(u,4)-'0');end
%o sol % _Marius A. Burtea_, Jan 17 2019
%Y Cf. A231664-A231667, A138530.
%Y Cf. A173524. - _Omar E. Pol_, Feb 21 2010
%Y Sum of digits of n written in bases 2-16: A000120, A053735, this sequence, A053824, A053827, A053828, A053829, A053830, A007953, A053831, A053832, A053833, A053834, A053835, A053836.
%Y Related base-4 sequences: A053737, A230631, A230632, A010064, A230633, A230634, A230635, A230636, A230637, A230638, A010065 (trajectory of 1).
%Y Cf. A007090, A239690.
%K base,nonn,easy
%O 0,3
%A _Henry Bottomley_, Mar 28 2000
|
