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)
2651

%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 Mohammad K. Azarian, Problem 1218, Pi Mu Epsilon Journal, Vol. 13, No. 2, Spring 2010, p. 116. Solution published in Vol. 13, No. 3, Fall 2010, pp. 183-185.

%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 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 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

%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 *)

%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

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

%Y For partial sums see A006218.

%Y Cf. 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).

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

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

%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 May 22 23:08 EDT 2018. Contains 304445 sequences. (Running on oeis4.)