login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000005 d(n) (also called tau(n) or sigma_0(n)), the number of divisors of n.
(Formerly M0246 N0086)
2810

%I M0246 N0086

%S 1,2,2,3,2,4,2,4,3,4,2,6,2,4,4,5,2,6,2,6,4,4,2,8,3,4,4,6,2,8,2,6,4,4,

%T 4,9,2,4,4,8,2,8,2,6,6,4,2,10,3,6,4,6,2,8,4,8,4,4,2,12,2,4,6,7,4,8,2,

%U 6,4,8,2,12,2,4,6,6,4,8,2,10,5,4,2,12,4,4,4,8,2,12,4,6,4,4,4,12,2,6,6,9,2,8,2,8

%N d(n) (also called tau(n) or sigma_0(n)), the number of divisors of n.

%C If the canonical factorization of n into prime powers is Product p^e(p) then d(n) = Product (e(p) + 1). More generally, for k>0, sigma_k(n) = Product_p ((p^((e(p)+1)*k))-1)/(p^k-1) is the sum of the k-th powers of the divisors of n.

%C Number of ways to write n as n = x*y, 1 <= x <= n, 1 <= y <= n. For number of unordered solutions to x*y=n, see A038548.

%C Note that d(n) is not the number of Pythagorean triangles with radius of the inscribed circle equal to n (that is A078644). For number of primitive Pythagorean triangles having inradius n, see A068068(n).

%C Number of factors in the factorization of the polynomial x^n-1 over the integers. - _T. D. Noe_, Apr 16 2003

%C Also equal to the number of partitions p of n such that all the parts have the same cardinality, i.e. max(p)=min(p). - _Giovanni Resta_, Feb 06 2006

%C Equals A127093 as an infinite lower triangular matrix * the harmonic series, [1/1, 1/2, 1/3, ...]. - _Gary W. Adamson_, May 10 2007

%C Sum_{n>0} d(n)/(n^n) = Sum_{n>0, m>0} 1/(n*m). - _Gerald McGarvey_, Dec 15 2007

%C For odd n, this is the number of partitions of n into consecutive integers. Proof: For n = 1, clearly true. For n = 2k + 1, k >= 1, map each (necessarily odd) divisor to such a partition as follows: For 1 and n, map k + (k+1) and n, respectively. For any remaining divisor d <= sqrt(n), map (n/d - (d-1)/2) + ... + (n/d - 1) + (n/d) + (n/d + 1) + ... + (n/d + (d-1)/2) {i.e., n/d plus (d-1)/2 pairs each summing to 2n/d}. For any remaining divisor d > sqrt(n), map ((d-1)/2 - (n/d - 1)) + ... + ((d-1)/2 - 1) + (d-1)/2 + (d+1)/2 + ((d+1)/2 + 1) + ... + ((d+1)/2 + (n/d - 1)) {i.e., n/d pairs each summing to d}. As all such partitions must be of one of the above forms, the 1-to-1 correspondence and proof is complete. - _Rick L. Shepherd_, Apr 20 2008

%C Number of subgroups of the cyclic group of order n. - _Benoit Jubin_, Apr 29 2008

%C Equals row sums of triangle A143319. - _Gary W. Adamson_, Aug 07 2008

%C Equals row sums of triangle A159934, equivalent to generating a(n) by convolving A000005 prefaced with a 1; (1, 1, 2, 2, 3, 2, ...) with the INVERTi transform of A000005, (A159933): (1, 1,-1, 0, -1, 2, ...). Example: a(6) = 4 = (1, 1, 2, 2, 3, 2) dot (2, -1, 0, -1, 1, 1) = (2, -1, 0, -2, 3, 2) = 4. - _Gary W. Adamson_, Apr 26 2009

%C Number of times n appears in an n X n multiplication table. - _Dominick Cancilla_, Aug 02 2010

%C Number of k >= 0 such that (k^2 + k*n + k)/(k + 1) is an integer. - _Juri-Stepan Gerasimov_, Oct 25 2015.

