A053735 Sum of digits of (n written in base 3).

0, 1, 2, 1, 2, 3, 2, 3, 4, 1, 2, 3, 2, 3, 4, 3, 4, 5, 2, 3, 4, 3, 4, 5, 4, 5, 6, 1, 2, 3, 2, 3, 4, 3, 4, 5, 2, 3, 4, 3, 4, 5, 4, 5, 6, 3, 4, 5, 4, 5, 6, 5, 6, 7, 2, 3, 4, 3, 4, 5, 4, 5, 6, 3, 4, 5, 4, 5, 6, 5, 6, 7, 4, 5, 6, 5, 6, 7, 6, 7, 8, 1, 2, 3, 2, 3, 4, 3, 4, 5, 2, 3, 4, 3, 4, 5, 4, 5, 6, 3, 4, 5, 4, 5, 6

Offset: 0

Author

Henry Bottomley, Mar 28 2000

Keywords

• base
• nonn
• easy

Comments

Also the fixed point of the morphism 0->{0,1,2}, 1->{1,2,3}, 2->{2,3,4}, etc. - Robert G. Wilson v, Jul 27 2006

Examples

			a(20) = 2 + 0 + 2 = 4 because 20 is written as 202 base 3.
From _Omar E. Pol_, Feb 20 2010: (Start)
This can be written as a triangle with row lengths A025192 (see the example in the entry A000120):
0,
1,2,
1,2,3,2,3,4,
1,2,3,2,3,4,3,4,5,2,3,4,3,4,5,4,5,6,
1,2,3,2,3,4,3,4,5,2,3,4,3,4,5,4,5,6,3,4,5,4,5,6,5,6,7,2,3,4,3,4,5,4,5,6,3,...
where the k-th row contains a(3^k+i) for 0<=i<2*3^k and converges to A173523 as k->infinity. (End) [Changed conjectures to statements in this entry. - _Franklin T. Adams-Watters_, Jul 02 2015]
G.f. = x + 2*x^2 + x^3 + 2*x^4 + 3*x^5 + 2*x^6 + 3*x^7 + 4*x^8 + x^9 + 2*x^10 + ...
		

Links

• T. D. Noe, Table of n, a(n) for n = 0..10000
• F. T. Adams-Watters and F. Ruskey, Generating Functions for the Digital Sum and Other Digit Counting Sequences, JIS, Vol. 12 (2009), Article 09.5.6.
• F. M. Dekking, The Thue-Morse Sequence in Base 3/2, J. Int. Seq., Vol. 26 (2023), Article 23.2.3.
• Michael Gilleland, Some Self-Similar Integer Sequences.
• A. V. Kitaev and A. Vartanian, Algebroid Solutions of the Degenerate Third Painlevé Equation for Vanishing Formal Monodromy Parameter, arXiv:2304.05671 [math.CA], 2023. See pp. 11, 13.
• Jan-Christoph Puchta and Jürgen Spilker, Altes und Neues zur Quersumme, Math. Semesterber, Vol. 49 (2002), pp. 209-226; preprint.
• Jeffrey O. Shallit, Problem 6450, Advanced Problems, The American Mathematical Monthly, Vol. 91, No. 1 (1984), pp. 59-60; Two series, solution to Problem 6450, ibid., Vol. 92, No. 7 (1985), pp. 513-514.
• Vladimir Shevelev, Compact integers and factorials, Acta Arith., Vol. 126, No. 3 (2007), pp. 195-236 (cf. p.205).
• Robert Walker, Self Similar Sloth Canon Number Sequences.
• Eric Weisstein's World of Mathematics, Digit Sum.

Crossrefs

Cf. A065363, A007089, A173523. See A134451 for iterations.

Cf. A003137, A138530.

Sum of digits of n written in bases 2-16: A000120, this sequence, A053737, A053824, A053827, A053828, A053829, A053830, A007953, A053831, A053832, A053833, A053834, A053835, A053836.

Related base-3 sequences: A006047, A230641, A230642, A230643, A230853, A230854, A230855, A230856, A230639, A230640, A010063 (trajectory of 1), A286585, A286632, A289813, A289814.

Programs

Haskell

a053735 = sum . a030341_row
-- Reinhard Zumkeller, Feb 21 2013, Feb 19 2012

MATLAB

m=1; for u=0:104; sol(m)=sum(dec2base(u,3)-'0'); m=m+1;end
sol; % Marius A. Burtea, Jan 17 2019

Magma

[&+Intseq(n,3):n in [0..104]]; // Marius A. Burtea, Jan 17 2019

Maple

seq(convert(convert(n,base,3),`+`),n=0..100); # Robert Israel, Jul 02 2015

Mathematica

Table[Plus @@ IntegerDigits[n, 3], {n, 0, 100}] (* or *)
Nest[Join[#, # + 1, # + 2] &, {0}, 6] (* Robert G. Wilson v, Jul 27 2006 and modified Jul 27 2014 *)

PARI

{a(n) = if( n<1, 0, a(n\3) + n%3)}; /* Michael Somos, Mar 06 2004 */

PARI

A053735(n)=sumdigits(n,3) \\ Requires version >= 2.7. Use sum(i=1,#n=digits(n,3),n[i]) in older versions. - M. F. Hasler, Mar 15 2016

Scheme

(define (A053735 n) (let loop ((n n) (s 0)) (if (zero? n) s (let ((d (mod n 3))) (loop (/ (- n d) 3) (+ s d)))))) ;; For R6RS standard. Use modulo instead of mod in older Schemes like MIT/GNU Scheme. - Antti Karttunen, Jun 03 2017

Formula

From Benoit Cloitre, Dec 19 2002: (Start)

a(0) = 0, a(3n) = a(n), a(3n + 1) = a(n) + 1, a(3n + 2) = a(n) + 2.

a(n) = n - 2*Sum_{k>0} floor(n/3^k) = n - 2*A054861(n). (End)

a(n) = A062756(n) + 2*A081603(n). - Reinhard Zumkeller, Mar 23 2003

G.f.: (Sum_{k >= 0} (x^(3^k) + 2*x^(2*3^k))/(1 + x^(3^k) + x^(2*3^k)))/(1 - x). - Michael Somos, Mar 06 2004, corrected by Franklin T. Adams-Watters, Nov 03 2005

In general, the sum of digits of (n written in base b) has generating function (Sum_{k>=0} (Sum_{0 <= i < b} i*x^(i*b^k))/(Sum_{i=0..b-1} x^(i*b^k)))/(1-x). - Franklin T. Adams-Watters, Nov 03 2005

First differences of A094345. - Vladeta Jovovic, Nov 08 2005

a(A062318(n)) = n and a(m) < n for m < A062318(n). - Reinhard Zumkeller, Feb 26 2008

a(n) = A138530(n,3) for n > 2. - Reinhard Zumkeller, Mar 26 2008

a(n) <= 2*log_3(n+1). - Vladimir Shevelev, Jun 01 2011

a(n) = Sum_{k>=0} A030341(n, k). - Philippe Deléham, Oct 21 2011

G.f. satisfies G(x) = (x+2*x^2)/(1-x^3) + (1+x+x^2)*G(x^3), and has a natural boundary at |x|=1. - Robert Israel, Jul 02 2015

a(n) = A056239(A006047(n)). - Antti Karttunen, Jun 03 2017

a(n) = A000120(A289813(n)) + 2*A000120(A289814(n)). - Antti Karttunen, Jul 20 2017

a(0) = 0; a(n) = a(n - 3^floor(log_3(n))) + 1. - Ilya Gutkovskiy, Aug 23 2019

Sum_{n>=1} a(n)/(n*(n+1)) = 3*log(3)/2 (Shallit, 1984). - Amiram Eldar, Jun 03 2021