A115361 -id:A115361 - cp's OEIS frontend

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

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

Offset: 1

N. J. A. Sloane

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.
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
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
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
Number of times n appears in an n X n multiplication table. - Dominick Cancilla, Aug 02 2010
Number of k >= 0 such that (k^2 + k*n + k)/(k + 1) is an integer. - Juri-Stepan Gerasimov, Oct 25 2015
The only numbers k such that tau(k) >= k/2 are 1,2,3,4,6,8,12. - Michael De Vlieger, Dec 14 2016
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
From Tomohiro Yamada, Oct 27 2020: (Start)
Let k(n) = log d(n)*log log n/(log 2 * log n), then lim sup k(n) = 1 (Hardy and Wright, Chapter 18, Theorem 317) and k(n) <= k(6983776800) = 1.537939... (the constant A280235) for every n (Nicolas and Robin, 1983).
There exist infinitely many n such that d(n) = d(n+1) (Heath-Brown, 1984). The number of such integers n <= x is at least c*x/(log log x)^3 (Hildebrand, 1987) but at most O(x/sqrt(log log x)) (Erdős, Carl Pomerance and Sárközy, 1987). (End)
Number of 2D grids of n congruent rectangles with two different side lengths, in a rectangle, modulo rotation (cf. A038548 for squares instead of rectangles). Also number of ways to arrange n identical objects in a rectangle (NOT modulo rotation, cf. A038548 for modulo rotation); cf. A007425 and A140773 for the 3D case. - Manfred Boergens, Jun 08 2021
The constant quoted above from Nicolas and Robin, 6983776800 = 2^5 * 3^3 * 5^2 * 7 * 11 * 13 * 17 * 19, appears arbitrary, but interestingly equals 2 * A095849(36). That second factor is highly composite and deeply composite. - Hal M. Switkay, Aug 08 2025

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

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.
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)
G. H. Hardy, Ramanujan: twelve lectures on subjects suggested by his life and work, Cambridge, University Press, 1940, p. 55.
G. H. Hardy and E. M. Wright, revised by D. R. Heath-Brown and J. H. Silverman, An Introduction to the Theory of Numbers, 6th ed., Oxford Univ. Press, 2008.
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.
James J. Tattersall, Elementary Number Theory in Nine Chapters, Cambridge University Press, 1999, page 285.
E. C. Titchmarsh, The Theory of Functions, Oxford, 1938, p. 160.
Terence Tao, Poincaré's Legacies, Part I, Amer. Math. Soc., 2009, see pp. 31ff for upper bounds on d(n).

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, Séminaire Lotharingien de Combinatoire, Paper B42a, Issue 42, 2000; see (7.1).
J. Bell, Lambert series in analytic number theory
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]
Henry Bottomley, Illustration of initial terms
D. M. Bressoud and 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
Imanuel Chen and Michael Z. Spivey, Integral Generalized Binomial Coefficients of Multiplicative Functions, Preprint 2015; Summer Research Paper 238, Univ. Puget Sound.
Jimmy Devillet and Gergely Kiss, Characterizations of biselective operations, arXiv:1806.02073 [math.RA], 2018.
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.
Paul Erdős, Carl Pomerance and András Sárközy, On locally repeated values of certain arithmetic functions, III, Proc. Amer. Math. Soc. 101 (1987), 1-7.
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.
D. R. Heath-Brown, The divisor function at consecutive integers, Mathematika 31 (1984), 141-149.
Adolf Hildebrand, The divisor function at consecutive integers, Pacific J. Math. 129 (1987), 307-319.
J. J. Holt and J. W. Jones, Counting Divisors, Discovering Number Theory, Section 1.4.
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, arXiv:math/0503436 [math.CO], 2005.
R. G. Martinez, Jr., The Factor Zone, Number of Factors for 1 through 600.
Math Forum, Divisor Counting.
Mathematics Stack Exchange, A question on discrete Fourier Transform of some function
K. Matthews, Factorizing n and calculating phi(n), omega(n), d(n), sigma(n) and mu(n).
Mircea Merca, A new look on the generating function for the number of divisors, Journal of Number Theory, Volume 149, April 2015, Pages 57-69.
Mircea Merca, Combinatorial interpretations of a recent convolution for the number of divisors of a positive integer, Journal of Number Theory, Volume 160, March 2016, Pages 60-75, corollary 2.1.
J. L. Nicolas and G. Robin, Majorations Explicites Pour le Nombre de Diviseurs de N, Canadian Mathematical Bulletin, Volume 26, Issue 4, 01 December 1983, pp. 485-492.
Matthew Parker, The first 25 million terms (7-Zip compressed file).
Ed Pegg, Jr., Sequence Pictures, Math Games column, Dec 08 2003.
Ed Pegg, Jr., Sequence Pictures, Math Games column, Dec 08 2003. [Cached copy, with permission (pdf only)]
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. Sierpiński, Number Of Divisors And Their Sum.
Terence Tao, Poincaré's Legacies: pages from year two of a mathematical blog, see page 59.
E. C. Titchmarsh, On a series of Lambert type, J. London Math. Soc., 13 (1938), 248-253.
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)
Wang Zheng Bing, Robert Fokkink and Wan Fokkink, A Relation Between Partitions and the Number of Divisors, Am. Math. Monthly, 102 (Apr., 1995), no. 4, 345-347.
Eric Weisstein's World of Mathematics, Binomial Number, Dirichlet Series Generating Function, Divisor Function, and Moebius Transform.
Wikipedia, Table of divisors.
Wolfram Research, Divisors of first 50 numbers
Index entries for "core" sequences
Index entries for sequences computed from exponents in factorization of n