%C The only numbers n such that tau(n) >= n/2 are 1,2,3,4,6,8,12. - _Michael De Vlieger_, Dec 14 2016

%C a(n) is also the number of partitions of 2*n into equal parts, minus the number of partitions of 2*n into consecutive parts. - _Omar E. Pol_, May 03 2017

%D M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 840.

%D T. M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976, page 38.

%D G. Chrystal, Algebra: An elementary text-book for the higher classes of secondary schools and for colleges, 6th ed, Chelsea Publishing Co., New York 1959 Part II, p. 345, Exercise XXI(16). MR0121327 (22 #12066)

%D K. Knopp, Theory and Application of Infinite Series, Blackie, London, 1951, p. 451.

%D D. S. Mitrinovic et al., Handbook of Number Theory, Kluwer, Chap. II. (For inequalities, etc.)

%D S. Ramanujan, Collected Papers, Ed. G. H. Hardy et al., Cambridge 1927; Chelsea, NY, 1962. Has many references to this sequence. - _N. J. A. Sloane_, Jun 02 2014

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

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

%D B. Spearman and K. S. Williams, Handbook of Estimates in the Theory of Numbers, Carleton Math. Lecture Note Series No. 14, 1975; see p. 2.1.

%D E. C. Titchmarsh, The Theory of Functions, Oxford, 1938, p. 160.

%D T. Tao, Poincaré's Legacies, Part I, Amer. Math. Soc., 2009, see pp. 31ff for upper bounds on d(n).

%H Daniel Forgues, <a href="/A000005/b000005.txt">Table of n, a(n) for n = 1..100000</a> (first 10000 terms from N. J. A. Sloane)

%H M. Abramowitz and I. A. Stegun, eds., <a href="http://www.convertit.com/Go/ConvertIt/Reference/AMS55.ASP">Handbook of Mathematical Functions</a>, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy, requires Flash plugin].

%H G. E. Andrews, <a href="http://www.mat.univie.ac.at/~slc/s/s42andrews.html">Some debts I owe</a>, Seminaire Lotharingien Combinatoire, Paper B42a, Issue 42, 2000; see (7.1).

%H R. Bellman and H. N. Shapiro, <a href="http://www.jstor.org/stable/1969281">On a problem in additive number theory</a>, Annals Math., 49 (1948), 333-340. [From _N. J. A. Sloane_, Mar 12 2009]

%H H. Bottomley, <a href="/A000005/a000005.gif">Illustration of initial terms</a>

%H D. M. Bressoud, M. V. Subbarao, <a href="http://dx.doi.org/10.4153/CMB-1984-022-5">On Uchimura's connection between partitions and the number of divisors</a>, Can. Math. Bull. 27, 143-145 (1984). Zbl 0536.10013.

%H C. K. Caldwell, The Prime Glossary, <a href="http://primes.utm.edu/glossary/page.php?sort=Tau">Number of divisors</a>

%H Imanuel Chen and Michael Z. Spivey, <a href="http://soundideas.pugetsound.edu/summer_research/238">Integral Generalized Binomial Coefficients of Multiplicative Functions</a>, Preprint 2015; Summer Research Paper 238, Univ. Puget Sound.

%H Jimmy Devillet, Gergely Kiss, <a href="https://arxiv.org/abs/1806.02073">Characterizations of biselective operations</a>, arXiv:1806.02073 [math.RA], 2018.

%H P. Erdős and L. Mirsky, <a href="http://www.renyi.hu/~p_erdos/1952-12.pdf">The distribution of values of the divisor function d(n)</a>, Proc. London Math. Soc. 2 (1952), pp. 257-271.

%H C. R. Fletcher, <a href="http://www.jstor.org/stable/3615885">Rings of small order</a>, Math. Gaz. vol. 64, p. 13, 1980.

%H Robbert Fokkink and Jan van Neerven, <a href="http://www.math.leidenuniv.nl/~naw/serie5/deel04/mrt2003/pdf/problemen-uwc.pdf">Problemen/UWC</a> (in Dutch)

%H Daniele A. Gewurz and Francesca Merola, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL6/Gewurz/gewurz5.html">Sequences realized as Parker vectors ...</a>, J. Integer Seqs., Vol. 6, 2003.

%H J. J. Holt & J. W. Jones, Discovering Number Theory, Section 1.4, <a href="http://www.math.mtu.edu/mathlab/COURSES/holt/dnt/divis4.html">Counting Divisors</a>.

%H P. A. MacMahon, <a href="http://plms.oxfordjournals.org/content/s2-19/1/75.extract">Divisors of numbers and their continuations in the theory of partitions</a>, Proc. London Math. Soc., 19 (1919), 75-113.

%H M. Maia and M. Mendez, <a href="http://arXiv.org/abs/math.CO/0503436">On the arithmetic product of combinatorial species</a>, arXiv:math/0503436 [math.CO], 2005.

%H R. G. Martinez, Jr., The Factor Zone, <a href="http://factorzone.tripod.com/factors.htm">Number of Factors for 1 through 600</a>.

%H Math Forum, <a href="http://mathforum.org/library/drmath/view/55741.html">Divisor Counting</a>.

%H K. Matthews, <a href="http://www.numbertheory.org/php/factor.html">Factorizing n and calculating phi(n), omega(n), d(n), sigma(n) and mu(n)</a>.

%H M. Merca, <a href="http://dx.doi.org/10.1016/j.jnt.2014.10.009">A new look on the generating function for the number of divisors</a>, Journal of Number Theory, Volume 149, April 2015, Pages 57-69.

%H Mircea Merca, <a href="http://dx.doi.org/10.1016/j.jnt.2015.08.014">Combinatorial interpretations of a recent convolution for the number of divisors of a positive integer</a>, Journal of Number Theory, Volume 160, March 2016, Pages 60-75, corollary 2.1.

%H Matthew Parker, <a href="https://oeis.org/A000005/a000005_25M.7z">The first 25 million terms (7-Zip compressed file)</a>.

%H Ed Pegg, Jr., <a href="http://www.mathpuzzle.com/MAA/07-Sequence%20Pictures/mathgames_12_08_03.html">Sequence Pictures</a>, Math Games column, Dec 08 2003.

%H Ed Pegg, Jr., <a href="/A000043/a000043_2.pdf">Sequence Pictures</a>, Math Games column, Dec 08 2003. [Cached copy, with permission (pdf only)]

%H Omar E. Pol, <a href="http://www.polprimos.com/imagenespub/poldiv01.jpg">Illustration of initial terms: figure 1</a>, <a href="http://www.polprimos.com/imagenespub/poldiv02.jpg">figure 2</a>, <a href="http://www.polprimos.com/imagenespub/poldiv03.jpg">figure 3</a>, <a href="http://www.polprimos.com/imagenespub/poldiv04.jpg">figure 4</a>, <a href="http://www.polprimos.com/imagenespub/poldiv3v.jpg">figure 5</a>, (2009), <a href="http://www.polprimos.com/imagenespub/poldiv13.jpg">figure 6 (a, b, c)</a>, (2013)

%H S. Ramanujan, <a href="http://www.imsc.res.in/~rao/ramanujan/CamUnivCpapers/Cpaper8/page1.htm">On The Number Of Divisors Of A Number</a>.

%H H. B. Reiter, <a href="http://www.math.uncc.edu/~hbreiter/DivisorsLasVegas.pdf">Counting Divisors</a>.

%H W. Sierpiński, <a href="http://matwbn.icm.edu.pl/ksiazki/mon/mon42/mon4204.pdf">Number Of Divisors And Their Sum</a>.

%H E. C. Titchmarsh, <a href="http://jlms.oxfordjournals.org/content/s1-13/4/248.extract">On a series of Lambert type</a>, J. London Math. Soc., 13 (1938), 248-253.

%H Keisuke Uchimura, <a href="http://dx.doi.org/10.1016/0097-3165(81)90009-1">An identity for the divisor generating function arising from sorting theory</a>, J. Combin. Theory Ser. A 31 (1981), no. 2, 131--135. MR0629588 (82k:05015)

