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

 

Logo

Invitation: celebrating 50 years of OEIS, 250000 sequences, and Sloane's 75th, there will be a conference at DIMACS, Rutgers, Oct 9-10 2014.

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)
1965
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, 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, 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 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

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

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.

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

Number of factors in the factorization of the polynomial x^n-1 over the integers. - T. D. Noe, Apr 16 2003

d(n) is odd if and only if n is a perfect square. If d(n) = 2, n is prime. - Donald Sampson (Marsquo(AT)hotmail.com), Dec 10 2003

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

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

Sum_{n>0} d(n)/(n^n) = Sum_{n>0, m>0} 1/(n*m). - Gerald McGarvey, Dec 15 2007

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

Number of subgroups of the cyclic group of order n. - Benoit Jubin, Apr 29 2008

Equals row sums of triangle A143319. - Gary W. Adamson, Aug 07 2008

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

a(n) = A048691(n) - A055205(n). - Reinhard Zumkeller, Dec 08 2009

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

Number of times n appears in an n X n multiplication table. - Dominick Cancilla, Aug 02 2010

a(n) = 2*A038548(n) - A010052(n). - Reinhard Zumkeller, Mar 08 2013

REFERENCES

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.

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

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.

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)

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

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

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

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

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.

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

E. C. Titchmarsh, On a series of Lambert type, J. London Math. Soc., 13 (1938), 248-253.

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

LINKS

N. J. A. Sloane and Daniel Forgues, Table of n, a(n) for n = 1..100000 (first 10000 terms from N. J. A. Sloane)

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy, requires Flash plugin].

G. E. Andrews, Some debts I owe, Seminaire Lotharingien Combinatoire, Paper B42a, Issue 42, 2000; see (7.1).

R. Bellman and H. N. Shapiro, On a problem in additive number theory, Annals Math., 49 (1948), 333-340. [From N. J. A. Sloane, Mar 12 2009]

H. Bottomley, Illustration of initial terms

D. M. Bressoud, M. V. Subbarao, On Uchimura's connection between partitions and the number of divisors, Can. Math. Bull. 27, 143-145 (1984). Zbl 0536.10013.

C. K. Caldwell, The Prime Glossary, Number of divisors

P. Erdős and L. Mirsky, The distribution of values of the divisor function d(n), Proc. London Math. Soc. 2 (1952), pp. 257-271.

C. R. Fletcher, Rings of small order, Math. Gaz. vol. 64, p. 13, 1980.

Robbert Fokkink and Jan van Neerven, Problemen/UWC (in Dutch)

Daniele A. Gewurz and Francesca Merola, Sequences realized as Parker vectors ..., J. Integer Seqs., Vol. 6, 2003.

J. J. Holt & J. W. Jones, Discovering Number Theory, Section 1.4, Counting Divisors

P. A. MacMahon, Divisors of numbers and their continuations in the theory of partitions, Proc. London Math. Soc., 19 (1919), 75-113.

M. Maia and M. Mendez, On the arithmetic product of combinatorial species

R. G. Martinez, Jr., The Factor Zone, Number of Factors for 1 through 600

Math Forum, Divisor Counting

K. Matthews, Factorizing n and calculating phi(n), omega(n), d(n), sigma(n) and mu(n)

Omar E. Pol, , Illustration of initial terms: figure 1, figure 2, figure 3, figure 4, figure 5, (2009), figure 6 (a, b, c), (2013)

S. Ramanujan, On The Number Of Divisors Of A Number

H. B. Reiter, Counting Divisors

W. Sierpinski, Number Of Divisors And Their Sum

Keisuke Uchimura, An identity for the divisor generating function arising from sorting theory, J. Combin. Theory Ser. A 31 (1981), no. 2, 131--135. MR0629588 (82k:05015)

Eric Weisstein's World of Mathematics, Divisor Function

Eric Weisstein's World of Mathematics, Moebius Transform

Eric Weisstein's World of Mathematics, Dirichlet Series Generating Function

Eric Weisstein's World of Mathematics, Binomial Number

Wikipedia, Table of divisors

Wolfram Research, Divisors of first 50 numbers

Index entries for "core" sequences

FORMULA

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

a(n) = 2 iff n is prime.

Multiplicative with a(p^e) = e+1. - David W. Wilson, Aug 01 2001

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

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

a(n) is odd iff n is a square. - Reinhard Zumkeller, Dec 29 2001

a(n) = sum(k=1, n, f(k, n)) where f(k, n) = 1 if k divides n, 0 otherwise. 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

G.f.: Sum_{k>0} ((-1)^(k+1) * x^(k * (k + 1)/2) / ((1 - x^k) * Product(1 - x^i, i=1..k))). - Michael Somos, Apr 27 2003