See A002183, A002182 for records. See A000203 for the sum-of-divisors function sigma(n).
For partial sums see A006218.
Cf. A007427 (Dirichlet Inverse), A001227, A001826, A001842, A005237, A005238, A006558, A006601, A019273, A027750, A034296, A039665, A049051, A049820, A051731, A061017, A066446, A091202, A091220, A106737, A115361, A127093, A129372, A129510, A143319, A156552, A159933, A159934, A163280, A183063, A237665, A263730.
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).
Cf. A000010, A095849.
Cf. A098198 (Dgf at s=2), A183030 (Dgf at s=3), A183031 (Dgf at s=3).

List([1..150],n->Tau(n)); # Muniru A Asiru, Mar 05 2019

divisors 1 = [1]
divisors n = (1:filter ((==0) . rem n)
               [2..n `div` 2]) ++ [n]
a = length . divisors
-- James Spahlinger, Oct 07 2012

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

function tau(n)
    i = 2; num = 1
    while i * i <= n
        if rem(n, i) == 0
            e = 0
            while rem(n, i) == 0
                e += 1
                n = div(n, i)
            end
            num *= e + 1
        end
        i += 1
    end
    return n > 1 ? num + num : num
end
println([tau(n) for n in 1:104])  # Peter Luschny, Sep 03 2023

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

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

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, Abs@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, Abs@n}]; (* Michael Somos, Mar 05 2014 *)
a[n_] := SeriesCoefficient[q/(1 - q) QHypergeometricPFQ[{q, q}, {q^2}, q, q], {q, 0, Abs@n}] (* Mats Granvik, Apr 15 2015 *)
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 *)

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

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

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