%H Wang Zheng Bing, Robert Fokkink and Wan Fokkink, <a href="http://www.jstor.org/stable/2974956">A Relation Between Partitions and the Number of Divisors</a>, Am. Math. Monthly, 102 (Apr., 1995), no. 4, 345-347.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/BinomialNumber.html">Binomial Number</a>, <a href="http://mathworld.wolfram.com/DirichletSeriesGeneratingFunction.html">Dirichlet Series Generating Function</a>, <a href="http://mathworld.wolfram.com/DivisorFunction.html">Divisor Function</a>, and <a href="http://mathworld.wolfram.com/MoebiusTransform.html">Moebius Transform</a>.

%H Wikipedia, <a href="http://www.wikipedia.org/wiki/Table_of_divisors">Table of divisors</a>.

%H Wolfram Research, <a href="http://functions.wolfram.com/NumberTheoryFunctions/Divisors/03/02">Divisors of first 50 numbers</a>

%H <a href="/index/Cor#core">Index entries for "core" sequences</a>

%H <a href="/index/Eu#epf">Index entries for sequences computed from exponents in factorization of n</a>

%F If n is written as 2^z*3^y*5^x*7^w*11^v*... then a(n)=(z+1)*(y+1)*(x+1)*(w+1)*(v+1)*...

%F a(n) = 2 iff n is prime.

%F a(n) = A083888(n) + A083889(n) + A083890(n) + A083891(n) + A083892(n) + A083893(n) + A083894(n) + A083895(n) + A083896(n).

%F a(n) = A083910(n) + A083911(n) + A083912(n) + A083913(n) + A083914(n) + A083915(n) + A083916(n) + A083917(n) + A083918(n) + A083919(n).

%F Multiplicative with a(p^e) = e+1. - _David W. Wilson_, Aug 01 2001

%F G.f.: Sum_{n >= 1} a(n) x^n = Sum_{k>0} x^k/(1-x^k). This is usually called THE Lambert series (see Knopp, Titchmarsh).

%F a(n) <= 2 sqrt(n) [see Mitrinovich, p. 39, also A046522].

%F a(n) is odd iff n is a square. - _Reinhard Zumkeller_, Dec 29 2001

%F a(n) = Sum_{k=1..n} f(k, n) where f(k, n) = 1 if k divides n, 0 otherwise (Mobius transform of A000012). Equivalently, f(k, n) = (1/k)*Sum_{l=1..k} z(k, l)^n with z(k, l) the k-th roots of unity. - _Ralf Stephan_, Dec 25 2002

%F G.f.: Sum_{k>0} ((-1)^(k+1) * x^(k * (k + 1)/2) / ((1 - x^k) * Product_{i=1..k} (1 - x^i))). - _Michael Somos_, Apr 27 2003

%F a(n) = n - Sum_{k=1..n} (ceiling(n/k) - floor(n/k)). - _Benoit Cloitre_, May 11 2003

%F a(n) = A032741(n) + 1 = A062011(n)/2 = A054519(n) - A054519(n-1) = A006218(n) - A006218(n-1) = 1 + Sum_{k=1..n-1} A051950(k+1). - _Ralf Stephan_, Mar 26 2004

%F G.f.: Sum_{k>0} x^(k^2)*(1+x^k)/(1-x^k). Dirichlet g.f.: zeta(s)^2. - _Michael Somos_, Apr 05 2003

%F Sequence = M*V where M = A129372 as an infinite lower triangular matrix and V = ruler sequence A001511 as a vector: [1, 2, 1, 3, 1, 2, 1, 4, ...]. - _Gary W. Adamson_, Apr 15 2007

%F A000005 = M*V, where M = A115361 is an infinite lower triangular matrix and V = A001227, the number of odd divors of n, is a vector: [1, 1, 2, 1, 2, 2, 2, ...]. - _Gary W. Adamson_, Apr 15 2007

%F Row sums of triangle A051731. - _Gary W. Adamson_, Nov 02 2007

