A054899 -id:A054899 - cp's OEIS frontend

A007953 Digital sum (i.e., sum of digits) of n; also called digsum(n).

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 8, 9, 10, 11, 12, 13, 14, 15

Offset: 0

R. Muller

Do not confuse with the digital root of n, A010888 (first term that differs is a(19)).
Also the fixed point of the morphism 0 -> {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, 1 -> {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, 2 -> {2, 3, 4, 5, 6, 7, 8, 9, 10, 11}, etc. - Robert G. Wilson v, Jul 27 2006
For n < 100 equal to (floor(n/10) + n mod 10) = A076314(n). - Hieronymus Fischer, Jun 17 2007
It appears that a(n) is the position of 10*n in the ordered set of numbers obtained by inserting/placing one digit anywhere in the digits of n (except a zero before 1st digit). For instance, for n=2, the resulting set is (12, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 32, 42, 52, 62, 72, 82, 92) where 20 is at position 2, so a(2) = 2. - Michel Marcus, Aug 01 2022
Also the total number of beads required to represent n on a Russian abacus (schoty). - P. Christopher Staecker, Mar 31 2023
a(n) / a(2n) <= 5 with equality iff n is in A169964, while a(n) / a(3n) is unbounded, since if n = (10^k + 2)/3, then a(n) = 3*k+1, a(3n) = 3, so a(n) / a(3n) = k + 1/3 -> oo when k->oo (see Diophante link). - Bernard Schott, Apr 29 2023
Also the number of symbols needed to write number n in Egyptian numerals for n < 10^7. - Wojciech Graj, Jul 10 2025

			a(123) = 1 + 2 + 3 = 6, a(9875) = 9 + 8 + 7 + 5 = 29.

N. J. A. Sloane, Table of n, a(n) for n = 0..10000
Krassimir Atanassov, On the 16th Smarandache Problem, Notes on Number Theory and Discrete Mathematics, Sophia, Bulgaria, Vol. 5 (1999), No. 1, 36-38.
Krassimir Atanassov, On Some of the Smarandache's Problems, 1999.
Jean-Luc Baril, Classical sequences revisited with permutations avoiding dotted pattern, Electronic Journal of Combinatorics, Vol. 18 (2011), #P178.
F. M. Dekking, The Thue-Morse Sequence in Base 3/2, J. Int. Seq., Vol. 26 (2023), Article 23.2.3.
Diophante, A1762, Des chiffres à la moulinette (in French).
Ernesto Estrada and Puri Pereira-Ramos, Spatial 'Artistic' Networks: From Deconstructing Integer-Functions to Visual Arts, Complexity, Vol. 2018 (2018), Article ID 9893867.
A. O. Gel'fond, Sur les nombres qui ont des propriétés additives et multiplicatives données (French) Acta Arith., Vol. 13 (1967/1968), pp. 259-265. MR0220693 (36 #3745)
Christian Mauduit and András Sárközy, On the arithmetic structure of sets characterized by sum of digits properties J. Number Theory, Vol. 61, No. 1 (1996), pp. 25-38. MR1418316 (97g:11107)
Christian Mauduit and András Sárközy, On the arithmetic structure of the integers whose sum of digits is fixed, Acta Arith., Vol. 81, No. 2 (1997), pp. 145-173. MR1456239 (99a:11096)
Kerry Mitchell, Spirolateral-Type Images from Integer Sequences, 2013.
Kerry Mitchell, Spirolateral image for this sequence . [taken, with permission, from the Spirolateral-Type Images from Integer Sequences article]
Jan-Christoph Puchta and Jürgen Spilker, Altes und Neues zur Quersumme, Mathematische Semesterberichte, Vol. 49 (2002), pp. 209-226.
Jan-Christoph Puchta and Jürgen Spilker, Altes und Neues zur Quersumme.
Maxwell Schneider and Robert Schneider, Digit sums and generating functions, arXiv:1807.06710 [math.NT], 2018.
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. pp. 205-206).
Robert Walker, Self Similar Sloth Canon Number Sequences.
Eric Weisstein's World of Mathematics, Digit Sum.
Wikipedia, Digit sum.
Index entries for Colombian or self numbers and related sequences

Cf. A003132, A055012, A055013, A055014, A055015, A010888, A007954, A031347, A055017, A076313, A076314, A054899, A138470, A138471, A138472, A000120, A004426, A004427, A054683, A054684, A069877, A179082-A179085, A108971, A169964, A179987, A179988, A180018, A180019, A217928, A216407, A037123, A074784, A231688, A231689, A225693, A254524 (ordinal transform).
Bisections: A004092, A004155.
For n + digsum(n) see A062028.

a007953 n | n < 10 = n
          | otherwise = a007953 n' + r where (n',r) = divMod n 10
-- Reinhard Zumkeller, Nov 04 2011, Mar 19 2011

[ &+Intseq(n): n in [0..87] ];  // Bruno Berselli, May 26 2011

A007953 := proc(n) add(d,d=convert(n,base,10)) ; end proc: # R. J. Mathar, Mar 17 2011

Table[Sum[DigitCount[n][[i]] * i, {i, 9}], {n, 50}] (* Stefan Steinerberger, Mar 24 2006 *)
Table[Plus @@ IntegerDigits @ n, {n, 0, 87}] (* or *)
Nest[Flatten[# /. a_Integer -> Array[a + # &, 10, 0]] &, {0}, 2] (* Robert G. Wilson v, Jul 27 2006 *)
Total/@IntegerDigits[Range[0,90]] (* Harvey P. Dale, May 10 2016 *)
DigitSum[Range[0, 100]] (* Requires v. 14 *) (* Paolo Xausa, May 17 2024 *)

a(n)=if(n<1, 0, if(n%10, a(n-1)+1, a(n/10))) \\ Recursive, very inefficient. A more efficient recursive variant: a(n)=if(n>9, n=divrem(n, 10); n[2]+a(n[1]), n)

a(n, b=10)={my(s=(n=divrem(n, b))[2]); while(n[1]>=b, s+=(n=divrem(n[1], b))[2]); s+n[1]} \\ M. F. Hasler, Mar 22 2011

a(n)=sum(i=1, #n=digits(n), n[i]) \\ Twice as fast. Not so nice but faster:

a(n)=sum(i=1,#n=Vecsmall(Str(n)),n[i])-48*#n \\ M. F. Hasler, May 10 2015
/* Since PARI 2.7, one can also use: a(n)=vecsum(digits(n)), or better: A007953=sumdigits. [Edited and commented by M. F. Hasler, Nov 09 2018] */

a(n) = sumdigits(n); \\ Altug Alkan, Apr 19 2018

def A007953(n):
    return sum(int(d) for d in str(n)) # Chai Wah Wu, Sep 03 2014

def a(n): return sum(map(int, str(n))) # Michael S. Branicky, May 22 2021

(0 to 99).map(.toString.map(.toInt - 48).sum) // Alonso del Arte, Sep 15 2019

"Recursive version for general bases. Set base = 10 for this sequence."
digitalSum: base
| s |
base = 1 ifTrue: [^self].
(s := self // base) > 0
  ifTrue: [^(s digitalSum: base) + self - (s * base)]
  ifFalse: [^self]
"by Hieronymus Fischer, Mar 24 2014"

A007953(n): String(n).compactMap{$0.wholeNumberValue}.reduce(0, +) // Egor Khmara, Jun 15 2021

a(A051885(n)) = n.
a(n) <= 9(log_10(n)+1). - Stefan Steinerberger, Mar 24 2006
From Benoit Cloitre, Dec 19 2002: (Start)
a(0) = 0, a(10n+i) = a(n) + i for 0 <= i <= 9.
a(n) = n - 9*(Sum_{k > 0} floor(n/10^k)) = n - 9*A054899(n). (End)
From Hieronymus Fischer, Jun 17 2007: (Start)
G.f. g(x) = Sum_{k > 0, (x^k - x^(k+10^k) - 9x^(10^k))/(1-x^(10^k))}/(1-x).
a(n) = n - 9*Sum_{10 <= k <= n} Sum_{j|k, j >= 10} floor(log_10(j)) - floor(log_10(j-1)). (End)
From Hieronymus Fischer, Jun 25 2007: (Start)
The g.f. can be expressed in terms of a Lambert series, in that g(x) = (x/(1-x) - 9*L[b(k)](x))/(1-x) where L[b(k)](x) = sum{k >= 0, b(k)*x^k/(1-x^k)} is a Lambert series with b(k) = 1, if k > 1 is a power of 10, else b(k) = 0.
G.f.: g(x) = (Sum_{k > 0} (1 - 9*c(k))*x^k)/(1-x), where c(k) = Sum_{j > 1, j|k} floor(log_10(j)) - floor(log_10(j-1)).
a(n) = n - 9*Sum_{0 < k <= floor(log_10(n))} a(floor(n/10^k))*10^(k-1). (End)
From Hieronymus Fischer, Oct 06 2007: (Start)
a(n) <= 9*(1 + floor(log_10(n))), equality holds for n = 10^m - 1, m > 0.
lim sup (a(n) - 9*log_10(n)) = 0 for n -> oo.
lim inf (a(n+1) - a(n) + 9*log_10(n)) = 1 for n -> oo. (End)
a(n) = A138530(n, 10) for n > 9. - Reinhard Zumkeller, Mar 26 2008
a(A058369(n)) = A004159(A058369(n)); a(A000290(n)) = A004159(n). - Reinhard Zumkeller, Apr 25 2009
a(n) mod 2 = A179081(n). - Reinhard Zumkeller, Jun 28 2010
a(n) <= 9*log_10(n+1). - Vladimir Shevelev, Jun 01 2011
a(n) = a(n-1) + a(n-10) - a(n-11), for n < 100. - Alexander R. Povolotsky, Oct 09 2011
a(n) = Sum_{k >= 0} A031298(n, k). - Philippe Deléham, Oct 21 2011
a(n) = a(n mod b^k) + a(floor(n/b^k)), for all k >= 0. - Hieronymus Fischer, Mar 24 2014
Sum_{n>=1} a(n)/(n*(n+1)) = 10*log(10)/9 (Shallit, 1984). - Amiram Eldar, Jun 03 2021

More terms from Hieronymus Fischer, Jun 17 2007

Edited by Michel Marcus, Nov 11 2013

A055642 Number of digits in the decimal expansion of n.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3

Offset: 0

Henry Bottomley, Jun 06 2000

From Hieronymus Fischer, Jun 08 2012: (Start)
For n > 0 the first differences of A117804.
The total number of digits necessary to write down all the numbers 0, 1, 2, ..., n is A117804(n+1). (End)
Here a(0) = 1, but a different common convention is to consider that the expansion of 0 in any base b > 0 has 0 terms and digits. - M. F. Hasler, Dec 07 2018

			Examples:
999: 1 + floor(log_10(999)) = 1 + floor(2.x) = 1 + 2 = 3 or
      ceiling(log_10(999+1)) = ceiling(log_10(1000)) = ceiling(3) = 3;
1000: 1 + floor(log_10(1000)) = 1 + floor(3) = 1 + 3 = 4 or
      ceiling(log_10(1000+1)) = ceiling(log_10(1001)) = ceiling(3.x) = 4;
1001: 1 + floor(log_10(1001)) = 1 + floor(3.x) = 1 + 3 = 4 or
      ceiling(log_10(1001+1)) = ceiling(log_10(1002)) = ceiling(3.x) = 4;

Charles R Greathouse IV, Table of n, a(n) for n = 0..10000

Cf. A043537, A178788, A046034, A019546, A054899, A122840, A055640, A055641, A102669-A102685, A117804, A160093, A160094, A196563, A196564, A000120, A000788, A023416, A059015 (for base 2).
Cf. A262190, A262198.
Cf. A007953: sum of digits.

a055642 :: Integer -> Int
a055642 = length . show  -- Reinhard Zumkeller, Feb 19 2012, Apr 26 2011

[ #Intseq(n): n in [0..105] ];   //  Bruno Berselli, Jun 30 2011
(Common Lisp) (defun A055642 (n) (if (zerop n) 1 (floor (log n 10)))) ; James Spahlinger, Oct 13 2012

A055642 := proc(n)
        max(1,ilog10(n)+1) ;
end proc:  # R. J. Mathar, Nov 30 2011

Join[{1}, Array[ Floor[ Log[10, 10# ]] &, 104]] (* Robert G. Wilson v, Jan 04 2006 *)
Join[{1},Table[IntegerLength[n],{n,104}]]
IntegerLength[Range[0,120]] (* Harvey P. Dale, Jul 02 2016 *)

a(n)=#Str(n) \\ M. F. Hasler, Nov 17 2008

A055642(n)=logint(n+!n,10)+1 \\ Increasingly faster than the above, for larger n. (About twice as fast for n ~ 10^7.) - M. F. Hasler, Dec 07 2018

def a(n): return len(str(n))
print([a(n) for n in range(121)]) # Michael S. Branicky, May 10 2022

def A055642(n): # Faster than len(str(n)) from ~ 50 digits on
    L = math.log10(n or 1)
    if L.is_integer() and 10**int(L)>n: return int(L or 1)
    return int(L)+1  # M. F. Hasler, Apr 08 2024

a(A046760(n)) < A050252(A046760(n)); a(A046759(n)) > A050252(A046759(n)). - Reinhard Zumkeller, Jun 21 2011
a(n) = A196563(n) + A196564(n).
a(n) = 1 + floor(log_10(n)) = 1 + A004216(n) = ceiling(log_10(n+1)) = A004218(n+1), if n >= 1. - Daniel Forgues, Mar 27 2014
a(A046758(n)) = A050252(A046758(n)). - Reinhard Zumkeller, Jun 21 2011
a(n) = A117804(n+1) - A117804(n), n > 0. - Hieronymus Fischer, Jun 08 2012
G.f.: g(x) = 1 + (1/(1-x))*Sum_{j>=0} x^(10^j). - Hieronymus Fischer, Jun 08 2012
a(n) = A262190(n) for n < 100; a(A262198(n)) != A262190(A262198(n)). - Reinhard Zumkeller, Sep 14 2015

A005187 a(n) = a(floor(n/2)) + n; also denominators in expansion of 1/sqrt(1-x) are 2^a(n); also 2n - number of 1's in binary expansion of 2n.

Original entry on oeis.org

0, 1, 3, 4, 7, 8, 10, 11, 15, 16, 18, 19, 22, 23, 25, 26, 31, 32, 34, 35, 38, 39, 41, 42, 46, 47, 49, 50, 53, 54, 56, 57, 63, 64, 66, 67, 70, 71, 73, 74, 78, 79, 81, 82, 85, 86, 88, 89, 94, 95, 97, 98, 101, 102, 104, 105, 109, 110, 112, 113, 116, 117, 119, 120, 127, 128

Offset: 0

N. J. A. Sloane, May 20 1991; Allan Wilks, Dec 11 1999

Also exponent of the largest power of 2 dividing (2n)! (A010050) and (2n)!! (A000165).
Write n in binary: 1ab..yz, then a(n) = 1ab..yz + ... + 1ab + 1a + 1. - Ralf Stephan, Aug 27 2003
Also numbers having a partition into distinct Mersenne numbers > 0; A079559(a(n))=1; complement of A055938. - Reinhard Zumkeller, Mar 18 2009
Wikipedia's article on the "Whitney Immersion theorem" mentions that the a(n)-dimensional sphere arises in the Immersion Conjecture proved by Ralph Cohen in 1985. - Jonathan Vos Post, Jan 25 2010
For n > 0, denominators for consecutive pairs of integral numerator polynomials L(n+1,x) for the Legendre polynomials with o.g.f. 1 / sqrt(1-tx+x^2). - Tom Copeland, Feb 04 2016
a(n) is the total number of pointers in the first n elements of a perfect skip list. - Alois P. Heinz, Dec 14 2017
a(n) is the position of the n-th a (indexing from 0) in the fixed point of the morphism a -> aab, b -> b. - Jeffrey Shallit, Dec 24 2020
Numbers that can be expressed as the sum of distinct numbers of the form 2^k - 1 (lenient Mersenne numbers, A000225). This follows from the 2N - Hamming weight definition. A corollary is that these are the numbers with no 2 in their skew-binary representation (cf. A169683). - Allan C. Wechsler, Feb 25 2025

			G.f. = x + 3*x^2 + 4*x^3 + 7*x^4 + 8*x^5 + 10*x^6 + 11*x^7 + 15*x^8 + ...

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

N. J. A. Sloane, Table of n, a(n) for n = 0..20000 (first 1000 terms from T. D. Noe)
Jean-Paul Allouche, Jean Bétréma, and Jeffrey Shallit, Sur des points fixes de morphismes d'un monoïde libre, RAIRO-Theor. Inf. Appl. 23 (1989), 235-249.
Laurent Alonso, Edward M. Reingold, and René Schott, Determining the majority, Inform. Process. Lett. 47 (1993), no. 5, 253-255.
Laurent Alonso, Edward M. Reingold, and René Schott, The average-case complexity of determining the majority, SIAM J. Comput. 26 (1997), no. 1, 1-14.
Barry Brent, On the Constant Terms of Certain Laurent Series, Preprints (2023) 2023061164.
Sung-Hyuk Cha, On Integer Sequences Derived from Balanced k-ary Trees, Applied Mathematics in Electrical and Computer Engineering, 2012.
Sung-Hyuk Cha, On Complete and Size Balanced k-ary Tree Integer Sequences, International Journal of Applied Mathematics and Informatics, Issue 2, Volume 6, 2012, pp. 67-75. - From _N. J. A. Sloane_, Dec 24 2012
Ralph L. Cohen, The Immersion Conjecture for Differentiable Manifolds, The Annals of Mathematics, 1985: 237-328.
Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications, preprint, 2016.
Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications, ACM Transactions on Algorithms, 13:4 (2017), #47; DOI: 10.1145/3127585.
Keith Johnson and Kira Scheibelhut, Rational Polynomials That Take Integer Values at the Fibonacci Numbers, American Mathematical Monthly 123.4 (2016): 338-346. See p. 340.
Tanya Khovanova, There are no coincidences, arXiv preprint 1410.2193 [math.CO], 2014.
Anunay Kulshrestha, On Hamming Distance between base-n representations of whole numbers, arXiv:1203.4547 [cs.DM], 2012.
Michael E. Saks and Michael Werman, On computing majority by comparisons, Combinatorica 11 (1991), no. 4, 383-387.
Ralf Stephan, Some divide-and-conquer sequences ...
Ralf Stephan, Table of generating functions
Wikipedia, Whitney Immersion Theorem.
Allan Wilks, Email to N. J. A. Sloane, Jul 7 1988.

Cf. A001790, A011371, A067080, A098844, A132027, A004128, A054899, A046161.
Cf. A001511 (first differences), A122247 (partial sums), A055938 (complement).
Cf. A004134, A010050, A000165.
Cf. A000120, A079559, A085354, A030308, A000225.

a005187 n = a005187_list !! n
a005187_list = 0 : zipWith (+) [1..] (map (a005187 . (`div` 2)) [1..])
-- Reinhard Zumkeller, Nov 07 2011, Oct 05 2011

[n + Valuation(Factorial(n), 2): n in [0..70]]; // Vincenzo Librandi, Jun 11 2019

A005187 := n -> 2*n - add(i, i=convert(n, base, 2)):
seq(A005187(n), n=0..65); # Peter Luschny, Apr 08 2014

a[0] = 0; a[n_] := a[n] = a[Floor[n/2]] + n; Table[ a[n], {n, 0, 50}] (* or *)
Table[IntegerExponent[(2n)!, 2], {n, 0, 65}] (* Robert G. Wilson v, Apr 19 2006 *)
Table[2n-DigitCount[2n,2,1],{n,0,70}] (* Harvey P. Dale, May 24 2014 *)

{a(n) = if( n<0, 0, valuation((2*n)!, 2))}; /* Michael Somos, Oct 24 2002 */

{a(n) = if( n<0, 0, sum(k=1, n, (2*n)\2^k))}; /* Michael Somos, Oct 24 2002 */

{a(n) = if( n<0, 0, 2*n - subst( Pol( binary( n ) ), x, 1) ) }; /* Michael Somos, Aug 28 2007 */

a(n)=my(s=n);while(n>>=1,s+=n);s \\ Charles R Greathouse IV, Apr 07 2012

a(n)=2*n-hammingweight(n) \\ Charles R Greathouse IV, Jan 07 2013

def A005187(n): return 2*n-bin(n).count('1') # Chai Wah Wu, Jun 03 2021

@CachedFunction
def A005187(n): return A005187(n//2) + n if n > 0 else 0
[A005187(n) for n in range(66)]  # Peter Luschny, Dec 13 2012

a(n) = A011371(2n+1) = A011371(n) + n, n >= 0.
A046161(n) = 2^a(n).
For m>0, let q = floor(log_2(m)); a(2m+1) = 2^q + 3m + Sum_{k>=1} floor((m-2^q)/2^k); a(2m) = a(2m+1) - 1. - Len Smiley
a(n) = Sum_{k >= 0} floor(n/2^k) = n + A011371(n). - Henry Bottomley, Jul 03 2001
G.f.: A(x) = Sum_{k>=0} x^(2^k)/((1-x)*(1-x^(2^k))). - Ralf Stephan, Dec 24 2002
a(n) = Sum_{k=1..n} A001511(k), sum of binary Hamming distances between consecutive integers up to n. - Gary W. Adamson, Jun 15 2003
Conjecture: a(n) = 2n + O(log(n)). - Benoit Cloitre, Oct 07 2003 [true as a(n) = 2*n - hamming_weight(2*n). Joerg Arndt, Jun 10 2019]
Sum_{n=2^k..2^(k+1)-1} a(n) = 3*4^k - (k+4)*2^(k-1) = A085354(k). - Philippe Deléham, Feb 19 2004
From Hieronymus Fischer, Aug 14 2007: (Start)
Recurrence: a(n) = n + a(floor(n/2)); a(2n) = 2n + a(n); a(n*2^m) = 2*n*(2^m-1) + a(n).
  a(2^m) = 2^(m+1) - 1, m >= 0.
Asymptotic behavior: a(n) = 2n + O(log(n)), a(n+1) - a(n) = O(log(n)); this follows from the inequalities below.
a(n) <= 2n-1; equality holds for powers of 2.
a(n) >= 2n-1-floor(log_2(n)); equality holds for n = 2^m-1, m > 0.
lim inf (2n - a(n)) = 1, for n-->oo.
lim sup (2n - log_2(n) - a(n)) = 0, for n-->oo.
lim sup (a(n+1) - a(n) - log_2(n)) = 1, for n-->oo. (End)
a(n) = 2n - A000120(n). - Paul Barry, Oct 26 2007
PURRS demo results: Bounds for a(n) = n + a(n/2) with initial conditions a(1) = 1: a(n) >= -2 + 2*n - log(n)*log(2)^(-1), a(n) <= 1 + 2*n for each n >= 1. - Alexander R. Povolotsky, Apr 06 2008
If n = 2^a_1 + 2^a_2 + ... + 2^a_k, then a(n) = n-k. This can be used to prove that 2^n maximally divides (2n!)/n!. - Jon Perry, Jul 16 2009
a(n) = Sum_{k>=0} A030308(n,k)*A000225(k+1). - Philippe Deléham, Oct 16 2011
a(n) = log_2(denominator(binomial(-1/2,n))). - Peter Luschny, Nov 25 2011
a(2n+1) = a(2n) + 1. - M. F. Hasler, Jan 24 2015
a(n) = A004134(n) - n. - Cyril Damamme, Aug 04 2015
G.f.: (1/(1 - x))*Sum_{k>=0} (2^(k+1) - 1)*x^(2^k)/(1 + x^(2^k)). - Ilya Gutkovskiy, Jul 23 2017

A000788 Total number of 1's in binary expansions of 0, ..., n.

Original entry on oeis.org

0, 1, 2, 4, 5, 7, 9, 12, 13, 15, 17, 20, 22, 25, 28, 32, 33, 35, 37, 40, 42, 45, 48, 52, 54, 57, 60, 64, 67, 71, 75, 80, 81, 83, 85, 88, 90, 93, 96, 100, 102, 105, 108, 112, 115, 119, 123, 128, 130, 133, 136, 140, 143, 147, 151, 156, 159, 163, 167, 172, 176, 181, 186

Offset: 0

N. J. A. Sloane

Partial sums of A000120.
The graph of this sequence is a version of the Takagi curve: see Lagarias (2012), Section 9, especially Theorem 9.1. - N. J. A. Sloane, Mar 12 2016
a(n-1) is the largest possible number of ordered pairs (a,b) such that a/b is a prime in a subset of the positive integers with n elements. - Yifan Xie, Feb 21 2025

J.-P. Allouche & J. Shallit, Automatic sequences, Cambridge University Press, 2003, p. 94
R. Bellman and H. N. Shapiro, On a problem in additive number theory, Annals Math., 49 (1948), 333-340. See Eq. 1.9. [From N. J. A. Sloane, Mar 12 2009]
L. E. Bush, An asymptotic formula for the average sums of the digits of integers, Amer. Math. Monthly, 47 (1940), pp. 154-156. [From the bibliography of Stolarsky, 1977]
P. Cheo and S. Yien, A problem on the k-adic representation of positive integers (Chinese; English summary), Acta Math. Sinica, 5 (1955), pp. 433-438. [From the bibliography of Stolarsky, 1977]
M. P. Drazin and J. S. Griffith, On the decimal representation of integers, Proc. Cambridge Philos. Soc., (4), 48 (1952), pp. 555-565. [From the bibliography of Stolarsky, 1977]
E. N. Gilbert, Games of identification or convergence, SIAM Review, 4 (1962), 16-24.
Grabner, P. J.; Kirschenhofer, P.; Prodinger, H.; Tichy, R. F.; On the moments of the sum-of-digits function. Applications of Fibonacci numbers, Vol. 5 (St. Andrews, 1992), 263-271, Kluwer Acad. Publ., Dordrecht, 1993.
R. L. Graham, On primitive graphs and optimal vertex assignments, pp. 170-186 of Internat. Conf. Combin. Math. (New York, 1970), Annals of the NY Academy of Sciences, Vol. 175, 1970.
E. Grosswald, Properties of some arithmetic functions, J. Math. Anal. Appl., 28 (1969), pp.405-430.
Donald E. Knuth, The Art of Computer Programming, volume 3 Sorting and Searching, section 5.3.4, subsection Bitonic sorting, with C'(p) = a(p-1).
Hiu-Fai Law, Spanning tree congestion of the hypercube, Discrete Math., 309 (2009), 6644-6648 (see p(m) on page 6647).
Z. Li and E. M. Reingold, Solution of a divide-and-conquer maximin recurrence, SIAM J. Comput., 18 (1989), 1188-1200.
B. Lindström, On a combinatorial problem in number theory, Canad. Math. Bull., 8 (1965), 477-490.
Mauclaire, J.-L.; Murata, Leo; On q-additive functions. I. Proc. Japan Acad. Ser. A Math. Sci. 59 (1983), no. 6, 274-276.
Mauclaire, J.-L.; Murata, Leo; On q-additive functions. II. Proc. Japan Acad. Ser. A Math. Sci. 59 (1983), no. 9, 441-444.
M. D. McIlroy, The number of 1's in binary integers: bounds and extremal properties, SIAM J. Comput., 3 (1974), 255-261.
L. Mirsky, A theorem on representations of integers in the scale of r, Scripta Math., 15 (1949), pp. 11-12.
I. Shiokawa, On a problem in additive number theory, Math. J. Okayama Univ., 16 (1974), pp.167-176. [From the bibliography of Stolarsky, 1977]
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
K. B. Stolarsky, Power and exponential sums of digital sums related to binomial coefficient parity, SIAM J. Appl. Math., 32 (1977), 717-730.
Trollope, J. R. An explicit expression for binary digital sums. Math. Mag. 41 1968 21-25.

T. D. Noe and Hieronymus Fischer, Table of n, a(n) for n = 0..10000 (terms up to n=1000 by T. D. Noe).
G. Agnarsson, On the number of hypercubic bipartitions of an integer, arXiv preprint arXiv:1106.4997 [math.CO], 2011.
G. Agnarsson, Induced subgraphs of hypercubes, arXiv preprint arXiv:1112.3015 [math.CO], 2011.
G. Agnarsson and K. Lauria, Extremal subgraphs of the d-dimensional grid graph, arXiv preprint arXiv:1302.6517 [math.CO], 2013.
J.-P. Allouche, On an Inequality in a 1970 Paper of R. L. Graham, INTEGERS 21A (2021), #A2.
Mathias Hauan Arbo, Esten Ingar Grøtli, and Jan Tommy Gravdahl, CASCLIK: CasADi-Based Closed-Loop Inverse Kinematics, arXiv:1901.06713 [cs.RO], 2019.
Venkata Sai Narayana Bavisetty, Matthew Wheeler, Reinhard Laubenbacher, and Claus Kadelka, Upper bound for the stability of Boolean networks, arXiv:2506.12310 [q-bio.MN], 2025. See p. 8.
Johann Cigler, A curious class of Hankel determinants, arXiv:1803.05164 [math.CO], 2018.
G. F. Clements and B. Lindström, A sequence of (+-1) determinants with large values, Proc. Amer. Math. Soc., 16 (1965), pp. 548-550. [From the bibliography of Stolarsky, 1977]
Jean Coquet, Power sums of digital sums, J. Number Theory 22 (1986), no. 2, 161-176.
H. Delange, Sur la fonction sommatoire de la fonction "somme des chiffres", Enseignement Math., (2), 21 (1975), pp. 31-47. [From the bibliography of Stolarsky, 1977]
Laurent Feuilloley, Brief Announcement: Average Complexity for the LOCAL Model, arXiv preprint arXiv:1505.05072 [cs.DC], 2015.
S. R. Finch, P. Sebah and Z.-Q. Bai, Odd Entries in Pascal's Trinomial Triangle, arXiv:0802.2654 [math.NT], 2008.
Oscar E. González, An observation of Rankin on Hankel determinants, Department of Mathematics, University of Illinois at Urbana-Champaign, 2018.
P. J. Grabner and H.-K. Hwang, Digital sums and divide-and-conquer recurrences: Fourier expansions and absolute convergence
Milton W. Green, Letter to N. J. A. Sloane, 1973 (note "A360" refers to N0360 which is the present sequence).
Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications, Preprint 2016.
Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications, ACM Transactions on Algorithms, 13:4 (2017), #47; DOI: 10.1145/3127585.
Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, Identities and periodic oscillations of divide-and-conquer recurrences splitting at half, arXiv:2210.10968 [cs.DS], 2022, p. 36 and 44.
Jeffrey C. Lagarias, The Takagi function and its properties, arXiv:1112.4205 [math.CA], 2011-2012.
Jeffrey C. Lagarias, The Takagi function and its properties, In Functions in number theory and their probabilistic aspects, 153--189, RIMS Kôkyûroku Bessatsu, B34, Res. Inst. Math. Sci. (RIMS), Kyoto, 2012. MR3014845.
Julien Leroy, Michel Rigo, and Manon Stipulanti, Behavior of Digital Sequences Through Exotic Numeration Systems, Electronic Journal of Combinatorics 24(1) (2017), #P1.44.
Raoul Nakhmanson-Kulish, Graphic representation of K(n)=a(n)/(n log2(n)/2) from n=63 to 131071
D. J. Newman, On the number of binary digits in a multiple of three, Proc. Amer. Math. Soc., 21 (1969), pp. 719-721. [From the bibliography of Stolarsky, 1977]
Ralf Stephan, Some divide-and-conquer sequences ...
Ralf Stephan, Table of generating functions
S. C. Tang, An improvement and generalization of Bellman-Shapiro's theorem on a problem in additive number theory, Proc. Amer. Math. Soc., 14 (1963), pp. 199-204. [From the bibliography of Stolarsky, 1977]
Eric Weisstein's World of Mathematics, Binary
David W. Wilson, Fast C++ function for computing a(n)
Index entries for sequences related to binary expansion of n

For number of 0's in binary expansion of 0, ..., n see A059015.
The basic sequences concerning the binary expansion of n are A000120, A000788, A000069, A001969, A023416, A059015, A070939, A083652.
Cf. A005183, A360189.
Cf. A027868, A037123, A054899, A055640, A055641, A102669-A102685, A117804, A122840, A122841, A160093, A160094, A196563, A196564 (for base 10).

a000788_list = scanl1 (+) A000120_list
-- Walt Rorie-Baety, Jun 30 2012

{a000788 0 = 0; a00788 n = a000788 n2 + a000788 (n-n2-1) + (n-n2) where n2 = n `div` 2}
-- Walt Rorie-Baety, Jul 15 2012

a:= proc(n) option remember; `if`(n=0, 0, a(n-1)+add(i, i=Bits[Split](n))) end:
seq(a(n), n=0..62);  # Alois P. Heinz, Nov 11 2024

a[n_] := Count[ Table[ IntegerDigits[k, 2], {k, 0, n}], 1, 2]; Table[a[n], {n, 0, 62}] (* Jean-François Alcover, Dec 16 2011 *)
Table[Plus@@Flatten[IntegerDigits[Range[n], 2]], {n, 0, 62}] (* Alonso del Arte, Dec 16 2011 *)
Accumulate[DigitCount[Range[0,70],2,1]] (* Harvey P. Dale, Jun 08 2013 *)

A000788(n)={ n<3 && return(n); if( bittest(n,0) \\
, n+1 == 1<A000788(n>>1)*2+n>>1+1 \\
, n == 1<A000788(n>>=1)+A000788(n-1)+n )} \\ M. F. Hasler, Nov 22 2009

a(n)=sum(k=1,n,hammingweight(k)) \\ Charles R Greathouse IV, Oct 04 2013

a(n) = if (n==0, 0, m = logint(n, 2); r = n % 2^m; m*2^(m-1) + r + 1 + a(r)); \\ Michel Marcus, Mar 27 2018

a(n)={n++; my(t, i, s); c=n; while(c!=0, i++; c\=2); for(j=1, i, d=(n\2^(i-j))%2; t+=(2^(i-j)*(s*d+d*(i-j)/2)); s+=d); t} \\ David A. Corneth, Nov 26 2024
(C++) /* See David W. Wilson link. */

def A000788(n): return sum(i.bit_count() for i in range(1,n+1)) # Chai Wah Wu, Mar 01 2023

def A000788(n): return (n+1)*n.bit_count()+(sum((m:=1<>j)-(r if n<<1>=m*(r:=k<<1|1) else 0)) for j in range(1,n.bit_length()+1))>>1) # Chai Wah Wu, Nov 11 2024

McIlroy (1974) gives bounds and recurrences. - N. J. A. Sloane, Mar 24 2014
Stolarsky (1977) studies the asymptotics, and gives at least nine references to earlier work on the problem. I have added all the references that were not here already. - N. J. A. Sloane, Apr 06 2014
a(n) = Sum_{k=1..n} A000120(k). - Benoit Cloitre, Dec 19 2002
a(0) = 0, a(2n) = a(n)+a(n-1)+n, a(2n+1) = 2a(n)+n+1. - Ralf Stephan, Sep 13 2003
a(n) = n*log_2(n)/2 + O(n); a(2^n)=n*2^(n-1)+1. - Benoit Cloitre, Sep 25 2003 (The first result is due to Bellman and Shapiro, - N. J. A. Sloane, Mar 24 2014)
a(n) = n*log_2(n)/2+n*F(log_2(n)) where F is a nowhere differentiable continuous function of period 1 (see Allouche & Shallit). - Benoit Cloitre, Jun 08 2004
G.f.: (1/(1-x)^2) * Sum_{k>=0} x^2^k/(1+x^2^k). - Ralf Stephan, Apr 19 2003
a(2^n-1) = A001787(n) = n*2^(n-1). - M. F. Hasler, Nov 22 2009
a(4^n-2) = n(4^n-2).
For real n, let f(n) = [n]/2 if [n] even, n-[n+1]/2 otherwise. Then a(n) = Sum_{k>=0} 2^k*f((n+1)/2^k).
a(A000225(n)) = A173921(A000225(n)) = A001787(n); a(A000079(n)) = A005183(n). - Reinhard Zumkeller, Mar 04 2010
From Hieronymus Fischer, Jun 10 2012: (Start)
a(n) = (1/2)*Sum_{j=1..m+1} (floor(n/2^j + 1/2)*(2n + 2 - floor(n/2^j + 1/2))*2^j - floor(n/2^j)*(2n + 2 - (1 + floor(n/2^j)) * 2^j)), where m=floor(log_2(n)).
a(n) = (n+1)*A000120(n) - 2^(m-1) + 1/4 + (1/2)*Sum_{j=1..m+1} ((floor(n/2^j) + 1/2)^2 - floor(n/2^j + 1/2)^2)*2^j, where m=floor(log_2(n)).
a(2^m-1) = m*2^(m-1).
(This is the total number of '1' digits occurring in all the numbers with <= m bits.)
Generic formulas for the number of digits >= d in the base p representations of all integers from 0 to n, where 1<= d < p.
a(n) = (1/2)*Sum_{j=1..m+1} (floor(n/p^j + (p-d)/p)*(2n + 2 + ((p-2*d)/p - floor(n/p^j + (p-d)/p))*p^j) - floor(n/p^j)*(2n + 2 - (1+floor(n/p^j)) * p^j)), where m=floor(log_p(n)).
a(n) = (n+1)*F(n,p,d) + (1/2)*Sum_{j=1..m+1} ((((p-2*d)/p)*floor(n/p^j+(p-d)/p) + floor(n/p^j))*p^j - (floor(n/p^j+(p-d)/p)^2 - floor(n/p^j)^2)*p^j), where m=floor(log_p(n)) and F(n,p,d) = number of digits >= d in the base p representation of n.
a(p^m-1) = (p-d)*m*p^(m-1).
(This is the total number of digits >= d occurring in all the numbers  with <= m digits in base p representation.)
G.f.: g(x) = (1/(1-x)^2)*Sum_{j>=0} (x^(d*p^j) - x^(p*p^j))/(1-x^(p*p^j)). (End)
a(n) = Sum_{k=1..n} A000120(A240857(n,k)). - Reinhard Zumkeller, Apr 14 2014
For n > 0, if n is written as 2^m + r with 0 <= r < 2^m, then a(n) = m*2^(m-1) + r + 1 + a(r). - Shreevatsa R, Mar 20 2018
a(n) = n*(n+1)/2 + Sum_{k=1..floor(n/2)} ((2k-1)((g(n,k)-1)*2^(g(n,k) + 1) + 2) - (n+1)*(g(n,k)+1)*g(n,k)/2), where g(n,k) = floor(log_2(n/(2k-1))). - Fabio Visonà, Mar 17 2020
From Jeffrey Shallit, Aug 07 2021: (Start)
A 2-regular sequence, satisfying the identities
a(4n+1) = -a(2n) + a(2n+1) + a(4n)
a(4n+2) = -2a(2n) + 2a(2n+1) + a(4n)
a(4n+3) = -4a(n) + 4a(2n+1)
a(8n) = 4a(n) - 8a(2n) + 5a(4n)
a(8n+4) = -9a(2n) + 5a(2n+1) + 4a(4n)
for n>=0. (End)
a(n) = Sum_{k=0..floor(log_2(n+1))} k * A360189(n,k). - Alois P. Heinz, Mar 06 2023

More terms from Larry Reeves (larryr(AT)acm.org), Jan 15 2001

A027868 Number of trailing zeros in n!; highest power of 5 dividing n!.

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 15, 15, 15, 15, 15, 16, 16, 16, 16, 16, 18, 18, 18, 18, 18, 19

Offset: 0

Warut Roonguthai

Also the highest power of 10 dividing n! (different from A054899). - Hieronymus Fischer, Jun 18 2007
Alternatively, a(n) equals the expansion of the base-5 representation A007091(n) of n (i.e., where successive positions from right to left stand for 5^n or A000351(n)) under a scale of notation whose successive positions from right to left stand for (5^n - 1)/4 or A003463(n); for instance, n = 7392 has base-5 expression 2*5^5 + 1*5^4 + 4*5^3 + 0*5^2 + 3*5^1 + 2*5^0, so that a(7392) = 2*781 + 1*156 + 4*31 + 0*6 + 3*1 + 2*0 = 1845. - Lekraj Beedassy, Nov 03 2010
Partial sums of A112765. - Hieronymus Fischer, Jun 06 2012
Also the number of trailing zeros in A000165(n) = (2*n)!!. - Stefano Spezia, Aug 18 2024

			a(100)  = 24.
a(10^3) = 249.
a(10^4) = 2499.
a(10^5) = 24999.
a(10^6) = 249998.
a(10^7) = 2499999.
a(10^8) = 24999999.
a(10^9) = 249999998.
a(10^n) = 10^n/4 - 3 for 10 <= n <= 15 except for a(10^14) = 10^14/4 - 2. - _M. F. Hasler_, Dec 27 2019

M. Gardner, "Factorial Oddities." Ch. 4 in Mathematical Magic Show: More Puzzles, Games, Diversions, Illusions and Other Mathematical Sleight-of-Mind from Scientific American. New York: Vintage, 1978, pp. 50-65.

Hieronymus Fischer, Table of n, a(n) for n = 0..10000 (first 1000 terms from T. D. Noe)
David S. Hart, James E. Marengo, Darren A. Narayan, and David S. Ross, On the number of trailing zeros in n!, College Math. J., 39(2):139-145, 2008.
Enrique Pérez Herrero, Trailing Zeros in n!, Psychedelic Geometry Blogspot.
Soichi Ikeda and Kaneaki Matsuoka, On transcendental numbers generated by certain integer sequences, Siauliai Math. Semin., 8 (16) 2013, 63-69.
Shyam Sunder Gupta, Fascinating Factorials, Exploring the Beauty of Fascinating Numbers, Springer (2025) Ch. 16, 411-442.
Shu-Chung Liu and Jean C.-C. Yeh, Catalan numbers modulo 2^k, J. Int. Seq. 13 (2010), 10.5.4, eq (5).
Antonio M. Oller-Marcén, A new look at the trailing zeros of n!, arXiv:0906.4868v1 [math.NT], 2009.
Antonio M. Oller-Marcén and J. Maria Grau, On the Base-b Expansion of the Number of Trailing Zeros of b^k!, J. Int. Seq. 14 (2011) 11.6.8
Eric Weisstein's World of Mathematics, Factorial.
Index entries for sequences related to factorial numbers

See A000966 for the missing numbers. See A011371 and A054861 for analogs involving powers of 2 and 3.
Cf. A054899, A007953, A112765, A067080, A098844, A132027, A067080, A098844, A132029, A054999, A112765, A191610, A000351.
Cf. also A000142, A004154.
Cf. A000165, A008904.

a027868 n = sum $ takeWhile (> 0) $ map (n `div`) $ tail a000351_list
-- Reinhard Zumkeller, Oct 31 2012

[Valuation(Factorial(n), 5): n in [0..80]]; // Bruno Berselli, Oct 11 2021

0, seq(add(floor(n/5^i),i=1..floor(log[5](n))), n=1..100); # Robert Israel, Nov 13 2014

Table[t = 0; p = 5; While[s = Floor[n/p]; t = t + s; s > 0, p *= 5]; t, {n, 0, 100} ]
Table[ IntegerExponent[n!], {n, 0, 80}] (* Robert G. Wilson v *)
zOF[n_Integer?Positive]:=Module[{maxpow=0},While[5^maxpow<=n,maxpow++];Plus@@Table[Quotient[n,5^i],{i,maxpow-1}]]; Attributes[zOF]={Listable}; Join[{0},zOF[ Range[100]]] (* Harvey P. Dale, Apr 11 2022 *)

a(n)={my(s);while(n\=5,s+=n);s} \\ Charles R Greathouse IV, Nov 08 2012, edited by M. F. Hasler, Dec 27 2019

a(n)=valuation(n!,5) \\ Charles R Greathouse IV, Nov 08 2012

apply( A027868(n)=(n-sumdigits(n,5))\4, [0..99]) \\ M. F. Hasler, Dec 27 2019

from sympy import multiplicity
A027868, p5 = [0,0,0,0,0], 0
for n in range(5,10**3,5):
    p5 += multiplicity(5,n)
    A027868.extend([p5]*5) # Chai Wah Wu, Sep 05 2014

def A027868(n): return 0 if n<5 else n//5 + A027868(n//5) # David Radcliffe, Jun 26 2016

from sympy.ntheory.factor_ import digits
def A027868(n): return n-sum(digits(n,5)[1:])>>2 # Chai Wah Wu, Oct 18 2024

a(n) = Sum_{i>=1} floor(n/5^i).
a(n) = (n - A053824(n))/4.
From Hieronymus Fischer, Jun 25 2007 and Aug 13 2007, edited by M. F. Hasler, Dec 27 2019: (Start)
G.f.: g(x) = Sum_{k>0} x^(5^k)/(1-x^(5^k))/(1-x).
a(n) = Sum_{k=5..n} Sum_{j|k, j>=5} (floor(log_5(j)) - floor(log_5(j-1))).
G.f.: g(x) = L[b(k)](x)/(1-x) where L[b(k)](x) = Sum_{k>=0} b(k)*x^k/(1-x^k) is a Lambert series with b(k) = 1, if k>1 is a power of 5, else b(k) = 0.
G.f.: g(x) = Sum_{k>0} c(k)*x^k/(1-x), where c(k) = Sum_{j>1, j|k} floor(log_5(j)) - floor(log_5(j - 1)).
Recurrence:
a(n) = floor(n/5) + a(floor(n/5));
a(5*n) = n + a(n);
a(n*5^m) = n*(5^m-1)/4 + a(n).
a(k*5^m) = k*(5^m-1)/4, for 0 <= k < 5, m >= 0.
Asymptotic behavior:
a(n) = n/4 + O(log(n)),
a(n+1) - a(n) = O(log(n)), which follows from the inequalities below.
a(n) <= (n-1)/4; equality holds for powers of 5.
a(n) >= n/4 - 1 - floor(log_5(n)); equality holds for n = 5^m-1, m > 0.
lim inf (n/4 - a(n)) = 1/4, for n -> oo.
lim sup (n/4 - log_5(n) - a(n)) = 0, for n -> oo.
lim sup (a(n+1) - a(n) - log_5(n)) = 0, for n -> oo.
(End)
a(n) <= A027869(n). - Reinhard Zumkeller, Jan 27 2008
10^a(n) = A000142(n) / A004154(n). - Reinhard Zumkeller, Nov 24 2012
a(n) = Sum_{k=1..floor(n/2)} floor(log_5(n/k)). - Ammar Khatab, Feb 01 2025

Examples added by Hieronymus Fischer, Jun 06 2012

A112765 Exponent of highest power of 5 dividing n. Or, 5-adic valuation of n.

Original entry on oeis.org

0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 2, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 2, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 2, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 2, 0, 0, 0, 0, 1

Offset: 1

Reinhard Zumkeller, Sep 18 2005

A027868 gives partial sums.

This is also the 5-adic valuation of Fibonacci(n). See Lengyel link. - Michel Marcus, May 06 2017

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Dario T. de Castro, P-adic Order of Positive Integers via Binomial Coefficients, INTEGERS, Electronic J. of Combinatorial Number Theory, Vol. 22, Paper A61, 2022.
T. Lengyel, The order of the Fibonacci and Lucas numbers, Fibonacci Quart. 33 (1995), no. 3, 234-239. See Lemma 1 p. 235.

Cf. A007814, A007949, A112762, A022337, A122840, A027868, A054899, A122841, A160093, A160094, A196563, A196564.

Cf. A343251, A000351 (positions of records, greedy inverse).

a112765 n = fives n 0 where
   fives n e | r > 0     = e
             | otherwise = fives n' (e + 1) where (n',r) = divMod n 5
-- Reinhard Zumkeller, Apr 08 2011

A112765 := proc(n)
    padic[ordp](n,5) ;
end proc: # R. J. Mathar, Jul 12 2016

a[n_] := IntegerExponent[n, 5]; Array[a, 105] (* Jean-François Alcover, Jan 25 2018 *)

A112765(n)=valuation(n,5); /* Joerg Arndt, Apr 08 2011 */

def a(n):
    k = 0
    while n > 0 and n%5 == 0: n //= 5; k += 1
    return k
print([a(n) for n in range(1, 106)]) # Michael S. Branicky, Aug 06 2021

Totally additive with a(p) = 1 if p = 5, 0 otherwise.
From Hieronymus Fischer, Jun 08 2012: (Start)
With m = floor(log_5(n)), frac(x) = x-floor(x):
a(n) = Sum_{j=1..m} (1 - ceiling(frac(n/5^j))).
a(n) = m + Sum_{j=1..m} (floor(-frac(n/5^j))).
a(n) = A027868(n) - A027868(n-1).
G.f.: Sum_{j>0} x^5^j/(1-x^5^j). (End)
a(5n) = A055457(n). - R. J. Mathar, Jul 17 2012
Asymptotic mean: lim_{m->oo} (1/m) * Sum_{k=1..m} a(k) = 1/4. - Amiram Eldar, Feb 14 2021
a(n) = 5*Sum_{j=1..floor(log(n)/log(5))} frac(binomial(n, 5^j)*5^(j-1)/n). - Dario T. de Castro, Jul 10 2022

A055641 Number of zero digits in n.

Original entry on oeis.org

1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 1, 1, 1, 1, 1

Offset: 0

Henry Bottomley, Jun 06 2000

			a(99) = 0 because the digits of 99 are 9 and 9, a(100) = 2 because the digits of 100 are 1, 0 and 0 and there are two 0's.

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

Cf. A011540, A004719, A052382, A054899, A055640, A102669-A102685, A122840, A160093, A160094, A196563, A195564, A000120, A000788, A023416, A059015 (for base 2), A085974.

a055641 n | n < 10    = 0 ^ n
          | otherwise = a055641 n' + 0 ^ d where (n',d) = divMod n 10
-- Reinhard Zumkeller, Apr 30 2013

Array[Last@ DigitCount@ # &, 105] (* Michael De Vlieger, Jul 02 2015 *)

a(n)=if(n,n=digits(n); sum(i=2,#n,n[i]==0), 1) \\ Charles R Greathouse IV, Sep 13 2015

A055641(n)=#select(d->!d,digits(n))+!n \\ M. F. Hasler, Jun 22 2018

def a(n): return str(n).count("0")
print([a(n) for n in range(106)]) # Michael S. Branicky, May 26 2022

From Hieronymus Fischer, Jun 06 2012: (Start)
a(n) = m + 1 - A055640(n) = Sum_{j=1..m+1} (1 + floor(n/10^j) - floor(n/10^j+0.9)), where m = floor(log_10(n)).
G.f.: g(x) = 1 + (1/(1-x))*Sum_{j>=0} (x^(10*10^j) - x^(11*10^j))/(1-x^10^(j+1)). (End)
a(n) = if n<10 then A000007(n) else a(A059995(n)) + A000007(A010879(n)). - Reinhard Zumkeller, Apr 30 2013, corrected by M. F. Hasler, Jun 22 2018

A054861 Greatest k such that 3^k divides n!.

Original entry on oeis.org

0, 0, 0, 1, 1, 1, 2, 2, 2, 4, 4, 4, 5, 5, 5, 6, 6, 6, 8, 8, 8, 9, 9, 9, 10, 10, 10, 13, 13, 13, 14, 14, 14, 15, 15, 15, 17, 17, 17, 18, 18, 18, 19, 19, 19, 21, 21, 21, 22, 22, 22, 23, 23, 23, 26, 26, 26, 27, 27, 27, 28, 28, 28, 30, 30, 30, 31, 31, 31, 32, 32, 32, 34, 34, 34, 35, 35

Offset: 0

Henry Bottomley, May 22 2000

Also the number of trailing zeros in the base-3 representation of n!. - Hieronymus Fischer, Jun 18 2007
Also the highest power of 6 dividing n!. - Hieronymus Fischer, Aug 14 2007
A column of A090622. - Alois P. Heinz, Oct 05 2012
The 'missing' values are listed in A096346. - Stanislav Sykora, Jul 16 2014

			a(100) = 48.
a(10^3) = 498.
a(10^4) = 4996.
a(10^5) = 49995.
a(10^6) = 499993.
a(10^7) = 4999994.
a(10^8) = 49999990.
a(10^9) = 499999993.

Hieronymus Fischer, Table of n, a(n) for n = 0..10000 (first 1000 terms from T. D. Noe)
S-C Liu and J. C.-C. Yeh, Catalan numbers modulo 2^k, J. Int. Seq. 13 (2010), 10.5.4, Eq. (5).
A. M. Oller-Marcen and J. Maria Grau, On the Base-b Expansion of the Number of Trailing Zeros of b^k!, J. Int. Seq. 14 (2011) 11.6.8

Cf. A011371 (for analog involving powers of 2). See also A027868.
Cf. A004128 (for a(3n)).
Cf. A000142, A007949, A053735, A054895, A054899, A067080, A096396, A098844, A132027.

[Valuation(Factorial(n), 3): n in [0..80]]; // Bruno Berselli, Aug 05 2013

A054861 := proc(n)
    (n - convert(convert(n, base, 3), `+`))/2 ;
end proc:
seq(A054861(n),n=0..1000) ; # Robert Israel, Jul 17 2014

(Plus@@Floor[#/3^Range[Length[IntegerDigits[#,3]]-1]]&)/@Range[0,100] (* Peter J. C. Moses, Apr 07 2012 *)
FoldList[Plus, 0, IntegerExponent[Range[100], 3]] (* T. D. Noe, Apr 10 2012 *)
Table[IntegerExponent[n!,3],{n,0,80}] (* Harvey P. Dale, Feb 05 2015 *)

a(n)=my(s);while(n\=3,s+=n);s \\ Charles R Greathouse IV, Jul 25 2011

a(n)=(n - vecsum(digits(n,3)))\2; \\ Gheorghe Coserea, Jan 01 2018

def A054861(n):
    A004128 = lambda n: A004128(n//3) + n if n > 0 else 0
    return A004128(n//3)
[A054861(i) for i in (0..76)]  # Peter Luschny, Nov 16 2012

a(n) = floor(n/3) + floor(n/9) + floor(n/27) + floor(n/81) + ... .
a(n) = (n - A053735(n))/2.
a(n+1) = Sum_{k=1..n} A007949(k). - Benoit Cloitre, Mar 24 2002
From Hieronymus Fischer, Jun 18, Jun 25 and Aug 14 2007: (Start)
G.f.: (1/(1-x))*Sum_{k>0} x^(3^k)/(1-x^(3^k)).
a(n) = Sum_{k=3..n} Sum_{j>=3, j|k} (floor(log_3(j)) - floor(log_3(j-1))).
G.f.: L[b(k)](x)/(1-x), where L[b(k)](x) = Sum_{k>=0} b(k)*x^k/(1-x^k) is a Lambert series with b(k) = 1, if k>1 is a power of 3, otherwise b(k)=0.
G.f.: (1/(1-x))*Sum_{k>0} c(k)*x^k, where c(k) = Sum_{j>1, j|k} (floor(log_3(j)) - floor(log_3(j-1))).
Recurrence:
a(n) = floor(n/3) + a(floor(n/3));
a(3*n) = n + a(n);
a(n*3^m) = n*(3^m-1)/2 + a(n).
a(k*3^m) = k*(3^m-1)/2, for 0 <= k < 3, m >= 0.
Asymptotic behavior:
a(n) = n/2 + O(log(n)),
a(n+1) - a(n) = O(log(n)); this follows from the inequalities below.
a(n) <= (n-1)/2; equality holds for powers of 3.
a(n) >= (n-2)/2 - floor(log_3(n)); equality holds for n = 3^m - 1, m > 0.
lim inf (n/2 - a(n)) = 1/2 for n->oo.
lim sup (n/2 - log_3(n) - a(n)) = 0 for n->oo.
lim sup (a(n+1) - a(n) - log_3(n)) = 0 for n->oo. (End)
a(n) = A007949(n!). - R. J. Mathar, Sep 03 2016
From R. J. Mathar, Jul 08 2021: (Start)
a(n) = A122841(n!).
Partial sums of A007949. (End)
a(n) = A007949(A000142(n)). - David A. Corneth, Nov 02 2023

Examples added by Hieronymus Fischer, Jun 06 2012

New name by David A. Corneth, Nov 02 2023

A122840 a(n) is the number of 0's at the end of n when n is written in base 10.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0

Offset: 1

Reinhard Zumkeller, Sep 13 2006

Greatest k such that 10^k divides n.
a(n) = the number of digits in n - A160093(n).
a(A005117(n)) <= 1. - Reinhard Zumkeller, Mar 30 2010
See A054899 for the partial sums. - Hieronymus Fischer, Jun 08 2012
From Amiram Eldar, Mar 10 2021: (Start)
The asymptotic density of the occurrences of k is 9/10^(k+1).
The asymptotic mean of this sequence is 1/9. (End)

			a(160) = 1 because there is 1 zero at the end of 160 when 160 is written in base 10.

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
S. Ikeda and K. Matsuoka, On transcendental numbers generated by certain integer sequences, Siauliai Math. Semin., 8 (16) 2013, 63-69.

A007814 is the base 2 equivalent of this sequence.

Cf. A160094, A160093, A001511, A070940, A122841, A027868, A054899, A196563, A196564, A004151, A112765.

a122840 n = if n < 10 then 0 ^ n else 0 ^ d * (a122840 n' + 1)
            where (n', d) = divMod n 10
-- Reinhard Zumkeller, Mar 09 2013

a[n_] := IntegerExponent[n, 10]; Array[a, 100] (* Amiram Eldar, Mar 10 2021 *)

a(n)=valuation(n,10) \\ Charles R Greathouse IV, Feb 26 2014

def a(n): return len(str(n)) - len(str(int(str(n)[::-1]))) # Indranil Ghosh, Jun 09 2017

def A122840(n): return len(s:=str(n))-len(s.rstrip('0')) # Chai Wah Wu, Jul 06 2022

A122840 = lambda n: sympy.multiplicity(10,n) # M. F. Hasler, Apr 05 2024

a(n) = A160094(n) - 1.
From Hieronymus Fischer, Jun 08 2012: (Start)
With m = floor(log_10(n)), frac(x) = x-floor(x):
a(n) = Sum_{j=1..m} (1 - ceiling(frac(n/10^j))).
a(n) = m + Sum_{j=1..m} (floor(-frac(n/10^j))).
a(n) = A054899(n) - A054899(n-1).
G.f.: g(x) = Sum_{j>0} x^10^j/(1-x^10^j). (End)
a(n) = min(A007814(n), A112765(n)). - Jianing Song, Jul 23 2022

A055640 Number of nonzero digits in decimal expansion of n.

Original entry on oeis.org

0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2

Offset: 0

Henry Bottomley, Jun 06 2000

Comment from Antti Karttunen, Sep 05 2004: (Start)
Also number of characters needed to write the number n in classical Greek alphabetic system, up to n=999. The Greek alphabetic system assigned values to the letters as follows:
alpha = 1, beta = 2, gamma = 3, delta = 4, epsilon = 5, digamma = 6, zeta = 7, eta = 8, theta = 9, iota = 10, kappa = 20, lambda = 30, mu = 40, nu = 50, xi = 60, omicron = 70, pi = 80, koppa = 90, rho = 100, sigma = 200, tau = 300, upsilon = 400, phi = 500, chi = 600, psi = 700, omega = 800, sampi = 900. (End)
For partial sums see A102685. - Hieronymus Fischer, Jun 06 2012

			129 is written as rho kappa theta in the old Greek system.

L. Threatte, The Greek Alphabet, in The World's Writing Systems, edited by Peter T. Daniels and William Bright, Oxford Univ. Press, 1996, p. 278.

Hieronymus Fischer, Table of n, a(n) for n = 0..10000
Unicode Consortium, Unicode Home Page. (Follow the link "Display Problems?" to find an appropriate information/font file to show the Greek characters correctly. Or look at the HTML source to see their names.)

Cf. A102669-A102685, A004719, A011540, A052382, A061745, A054899, A055641, A055642, A122840, A160093, A160094, A193238, A196563, A195564, A000120, A000788, A023416, A059015 (for base 2).

Differs from A098378 for the first time at position n=200 with a(200)=1, as only one nonzero Arabic digit (and only one Greek letter) is needed for two hundred, while A098378(200)=2 as two characters are needed in the Ethiopic system.

a055640 n = length $ filter (/= '0') $ show n
-- Reinhard Zumkeller, May 02 2011

Table[Count[IntegerDigits[n],?(#>0&)],{n,0,120}] (* _Harvey P. Dale, Mar 11 2012 *)
Total[Most[DigitCount[#]]]&/@Range[0,120] (* Harvey P. Dale, Mar 19 2021 *)

a(n)=my(v=digits(n));sum(i=1,#v,!!v[i]) \\ Charles R Greathouse IV, Aug 05 2012

From Hieronymus Fischer, Jun 06 2012: (Start)
a(n) = Sum_{j=1..m+1} (floor(n/10^j+0.9) - floor(n/10^j)), where m = floor(log_10(n)).
a(n) = m + 1 - A055641(n).
G.f.: (1/(1-x))*Sum_{j>=0} (x^10^j - x^(10*10^j))/(1-x^10^(j+1)). (End)
a(n) = A055642(n) - A055641(n).

cp's OEIS Frontend

A007953 Digital sum (i.e., sum of digits) of n; also called digsum(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

PARI

PARI

PARI

Python

Python

Scala

Smalltalk

Swift

Formula

Extensions

A055642 Number of digits in the decimal expansion of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

Python

Python

Formula

A005187 a(n) = a(floor(n/2)) + n; also denominators in expansion of 1/sqrt(1-x) are 2^a(n); also 2n - number of 1's in binary expansion of 2n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

PARI

PARI

PARI

Python

Sage

Formula

A000788 Total number of 1's in binary expansions of 0, ..., n.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Haskell

Maple

Mathematica

PARI