a(n)=n-sum(k=1, n, ceil(n/k)-floor(n/k)) - Benoit Cloitre, May 11 2003

a(n) = A032741(n)+1 = A062011(n)/2 = A054519(n)-A054519(n-1) = A006218(n)-A006218(n-1) = sum(k=0, n-1, A051950(k)). - Ralf Stephan, Mar 26 2004

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

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

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

Row sums of triangle A051731. - Gary W. Adamson, Nov 02 2007

Logarithmic g.f.: sum(n>=1, a(n)/n * x^n ) = -log( prod(n>=1, (1-x^n)^(1/n) ) ). - Joerg Arndt, May 03 2008

a(n)=sum(k=1, n, floor(n/k)-floor((n-1)/k). - Enrique Pérez Herrero, Aug 27 2009

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

a(n)=1+sum(k=1,n,mod(floor(2^n/(2^k-1)),2)) For every n. - Fabio Civolani (civox(AT)tiscali.it), Mar 12 2010

1. (Sum{d|n}a(d))^2=Sum{d|n}(a(d))^3 (J.Liouville); 2. Sum{d|n}A008836(d)*(a(d))^2=A008836(n)*Sum{d|n}a(d). - Vladimir Shevelev, May 22 2010

a(n) = sigma0(n) = 1 + Sum_{m=2..inf} Sum_{r=1..inf} (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

Sum(a(n) q^n, n=1..inf) = (log(1-q) + psi_q(1)) / log(q), where psi_q(z) is the q-digamma function. - Vladimir Reshetnikov, Apr 23 2013

a(n) = product(A124010(n,k) + 1: k = 1 .. A001221(n)). - Reinhard Zumkeller, Jul 12 2013

a(n) = sum_{k=1..n} A238133(k)*A000041(n-k). - Mircea Merca, Feb 18 2013

G.f.:  sum(k>=1, sum(j>=1, x^(j*k) ) ). - Mats Granvik, Jun 15 2013

The formula above is obtained be expanding the Lambert series sum(k>=1, x^k/(1-x^k) ). - Joerg Arndt, Mar 12 2014

EXAMPLE

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 + ...

MAPLE

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

MATHEMATICA

Table[DivisorSigma[0, n], {n, 100}] (* Enrique Pérez Herrero, Aug 27 2009 *)

CoefficientList[Series[(Log[1 - q] + QPolyGamma[1, q])/(q Log[q]), {q, 0, 100}], q] (* Vladimir Reshetnikov, Apr 23 2013 *)

a[ n_] := SeriesCoefficient[ (QPolyGamma[ 1, q] + Log[1 - q]) / Log[q], {q, 0, n}]; (* Michael Somos, Apr 25 2013 *)

a[ n_] := SeriesCoefficient[ q/(1 - q)^2 QHypergeometricPFQ[ {q, q}, {q^2, q^2}, q, q^2], {q, 0, n}]; (* Michael Somos, Mar 05 2014 *)

PROG

(PARI) {a(n) = if( n==0, 0, numdiv(n))}; /* Michael Somos, Apr 27 2003 */

(PARI) {a(n) = if( n<1, 0, direuler( p=2, n, 1 / (1 - X)^2)[n])}; /* Michael Somos, Apr 27 2003 */

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

(MuPad) numlib::tau (n)$ n=1..90 - Zerinvary Lajos, May 13 2008

(Sage) [sigma(n, 0) for n in xrange(1, 105)] # Zerinvary Lajos, Jun 04 2009

(Haskell)

divisors 1 = [1]

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

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

a = length . divisors

-- James Spahlinger, Oct 07 2012

(Haskell)

a000005 = product . map (+ 1) . a124010_row  -- Reinhard Zumkeller, Jul 12 2013

CROSSREFS

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

Cf. A001227, A005237, A005238, A006601, A006558, A019273, A039665, A049051.

Cf. A001826, A001842, A051731, A066446, A129510, A115361, A129372, A115361, A127093, A143319.

a(n) = A091220(A091202(n)). Cf. A061017.

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

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

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

Cf. A159933, A159934, A027750, A163280, A183063.

Sequence in context: A184395 A179941 A179942 * A122667 A122668 A073668

Adjacent sequences:  A000002 A000003 A000004 * A000006 A000007 A000008

KEYWORD

easy,core,nonn,nice,mult,hear

AUTHOR

N. J. A. Sloane

STATUS

approved

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

Content is available under The OEIS End-User License Agreement .

Last modified August 21 10:03 EDT 2014. Contains 245845 sequences.