%F Logarithmic g.f.: Sum_{n>=1} a(n)/n * x^n = -log( Product_{n>=1} (1-x^n)^(1/n) ). - _Joerg Arndt_, May 03 2008

%F a(n) = Sum_{k=1..n} (floor(n/k) - floor((n-1)/k)). - _Enrique Pérez Herrero_, Aug 27 2009

%F a(s) = 2^omega(s), if s>1 is a squarefree number (A005117) and omega(s) is: A001221. - _Enrique Pérez Herrero_, Sep 08 2009

%F a(n) = A048691(n) - A055205(n). - _Reinhard Zumkeller_, Dec 08 2009

%F For n>0, a(n) = 1 + Sum(s=2..n, cos(Pi*n/s)^2 ). Also tau(n) = 2 + Sum[integerpart[(cos(Pi*n/k))^2], {k, 2, n-1}]. And [(cos(Pi*n/k))^2] = [1/4 * e^(-(2*i*Pi*n)/k) + 1/4 * e^((2*i*Pi*n)/k) + 1/2]. - _Eric Desbiaux_, Mar 09 2010, corrected Apr 16 2011

%F a(n) = 1 + Sum_{k=1..n} (floor(2^n/(2^k-1)) mod 2) for every n. - Fabio Civolani (civox(AT)tiscali.it), Mar 12 2010

%F From _Vladimir Shevelev_, May 22 2010: (Start)

%F (Sum_{d|n} a(d))^2 = Sum_{d|n} a(d)^3 (J. Liouville).

%F Sum_{d|n} A008836(d)*a(d)^2 = A008836(n)*Sum_{d|n} a(d). (End)

%F a(n) = sigma_0(n) = 1 + Sum_{m>=2} Sum_{r>=1} (1/m^(r+1))*Sum_{j=1..m-1} Sum_{k=0..m^(r+1)-1} e^(2*k*Pi*i*(n+(m-j)*m^r)/m^(r+1)). - _A. Neves_, Oct 04 2010

%F a(n) = 2*A038548(n) - A010052(n). - _Reinhard Zumkeller_, Mar 08 2013

%F Sum_{n>=1} a(n)*q^n = (log(1-q) + psi_q(1)) / log(q), where psi_q(z) is the q-digamma function. - _Vladimir Reshetnikov_, Apr 23 2013

%F a(n) = Product_{k = 1 .. A001221(n)} (A124010(n,k) + 1). - _Reinhard Zumkeller_, Jul 12 2013

%F a(n) = Sum_{k=1..n} A238133(k)*A000041(n-k). - _Mircea Merca_, Feb 18 2013

%F G.f.: Sum_{k>=1} Sum_{j>=1} x^(j*k). - _Mats Granvik_, Jun 15 2013

%F The formula above is obtained by expanding the Lambert series Sum_{k>=1} x^k/(1-x^k). - _Joerg Arndt_, Mar 12 2014

%F G.f.: Sum_{n>=1} Sum_{d|n} ( -log(1 - x^(n/d)) )^d / d!. - _Paul D. Hanna_, Aug 21 2014

%F 2*Pi*a(n) = Sum_{m=1..n} integral_{x=0..2*Pi} r^(m-n)( cos((m-n)*x)-r^m cos(n*x) )/( 1+r^(2*m)-2r^m cos(m*x) )dx, 0<r<1 a free parameter. This formula is obtained as the sum of the residues of the Lambert series Sum_{k>=1} x^k/(1-x^k). - _Seiichi Kirikami_, Oct 22 2015

%F a(n) = A091220(A091202(n)) = A106737(A156552(n)). - _Antti Karttunen_, circa 2004 & Mar 06 2017

%F a(n) = A034296(n) - A237665(n+1) [Wang, Fokkink, Fokkink]. - _George Beck_, May 06 2017

%F G.f.: 2*x/(1-x) - Sum_{k>0} x^k*(1-2*x^k)/(1-x^k). - _Mamuka Jibladze_, Aug 29 2018

%F a(n) = Sum_{k=1..n} 1/phi(n / gcd(n, k)). - _Daniel Suteu_, Nov 05 2018

%e G.f. = x + 2*x^2 + 2*x^3 + 3*x^4 + 2*x^5 + 4*x^6 + 2*x^7 + 4*x^8 + 3*x^9 + ...

%p with(numtheory): A000005 := tau; [ seq(tau(n), n=1..100) ];

%t Table[DivisorSigma[0, n], {n, 100}] (* _Enrique Pérez Herrero_, Aug 27 2009 *)

%t CoefficientList[Series[(Log[1 - q] + QPolyGamma[1, q])/(q Log[q]), {q, 0, 100}], q] (* _Vladimir Reshetnikov_, Apr 23 2013 *)

%t a[ n_] := SeriesCoefficient[ (QPolyGamma[ 1, q] + Log[1 - q]) / Log[q], {q, 0, Abs@n}]; (* _Michael Somos_, Apr 25 2013 *)

%t a[ n_] := SeriesCoefficient[ q/(1 - q)^2 QHypergeometricPFQ[ {q, q}, {q^2, q^2}, q, q^2], {q, 0, Abs@n}]; (* _Michael Somos_, Mar 05 2014 *)

%t a[n_] := SeriesCoefficient[q/(1 - q) QHypergeometricPFQ[{q, q}, {q^2}, q, q], {q, 0, Abs@n}] (* _Mats Granvik_, Apr 15 2015 *)

%t With[{M=500},CoefficientList[Series[(2x)/(1-x)-Sum[x^k (1-2x^k)/(1-x^k),{k,M}],{x,0,M}],x]] (* _Mamuka Jibladze_, Aug 31 2018 *)

%o (PARI) {a(n) = if( n==0, 0, numdiv(n))}; /* _Michael Somos_, Apr 27 2003 */

%o (PARI) {a(n) = n=abs(n); if( n<1, 0, direuler( p=2, n, 1 / (1 - X)^2)[n])}; /* _Michael Somos_, Apr 27 2003 */

%o (PARI) {a(n)=polcoeff(sum(m=1, n+1, sumdiv(m, d, (-log(1-x^(m/d) +x*O(x^n) ))^d/d!)), n)} \\ _Paul D. Hanna_, Aug 21 2014

%o (MAGMA) [ NumberOfDivisors(n) : n in [1..100] ]; // Sergei Haller (sergei(AT)sergei-haller.de), Dec 21 2006

%o (MuPAD) numlib::tau (n)$ n=1..90 // _Zerinvary Lajos_, May 13 2008

%o (Sage) [sigma(n,0) for n in xrange(1,105)] # _Zerinvary Lajos_, Jun 04 2009

%o (Haskell)

%o divisors 1 = [1]

%o divisors n = (1:filter ((==0) . rem n)

%o [2..n `div` 2]) ++ [n]

%o a = length . divisors

%o -- _James Spahlinger_, Oct 07 2012

%o (Haskell)

%o a000005 = product . map (+ 1) . a124010_row -- _Reinhard Zumkeller_, Jul 12 2013

%o (Python)

%o from sympy import divisor_count

%o for n in range(1,20): print(divisor_count(n), end=', ') # _Stefano Spezia_, Nov 05 2018

%Y See A002183, A002182 for records. See A000203 for the sum-of-divisors function sigma(n).

%Y For partial sums see A006218.

%Y Cf. A007427 (Dirichlet Inverse), A001227, A005237, A005238, A006601, A006558, A019273, A039665, A049051, A001826, A001842, A049820, A051731, A066446, A106737, A129510, A115361, A129372, A127093, A143319, A061017, A091202, A091220, A156552, A159933, A159934, A027750, A163280, A183063, A263730, A034296, A237665.

%Y Factorizations into given number of factors: writing n = x*y (A038548, unordered, A000005, ordered), n = x*y*z (A034836, unordered, A007425, ordered), n = w*x*y*z (A007426, ordered).

%K easy,core,nonn,nice,mult,hear,changed

%O 1,2

%A _N. J. A. Sloane_

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 13 19:25 EST 2018. Contains 317149 sequences. (Running on oeis4.)