{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

from sympy import divisor_count
for n in range(1, 20): print(divisor_count(n), end=', ') # Stefano Spezia, Nov 05 2018

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

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.
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) = 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).
Multiplicative with a(p^e) = e+1. - David W. Wilson, Aug 01 2001
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 (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
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
a(n) = n - Sum_{k=1..n} (ceiling(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) = 1 + Sum_{k=1..n-1} A051950(k+1). - 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
Sequence = M*V, where M = A115361 is an infinite lower triangular matrix and V = A001227, the number of odd divisors 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
Sum_{n>0} a(n)/(n^n) = Sum_{n>0, m>0} 1/(n*m). - Gerald McGarvey, Dec 15 2007
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
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) = A048691(n) - A055205(n). - Reinhard Zumkeller, Dec 08 2009
For n > 1, a(n) = 2 + Sum_{k=2..n-1} floor((cos(Pi*n/k))^2). And floor((cos(Pi*n/k))^2) = floor(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
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
From Vladimir Shevelev, May 22 2010: (Start)
(Sum_{d|n} a(d))^2 = Sum_{d|n} a(d)^3 (J. Liouville).
Sum_{d|n} A008836(d)*a(d)^2 = A008836(n)*Sum_{d|n} a(d). (End)
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
a(n) = 2*A038548(n) - A010052(n). - Reinhard Zumkeller, Mar 08 2013
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
a(n) = Product_{k = 1..A001221(n)} (A124010(n,k) + 1). - 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 by expanding the Lambert series Sum_{k>=1} x^k/(1-x^k). - Joerg Arndt, Mar 12 2014
G.f.: Sum_{n>=1} Sum_{d|n} ( -log(1 - x^(n/d)) )^d / d!. - Paul D. Hanna, Aug 21 2014
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
a(n) = A091220(A091202(n)) = A106737(A156552(n)). - Antti Karttunen, circa 2004 & Mar 06 2017
a(n) = A034296(n) - A237665(n+1) [Wang, Fokkink, Fokkink]. - George Beck, May 06 2017
G.f.: 2*x/(1-x) - Sum_{k>0} x^k*(1-2*x^k)/(1-x^k). - Mamuka Jibladze, Aug 29 2018
a(n) = Sum_{k=1..n} 1/phi(n / gcd(n, k)). - Daniel Suteu, Nov 05 2018
a(k*n) = a(n)*(f(k,n)+2)/(f(k,n)+1), where f(k,n) is the exponent of the highest power of k dividing n and k is prime. - Gary Detlefs, Feb 08 2019
a(n) = 2*log(p(n))/log(n), n > 1, where p(n)= the product of the factors of n = A007955(n). - Gary Detlefs, Feb 15 2019
a(n) = (1/n) * Sum_{k=1..n} sigma(gcd(n,k)), where sigma(n) = sum of divisors of n. - Orges Leka, May 09 2019
a(n) = A001227(n)*(A007814(n) + 1) = A001227(n)*A001511(n). - Ivan N. Ianakiev, Nov 14 2019
From Richard L. Ollerton, May 11 2021: (Start)
a(n) = A038040(n) / n = (1/n)*Sum_{d|n} phi(d)*sigma(n/d), where phi = A000010 and sigma = A000203.
a(n) = (1/n)*Sum_{k=1..n} phi(gcd(n,k))*sigma(n/gcd(n,k))/phi(n/gcd(n,k)). (End)
From Ridouane Oudra, Nov 12 2021: (Start)
a(n) = Sum_{j=1..n} Sum_{k=1..j} (1/j)*cos(2*k*n*Pi/j);
a(n) = Sum_{j=1..n} Sum_{k=1..j} (1/j)*e^(2*k*n*Pi*i/j), where i^2=-1. (End)

Incorrect formula deleted by Ridouane Oudra, Oct 28 2021

A051731 Triangle read by rows: T(n, k) = 1 if k divides n, T(n, k) = 0 otherwise, for 1 <= k <= n.

Original entry on oeis.org

1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1

Offset: 1

Klaus Strassburger (strass(AT)ddfi.uni-duesseldorf.de)

T(n, k) is the number of partitions of n into k equal parts. - Omar E. Pol, Apr 21 2018

This triangle is the lower triangular array L in the LU decomposition of the square array A003989. - Peter Bala, Oct 15 2023

			The triangle T(n, k) begins:
  n\k 1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 ...
  1:  1
  2:  1  1
  3:  1  0  1
  4:  1  1  0  1
  5:  1  0  0  0  1
  6:  1  1  1  0  0  1
  7:  1  0  0  0  0  0  1
  8:  1  1  0  1  0  0  0  1
  9:  1  0  1  0  0  0  0  0  1
  10: 1  1  0  0  1  0  0  0  0  1
  11: 1  0  0  0  0  0  0  0  0  0  1
  12: 1  1  1  1  0  1  0  0  0  0  0  1
  13: 1  0  0  0  0  0  0  0  0  0  0  0  1
  14: 1  1  0  0  0  0  1  0  0  0  0  0  0  1
  15: 1  0  1  0  1  0  0  0  0  0  0  0  0  0  1
  ... Reformatted and extended. - _Wolfdieter Lang_, Nov 12 2014

Charles R Greathouse IV, Rows n = 1..100, flattened
Marc Chamberland, Factored matrices can generate combinatorial identities, Linear Algebra and its Applications, Volume 438, Issue 4, 2013, pp. 1667-1677.
Mats Granvik, Illustration.
Warren P. Johnson, An LDU Factorization in Elementary Number Theory, Mathematics Magazine, Vol. 76, No. 5 (Dec., 2003), pp. 392-394.
Jeffrey Ventrella, Divisor Plot.

Cf. A000007, A000203, A002260, A003989, A048158, A049820, A054525.
Cf. A074854, A101508, A115361, A129372, A172119, A175105.
Cf. A000005 (row sums), A032741(n+2) (diagonal sums).
Cf. A243987 (partial sums per row).
Cf. A134546 (A004736 * T, matrix multiplication).
Variants: A113704, A077049, A077051.

a051731 n k = 0 ^ mod n k
a051731_row n = a051731_tabl !! (n-1)
a051731_tabl = map (map a000007) a048158_tabl
-- Reinhard Zumkeller, Aug 13 2013

[0^(n mod k): k in [1..n], n in [1..17]]; // G. C. Greubel, Jun 22 2024

A051731 := proc(n, k) if n mod k = 0 then 1 else 0 end if end proc:
# R. J. Mathar, Jul 14 2012

Flatten[Table[If[Mod[n, k] == 0, 1, 0], {n, 20}, {k, n}]]

for(n=1,17,for(k=1,n,print1(!(n%k)", "))) \\ Charles R Greathouse IV, Mar 14 2012

from math import isqrt, comb
def A051731(n): return int(not (a:=(m:=isqrt(k:=n<<1))+(k>m*(m+1)))%(n-comb(a,2))) # Chai Wah Wu, Nov 13 2024

A051731_row = lambda n: [int(k.divides(n)) for k in (1..n)]
for n in (1..17): print(A051731_row(n)) # Peter Luschny, Jan 05 2018

{T(n, k)*k, k=1..n} setminus {0} = divisors(n).
Sum_{k=1..n} T(n, k)*k^i = sigma[i](n), where sigma[i](n) is the sum of the i-th power of the positive divisors of n.
Sum_{k=1..n} T(n, k) = A000005(n).
Sum_{k=1..n} T(n, k)*k = A000203(n).
T(n, k) = T(n-k, k) for k <= n/2, T(n, k) = 0 for n/2 < k <= n-1, T(n, n) = 1.
Rows given by A074854 converted to binary. Example: A074854(4) = 13 = 1101_2; row 4 = 1, 1, 0, 1. - Philippe Deléham, Oct 04 2003
From Paul Barry, Dec 05 2004: (Start)
Binomial transform (product by binomial matrix) is A101508.
Columns have g.f.: x^k/(1-x^(k+1)) (k >= 0). (End)
Matrix inverse of triangle A054525, where A054525(n, k) = MoebiusMu(n/k) if k|n, 0 otherwise. - Paul D. Hanna, Jan 09 2006
From Gary W. Adamson, Apr 15 2007, May 10 2007: (Start)
Equals A129372 * A115361 as infinite lower triangular matrices.
A054525 is the inverse of this triangle (as lower triangular matrix).
This triangle * [1, 2, 3, ...] = sigma(n) (A000203).
This triangle * [1/1, 1/2, 1/3, ...] = sigma(n)/n. (End)
From  Reinhard Zumkeller, Nov 01 2009: (Start)
T(n, k) = 0^(n mod k).
T(n, k) = A000007(A048158(n, k)). (End)
From Mats Granvik, Jan 26 2010, Feb 10 2010, Feb 16 2010: (Start)
T(n, k) = A172119(n) mod 2.
T(n, k) = A175105(n) mod 2.
T(n, k) = Sum_{i=1..k-1} (T(n-i, k-1) - T(n-i, k)) for k > 1 and T(n, 1) = 1.
(Jeffrey O. Shallit kindly provided a clarification along with a proof of this formula.) (End)
A049820(n) = number of zeros in n-th row. - Reinhard Zumkeller, Mar 09 2010
The determinant of this matrix where T(n, n) has been swapped with T(1,k) is equal to the n-th term of the Mobius function. - Mats Granvik, Jul 21 2012
T(n, k) = Sum_{y=1..n} Sum_{x=1..n} [GCD((x/y)*(k/n), n) = k]. - Mats Granvik, Dec 17 2023

Edited by Peter Luschny, Oct 18 2023

A018819 Binary partition function: number of partitions of n into powers of 2.

Original entry on oeis.org

1, 1, 2, 2, 4, 4, 6, 6, 10, 10, 14, 14, 20, 20, 26, 26, 36, 36, 46, 46, 60, 60, 74, 74, 94, 94, 114, 114, 140, 140, 166, 166, 202, 202, 238, 238, 284, 284, 330, 330, 390, 390, 450, 450, 524, 524, 598, 598, 692, 692, 786, 786, 900, 900, 1014, 1014, 1154, 1154, 1294, 1294

Offset: 0

David W. Wilson, N. J. A. Sloane and J. H. Conway

First differences of A000123; also A000123 with terms repeated. See the relevant proof that follows the first formula below.
Among these partitions there is exactly one partition with all distinct terms, as every number can be expressed as the sum of the distinct powers of 2.
Euler transform of A036987 with offset 1.
a(n) is the number of "non-squashing" partitions of n, that is, partitions n = p_1 + p_2 + ... + p_k with 1 <= p_1 <= p_2 <= ... <= p_k and p_1 + p_2 + ... + p_i <= p_{i+1} for all 1 <= i < k. - N. J. A. Sloane, Nov 30 2003
Normally the OEIS does not include sequences like this where every term is repeated, but an exception was made for this one because of its importance. The unrepeated sequence A000123 is the main entry.
Number of different partial sums from 1 + [1, *2] + [1, *2] + ..., where [1, *2] means we can either add 1 or multiply by 2. E.g., a(6) = 6 because we have 6 = 1 + 1 + 1 + 1 + 1 + 1 = (1+1) * 2 + 1 + 1 = 1 * 2 * 2 + 1 + 1 = (1+1+1) * 2 = 1 * 2 + 1 + 1 + 1 + 1 = (1*2+1) * 2 where the connection is defined via expanding each bracket; e.g., this is 6 = 1 + 1 + 1 + 1 + 1 + 1 = 2 + 2 + 1 + 1 = 4 + 1 + 1 = 2 + 2 + 2 = 2 + 1 + 1 + 1 + 1 = 4 + 2. - Jon Perry, Jan 01 2004
Number of partitions p of n such that the number of compositions generated by p is odd. For proof see the Alekseyev and Adams-Watters link. - Vladeta Jovovic, Aug 06 2007
Differs from A008645 first at a(64). - R. J. Mathar, May 28 2008
Appears to be row sums of A155077. - Mats Granvik, Jan 19 2009
Number of partitions (p_1, p_2, ..., p_k) of n, with p_1 >= p_2 >= ... >= p_k, such that for each i, p_i >= p_{i+1} + ... + p_k. - John MCKAY (mckay(AT)encs.concordia.ca), Mar 06 2009 (these are the "non-squashing" partitions as nonincreasing lists).
Equals rightmost diagonal of triangle of A168261. Starting with offset 1 = eigensequence of triangle A115361 and row sums of triangle A168261. - Gary W. Adamson, Nov 21 2009
Equals convolution square root of A171238: (1, 2, 5, 8, 16, 24, 40, 56, 88, ...). - Gary W. Adamson, Dec 05 2009
Let B = the n-th convolution power of the sequence and C = the aerated variant of B. It appears that B/C = the binomial sequence beginning (1, n, ...). Example: Third convolution power of the sequence is (1, 3, 9, 19, 42, 78, 146, ...), with C = (1, 0, 3, 0, 9, 0, 19, ...). Then B/C = (1, 3, 6, 10, 15, 21, ...). - Gary W. Adamson, Aug 15 2016
From Gary W. Adamson, Sep 08 2016: (Start)
The limit of the matrix power M^k as n-->inf results in a single column vector equal to the sequence, where M is the following production matrix:
  1, 0, 0, 0, 0, ...
  1, 0, 0, 0, 0, ...
  1, 1, 0, 0, 0, ...
  1, 1, 0, 0, 0, ...
  1, 1, 1, 0, 0, ...
  1, 1, 1, 0, 0, ...
  1, 1, 1, 1, 0, ...
  1, 1, 1, 1, 0, ...
  1, 1, 1, 1, 1, ...
  ... (End)
a(n) is the number of "non-borrowing" partitions of n, meaning binary subtraction of a smaller part from a larger part will never require place-value borrowing. - David V. Feldman, Jan 29 2020
From Gus Wiseman, May 25 2024: (Start)
Also the number of multisets of positive integers whose binary rank is n, where the binary rank of a multiset m is given by Sum_i 2^(m_i-1). For example, the a(1) = 1 through a(8) = 10 multisets are:
  {1}  {2}   {12}   {3}     {13}     {23}      {123}      {4}
       {11}  {111}  {22}    {122}    {113}     {1113}     {33}
                    {112}   {1112}   {222}     {1222}     {223}
                    {1111}  {11111}  {1122}    {11122}    {1123}
                                     {11112}   {111112}   {2222}
                                     {111111}  {1111111}  {11113}
                                                          {11222}
                                                          {111122}
                                                          {1111112}
                                                          {11111111}
(End)

			G.f. = 1 + x + 2*x^2 + 2*x^3 + 4*x^4 + 4*x^5 + 6*x^6 + 6*x^7 + 10*x^8 + ...
a(4) = 4: the partitions are 4, 2 + 2, 2 + 1 + 1, 1 + 1 + 1 + 1.
a(7) = 6: the partitions are 4 + 2 + 1, 4 + 1 + 1 + 1, 2 + 2 + 2 + 1, 2 + 2 + 1 + 1 + 1, 2 + 1 + 1 + 1 + 1 + 1, 1 + 1 + 1 + 1 + 1 + 1 + 1.
From _Joerg Arndt_, Dec 17 2012: (Start)
The a(10) = 14 binary partitions of 10 are (in lexicographic order)
[ 1]  [ 1 1 1 1 1 1 1 1 1 1 ]
[ 2]  [ 2 1 1 1 1 1 1 1 1 ]
[ 3]  [ 2 2 1 1 1 1 1 1 ]
[ 4]  [ 2 2 2 1 1 1 1 ]
[ 5]  [ 2 2 2 2 1 1 ]
[ 6]  [ 2 2 2 2 2 ]
[ 7]  [ 4 1 1 1 1 1 1 ]
[ 8]  [ 4 2 1 1 1 1 ]
[ 9]  [ 4 2 2 1 1 ]
[10]  [ 4 2 2 2 ]
[11]  [ 4 4 1 1 ]
[12]  [ 4 4 2 ]
[13]  [ 8 1 1 ]
[14]  [ 8 2 ]
The a(11) = 14 binary partitions of 11 are obtained by appending 1 to each partition in the list.
The a(10) = 14 non-squashing partitions of 10 are (in lexicographic order)
[ 1]  [ 6 3 1 1 ]
[ 2]  [ 6 3 2 ]
[ 3]  [ 6 4 1 ]
[ 4]  [ 6 5 ]
[ 5]  [ 7 2 1 1 ]
[ 6]  [ 7 2 2 ]
[ 7]  [ 7 3 1 ]
[ 8]  [ 7 4 ]
[ 9]  [ 8 2 1 ]
[10]  [ 8 3 ]
[11]  [ 9 1 1 ]
[12]  [ 9 2 ]
[13]  [ 10 1 ]
[14]  [ 11 ]
The a(11) = 14 non-squashing partitions of 11 are obtained by adding 1 to the first part in each partition in the list.
(End)
From _David V. Feldman_, Jan 29 2020: (Start)
The a(10) = 14 non-borrowing partitions of 10 are (in lexicographic order)
[ 1] [1 1 1 1 1 1 1 1 1 1]
[ 2] [2 2 2 2 2]
[ 3] [3 1 1 1 1 1 1 1]
[ 4] [3 3 1 1 1 1]
[ 5] [3 3 2 2]
[ 6] [3 3 3 1]
[ 7] [5 1 1 1 1 1]
[ 8] [5 5]
[ 9] [6 2 2]
[10] [6 4]
[11] [7 1 1 1]
[12] [7 3]
[13] [9 1]
[14] [10]
The a(11) = 14 non-borrowing partitions of 11 are obtained either by adding 1 to the first even part in each partition (if any) or else appending a 1 after the last part.
(End)
For example, the five partitions of 4, written in nonincreasing order, are [1, 1, 1, 1], [2, 1, 1], [2, 2], [3, 1], [4]. The last four satisfy the condition, and a(4) = 4. The Maple program below verifies this for small values of n.

T. D. Noe, Table of n, a(n) for n = 0..1000
Max Alekseyev and Franklin T. Adams-Watters, Two proofs of an observation of Vladeta Jovovic
Giedrius Alkauskas, Generalization of the Rodseth-Gupta theorem on binary partitions, Lithuanian Math. J., 43 (2) (2003), 103-110.
Giedrius Alkauskas, Congruence Properties of the Function that Counts Compositions into Powers of 2 , J. Int. Seq. 13 (2010), 10.5.3.
Joerg Arndt, Matters Computational (The Fxtbook), section 38.1, p.729.
Scott M. Bailey and Donald M. Larson, The A(1)-module structure of the homology of Brown-Gitler spectra, arXiv:2107.01316 [math.AT], 2021.
Valentin P. Bakoev, Algorithmic approach to counting of certain types m-ary partitions, Discrete Mathematics, 275 (2004) pp. 17-41.
Philippe Biane, Laver tables and combinatorics, arXiv:1810.00548 [math.CO], 2018. Mentions this sequence.
Peter J. Cameron, Firdous Ee Jannat, Rajat Kanti Nath, and Reza Sharafdini, A survey on conjugacy class graphs of groups, arXiv:2403.09423 [math.GR], 2024.
Karl Dilcher and Larry Ericksen, Polynomial Analogues of Restricted b-ary Partition Functions, J. Int. Seq., Vol. 22 (2019), Article 19.3.2.
Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, 2009; see page 48, 581.
Maciej Gawron, Piotr Miska and Maciej Ulas, Arithmetic properties of coefficients of power series expansion of Prod_{n>=0} (1-x^(2^n))^t, arXiv:1703.01955 [math.NT], 2017.
Michael D. Hirschhorn and James A. Sellers, A different view of m-ary partitions, Australasian J. Combin., vol.30 (2004), 193-196.
Jonathan Jordan and Richard Southwell, Further Properties of Reproducing Graphs, Applied Mathematics, Vol. 1 No. 5, 2010, pp. 344-350. doi: 10.4236/am.2010.15045. - From _N. J. A. Sloane_, Feb 03 2013
Yasuyuki Kachi and Pavlos Tzermias, On the m-ary partition numbers, Algebra and Discrete Mathematics, Volume 19 (2015). Number 1, pp. 67-76.
Matjaž Konvalinka and Igor Pak, Cayley compositions, partitions, polytopes, and geometric bijections, Journal of Combinatorial Theory, Series A, Volume 123, Issue 1, April 2014, Pages 86-91; see also DOI link. - From _N. J. A. Sloane_, Dec 22 2012
Apisit Pakapongpun and Thomas Ward, Functorial Orbit counting, J. Int. Seq., 12 (2009) 09.2.4, example 25.
Øystein J. Rodseth and James A. Sellers, On a Restricted m-Non-Squashing Partition Function, Journal of Integer Sequences, Vol. 8 (2005), Article 05.5.4.
David Ruelle, Dynamical zeta functions and transfer operators, Notices Amer. Math. Soc., 49 (No. 8, 2002), 887-895; see p. 888.
N. J. A. Sloane and James A. Sellers, On non-squashing partitions, arXiv:math/0312418 [math.CO], 2003.
N. J. A. Sloane and James A. Sellers, On non-squashing partitions, Discrete Math., 294 (2005), 259-274.

A000123 is the main entry for the binary partition function and gives many more properties and references.
Cf. A115625 (labeled binary partitions), A115626 (labeled non-squashing partitions).
Convolution inverse of A106400.
Cf. A023893, A062051, A105420, A131995, A040039, A018819, A088567, A089054, A115361, A168261, A171238, A179051, A008619.
Multiplicity of n in A048675, for distinct prime indices A087207.
Row lengths of A277905.
A118462 lists binary ranks of strict integer partitions, row sums A372888.
A372890 adds up binary ranks of integer partitions.
Binary indices: A000120, A001511, A029931, A048793, A070939, A272020.
Cf. A005940, A019565, A056239, A158704, A158705, A231204, A277319, A372688.

a018819 n = a018819_list !! n
a018819_list = 1 : f (tail a008619_list) where
   f (x:xs) = (sum $ take x a018819_list) : f xs
-- Reinhard Zumkeller, Jan 28 2012

import Data.List (intersperse)
a018819 = (a018819_list !!)
a018819_list = 1 : 1 : (<*>) (zipWith (+)) (intersperse 0) (tail a018819_list)
-- Johan Wiltink, Nov 08 2018

with(combinat); N:=8; a:=array(1..N); c:=array(1..N);
for n from 1 to N do p:=partition(n); np:=nops(p); t:=0;
for s to np do r:=p[s]; r:=sort(r,`>`); nr:=nops(r); j:=1;
# while jsum(r[k],k=j+1..nr) do j:=j+1;od; # gives A040039
while j= sum(r[k],k=j+1..nr) do j:=j+1;od; # gives A018819
if j=nr then t:=t+1;fi od; a[n]:=t; od; # John McKay

max = 59; a[0] = a[1] = 1; a[n_?OddQ] := a[n] = a[n-1]; a[n_?EvenQ] := a[n] = a[n-1] + a[n/2]; Table[a[n], {n, 0, max}]
(* or *) CoefficientList[Series[1/Product[(1-x^(2^j)), {j, 0, Log[2, max] // Ceiling}], {x, 0, max}], x] (* Jean-François Alcover, May 17 2011, updated Feb 17 2014 *)
a[ n_] := If[n<1, Boole[n==0], a[n] = a[n-1] + If[EvenQ@n, a[Quotient[n,2]], 0]]; (* Michael Somos, May 04 2022 *)
Table[Count[IntegerPartitions[n],?(AllTrue[Log2[#],IntegerQ]&)],{n,0,60}] (* _Harvey P. Dale, Jun 20 2024 *)

{ n=15; v=vector(n); for (i=1,n,v[i]=vector(2^(i-1))); v[1][1]=1; for (i=2,n, k=length(v[i-1]); for (j=1,k, v[i][j]=v[i-1][j]+1; v[i][j+k]=v[i-1][j]*2)); c=vector(n); for (i=1,n, for (j=1,2^(i-1), if (v[i][j]<=n, c[v[i][j]]++))); c } /* Jon Perry */

{a(n) = my(A, m); if( n<1, n==0, m=1; A = 1 + O(x); while(m<=n, m*=2; A = subst(A, x, x^2) / (1 - x)); polcoeff(A, n))}; /* Michael Somos, Aug 25 2003 */

{a(n) = if( n<1, n==0, if( n%2, a(n-1), a(n/2)+a(n-1)))}; /* Michael Somos, Aug 25 2003 */

from functools import lru_cache
@lru_cache(maxsize=None)
def A018819(n): return 1 if n == 0 else A018819(n-1) + (0 if n % 2 else A018819(n//2)) # Chai Wah Wu, Jan 18 2022

a(2m+1) = a(2m), a(2m) = a(2m-1) + a(m). Proof: If n is odd there is a part of size 1; removing it gives a partition of n - 1. If n is even either there is a part of size 1, whose removal gives a partition of n - 1, or else all parts have even sizes and dividing each part by 2 gives a partition of n/2.
G.f.: 1 / Product_{j>=0} (1-x^(2^j)).
a(n) = (1/n)*Sum_{k = 1..n} A038712(k)*a(n-k), n > 1, a(0) = 1. - Vladeta Jovovic, Aug 22 2002
a(2*n) = a(2*n + 1) = A000123(n). - Michael Somos, Aug 25 2003
a(n) = 1 if n = 0, Sum_{j = 0..floor(n/2)} a(j) if n > 0. - David W. Wilson, Aug 16 2007
G.f. A(x) satisfies A(x^2) = (1-x) * A(x). - Michael Somos, Aug 25 2003
G.f. A(x) satisfies 0 = f(A(x), A(x^2), A(x^4)) where f(u, v, w) = u^2*w - 2*u*v^2 + v^3. - Michael Somos, Apr 10 2005
G.f. A(x) satisfies 0 = f(A(x), A(x^2), A(x^3), A(x^6)) where f(u1, u2, u3, u6) = u6 * u1^3 - 3*u3*u2*u1^2 + 3*u3*u2^2*u1 - u3*u2^3. - Michael Somos, Oct 15 2006
G.f.: 1/( Sum_{n >= 0} x^evil(n) - x^odious(n) ), where evil(n) = A001969(n) and odious(n) = A000069(n). - Paul D. Hanna, Jan 23 2012
Let A(x) by the g.f. and B(x) = A(x^k), then 0 = B*((1-A)^k - (-A)^k) + (-A)^k, see fxtbook link. - Joerg Arndt, Dec 17 2012
G.f.: Product_{n>=0} (1+x^(2^n))^(n+1), see the fxtbook link. - Joerg Arndt, Feb 28 2014
G.f.: 1 + Sum_{i>=0} x^(2^i) / Product_{j=0..i} (1 - x^(2^j)). - Ilya Gutkovskiy, May 07 2017

A054525 Triangle T(n,k): T(n,k) = mu(n/k) if k divides n, T(n,k) = 0 otherwise (n >= 1, 1 <= k <= n).

Original entry on oeis.org

1, -1, 1, -1, 0, 1, 0, -1, 0, 1, -1, 0, 0, 0, 1, 1, -1, -1, 0, 0, 1, -1, 0, 0, 0, 0, 0, 1, 0, 0, 0, -1, 0, 0, 0, 1, 0, 0, -1, 0, 0, 0, 0, 0, 1, 1, -1, 0, 0, -1, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, -1, 0, -1, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1

Offset: 1

N. J. A. Sloane, Apr 09 2000

A051731 = the inverse of this triangle = A129372 * A115361. - Gary W. Adamson, Apr 15 2007

If a column T(n,0)=0 is added, these are the coefficients of the necklace polynomials multiplied by n [Moree, Metropolis]. - R. J. Mathar, Nov 11 2008

			Triangle (with rows n >= 1 and columns k >= 1) begins as follows:
   1;
  -1,  1;
  -1,  0,  1;
   0, -1,  0,  1;
  -1,  0,  0,  0,  1;
   1, -1, -1,  0,  0,  1;
  -1,  0,  0,  0,  0,  0,  1;
   0,  0,  0, -1,  0,  0,  0,  1; ...
Matrix inverse is triangle A051731:
  1;
  1, 1;
  1, 0, 1;
  1, 1, 0, 1;
  1, 0, 0, 0, 1;
  1, 1, 1, 0, 0, 1;
  1, 0, 0, 0, 0, 0, 1;
  1, 1, 0, 1, 0, 0, 0, 1; ...

G. C. Greubel, Table of n, a(n) for the first 50 rows
Trevor Hyde, Cyclotomic factors of necklace polynomials, arXiv:1811.08601 [math.CO], 2018.
N. Metropolis and G.-C. Rota, Witt vectors and the algebra of necklaces, Adv. Math. 50 (1983), 95-125.
Pieter Moree, The formal series Witt transform, Discr. Math. 295 (2005), 143-160.

Cf. A054521.
Cf. A051731, A115361, A129372.
Cf. A077050, A115359, A129360.

A054525 := proc(n,k)
    if n mod k = 0 then
        numtheory[mobius](n/k) ;
    else
        0 ;
    end if;
end proc: # R. J. Mathar, Oct 21 2012

t[n_, k_] := If[Divisible[n, k], MoebiusMu[n/k ], 0]; Table[t[n, k], {n, 1, 14}, {k, 1, n}] // Flatten (* Jean-François Alcover, Jan 14 2014 *)

tabl(nn) = {T = matrix(nn, nn, n, k, if (! (n % k), moebius(n/k), 0)); for (n=1, nn, for (k=1, n, print1(T[n, k], ", ");); print(););} \\ Michel Marcus, Mar 28 2015

row(n) = Vecrev(sumdiv(n, d, moebius(d)*x^(n/d))/x); \\ Michel Marcus, Aug 24 2021

from math import isqrt, comb
from sympy import mobius
def A054525(n): return 0 if (a:=(m:=isqrt(k:=n<<1))+(k>m*(m+1)))%(b:=n-comb(a,2)) else mobius(a//b) # Chai Wah Wu, Nov 13 2024

Matrix inverse of triangle A051731, where A051731(n, k) = 1 if k|n, 0 otherwise. - Paul D. Hanna, Jan 09 2006
Equals = A129360 * A115359 as infinite lower triangular matrices. - Gary W. Adamson, Apr 15 2007
Bivariate g.f.: Sum_{n, k >= 1} T(n, k)*x^n*y^k = Sum_{m >= 1} mu(m)*x^m*y/(1 - x^m*y). - Petros Hadjicostas, Jun 25 2019

A129527 a(2n) = a(n) + 2n, a(2n+1) = 2n + 1.

Original entry on oeis.org

0, 1, 3, 3, 7, 5, 9, 7, 15, 9, 15, 11, 21, 13, 21, 15, 31, 17, 27, 19, 35, 21, 33, 23, 45, 25, 39, 27, 49, 29, 45, 31, 63, 33, 51, 35, 63, 37, 57, 39, 75, 41, 63, 43, 77, 45, 69, 47, 93, 49, 75, 51, 91, 53, 81, 55, 105, 57, 87, 59, 105, 61, 93, 63, 127, 65, 99, 67

Offset: 0

Ralf Stephan, May 29 2007

Sum of odd part of n and its double, fourfold, eightfold etc. <= n.
Starting with 1 = the ruler function triangle A115361 * [1, 2, 3, ...]. - Gary W. Adamson, Nov 27 2009
Starting with 1 and parsed into subsets of 1, 2, 4, 8, ... terms, sum of terms in the subsets = A006516: (1, 6, 28, 120, ...). Example: 120 = (15 + 9 + 15 + 11 + 21 + 13 + 21 + 15). - Gary W. Adamson Mar 18 2011
a(n) = Sum(even divisors of 2(n-1) not including 2(n-1) that are obtained dividing repeatedly by 2) + (greatest odd divisor of 2(n-1), including 1), for the initial case 2(1-1)=0 will be set to 0. E.g., (offset is starting with n=1) a(3) = Sum(even divisors of 2*(3-1)=2*2=4 not including 4 obtained dividing repeatedly by 2) + greatest odd divisor of 4 = (2)+(1)=3; a(4) = Sum(even divisors of 2*(4-1)=6 not including 6 obtained dividing repeatedly by 2) + greatest odd divisor of 6 = (0) + (3) = 3; a(5) = Sum(even divisors of 2*(5-1)=8 not including 8 obtained dividing repeatedly by 2) + greatest odd divisor of 8 = (4+2) + (1) = 7, etc. - David Morales Marciel, Dec 21 2015
For n >=1, a(n) is the sum of divisors d of n such that n/d is a power of 2. - Amiram Eldar, Nov 17 2022

Robert Israel, Table of n, a(n) for n = 0..10000
Cristina Ballantine and Mircea Merca, Plane Partitions and Divisors, Symmetry (2024), Vol. 16, Iss. 5. See page 3.
Mircea Merca and Emil Simion, n-Color Partitions into Distinct Parts as Sums over Partitions, Symmetry (2023) Vol. 15, Iss. 11.

Row sums of A129265 and A129559.

Cf. A000265, A006516, A062570, A115361.

f:= proc(n) option remember;
  if n::odd then n else n + procname(n/2) fi
end proc:
f(0):= 0:
seq(f(n),n=0..100); # Robert Israel, Dec 20 2015

a[n_] := a[n] = If[EvenQ@ n, a[n/2] + n, n]; {0}~Join~Array[a, 67] (* Michael De Vlieger, Jun 26 2017 *)

a(n)=if (n==0, 0, sum(k=0,valuation(n,2),n/2^k)); \\ corrected by Michel Marcus, Dec 22 2021

a(n)=if(n<2,return(n)); my(k=valuation(n,2)); 2*n-n>>k \\ Charles R Greathouse IV, Feb 09 2016

a(n)=sumdiv(n, d, eulerphi(2*d)) \\ Andrew Howroyd, Aug 07 2018

G.f.: Sum_{k>=0} x^(2^k)/(1-x^(2^k))^2.
Dirichlet g.f.: zeta(s-1)*2^s/(2^s-1). - Ralf Stephan, Jun 17 2007
G.f. satisfies g(x) = g(x^2) + x/(1-x)^2. - Robert Israel, Dec 20 2015
n <= a(n) <= 2n - 1 for n > 0. - Charles R Greathouse IV, Feb 09 2016
Conjecture: a(n) = 2*n-A000265(n) for n > 0. - Velin Yanev, Jun 23 2017. [Joerg Arndt, Jun 23 2017: For odd n the conjecture holds, for even n induction should work.
Andrey Zabolotskiy, Aug 03 2017: Confirm: induction works, the conjecture holds for all n.]
a(n) for n > 0 is multiplicative with a(2^e) = 2^(e+1)-1 and a(p^e) = p^e for prime p > 2 and e >= 0. - Werner Schulte, Jul 02 2018
Inverse Moebius transform of A062570. - Andrew Howroyd, Aug 07 2018
Sum_{k=1..n} a(k) ~ 2*n^2/3. - Vaclav Kotesovec, Jun 11 2020
a(n) = A038712(n)*A000265(n), for n > 0. - Ivan N. Ianakiev, Feb 24 2025

cp's OEIS Frontend

A188023 Triangle read by rows, T(n,k) = k*A115361(n-1,k-1).

Views

Author

Keywords

Comments

Examples

Crossrefs

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Haskell

Haskell

Julia

Magma

Maple

Mathematica

MuPAD

PARI

PARI

PARI

Python

Sage

Formula

Extensions

A051731 Triangle read by rows: T(n, k) = 1 if k divides n, T(n, k) = 0 otherwise, for 1 <= k <= n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

Python

Sage

Formula

Extensions

A018819 Binary partition function: number of partitions of n into powers of 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Haskell

Maple

Mathematica

PARI

PARI

PARI

Python

Formula

A054525 Triangle T(n,k): T(n,k) = mu(n/k) if k divides n, T(n,k) = 0 otherwise (n >= 1, 1 <= k <= n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica