cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Previous Showing 21-30 of 146 results. Next

A000217 Triangular numbers: a(n) = binomial(n+1,2) = n*(n+1)/2 = 0 + 1 + 2 + ... + n.

Original entry on oeis.org

0, 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120, 136, 153, 171, 190, 210, 231, 253, 276, 300, 325, 351, 378, 406, 435, 465, 496, 528, 561, 595, 630, 666, 703, 741, 780, 820, 861, 903, 946, 990, 1035, 1081, 1128, 1176, 1225, 1275, 1326, 1378, 1431
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

Also referred to as T(n) or C(n+1, 2) or binomial(n+1, 2) (preferred).
Also generalized hexagonal numbers: n*(2*n-1), n=0, +-1, +-2, +-3, ... Generalized k-gonal numbers are second k-gonal numbers and positive terms of k-gonal numbers interleaved, k >= 5. In this case k = 6. - Omar E. Pol, Sep 13 2011 and Aug 04 2012
Number of edges in complete graph of order n+1, K_{n+1}.
Number of legal ways to insert a pair of parentheses in a string of n letters. E.g., there are 6 ways for three letters: (a)bc, (ab)c, (abc), a(b)c, a(bc), ab(c). Proof: there are C(n+2,2) ways to choose where the parentheses might go, but n + 1 of them are illegal because the parentheses are adjacent. Cf. A002415.
For n >= 1, a(n) is also the genus of a nonsingular curve of degree n+2, such as the Fermat curve x^(n+2) + y^(n+2) = 1. - Ahmed Fares (ahmedfares(AT)my_deja.com), Feb 21 2001
From Harnack's theorem (1876), the number of branches of a nonsingular curve of order n is bounded by a(n-1)+1, and the bound can be achieved. See also A152947. - Benoit Cloitre, Aug 29 2002. Corrected by Robert McLachlan, Aug 19 2024
Number of tiles in the set of double-n dominoes. - Scott A. Brown, Sep 24 2002
Number of ways a chain of n non-identical links can be broken up. This is based on a similar problem in the field of proteomics: the number of ways a peptide of n amino acid residues can be broken up in a mass spectrometer. In general, each amino acid has a different mass, so AB and BC would have different masses. - James A. Raymond, Apr 08 2003
Triangular numbers - odd numbers = shifted triangular numbers; 1, 3, 6, 10, 15, 21, ... - 1, 3, 5, 7, 9, 11, ... = 0, 0, 1, 3, 6, 10, ... - Xavier Acloque, Oct 31 2003 [Corrected by Derek Orr, May 05 2015]
Centered polygonal numbers are the result of [number of sides * A000217 + 1]. E.g., centered pentagonal numbers (1,6,16,31,...) = 5 * (0,1,3,6,...) + 1. Centered heptagonal numbers (1,8,22,43,...) = 7 * (0,1,3,6,...) + 1. - Xavier Acloque, Oct 31 2003
Maximum number of lines formed by the intersection of n+1 planes. - Ron R. King, Mar 29 2004
Number of permutations of [n] which avoid the pattern 132 and have exactly 1 descent. - Mike Zabrocki, Aug 26 2004
Number of ternary words of length n-1 with subwords (0,1), (0,2) and (1,2) not allowed. - Olivier Gérard, Aug 28 2012
Number of ways two different numbers can be selected from the set {0,1,2,...,n} without repetition, or, number of ways two different numbers can be selected from the set {1,2,...,n} with repetition.
Conjecturally, 1, 6, 120 are the only numbers that are both triangular and factorial. - Christopher M. Tomaszewski (cmt1288(AT)comcast.net), Mar 30 2005
Binomial transform is {0, 1, 5, 18, 56, 160, 432, ...}, A001793 with one leading zero. - Philippe Deléham, Aug 02 2005
Each pair of neighboring terms adds to a perfect square. - Zak Seidov, Mar 21 2006
Number of transpositions in the symmetric group of n+1 letters, i.e., the number of permutations that leave all but two elements fixed. - Geoffrey Critzer, Jun 23 2006
With rho(n):=exp(i*2*Pi/n) (an n-th root of 1) one has, for n >= 1, rho(n)^a(n) = (-1)^(n+1). Just use the triviality a(2*k+1) == 0 (mod (2*k+1)) and a(2*k) == k (mod (2*k)).
a(n) is the number of terms in the expansion of (a_1 + a_2 + a_3)^(n-1). - Sergio Falcon, Feb 12 2007
a(n+1) is the number of terms in the complete homogeneous symmetric polynomial of degree n in 2 variables. - Richard Barnes, Sep 06 2017
The number of distinct handshakes in a room with n+1 people. - Mohammad K. Azarian, Apr 12 2007 [corrected, Joerg Arndt, Jan 18 2016]
Equal to the rank (minimal cardinality of a generating set) of the semigroup PT_n\S_n, where PT_n and S_n denote the partial transformation semigroup and symmetric group on [n]. - James East, May 03 2007
a(n) gives the total number of triangles found when cevians are drawn from a single vertex on a triangle to the side opposite that vertex, where n = the number of cevians drawn+1. For instance, with 1 cevian drawn, n = 1+1 = 2 and a(n)= 2*(2+1)/2 = 3 so there is a total of 3 triangles in the figure. If 2 cevians are drawn from one point to the opposite side, then n = 1+2 = 3 and a(n) = 3*(3+1)/2 = 6 so there is a total of 6 triangles in the figure. - Noah Priluck (npriluck(AT)gmail.com), Apr 30 2007
For n >= 1, a(n) is the number of ways in which n-1 can be written as a sum of three nonnegative integers if representations differing in the order of the terms are considered to be different. In other words, for n >= 1, a(n) is the number of nonnegative integral solutions of the equation x + y + z = n-1. - Amarnath Murthy, Apr 22 2001 (edited by Robert A. Beeler)
a(n) is the number of levels with energy n + 3/2 (in units of h*f0, with Planck's constant h and the oscillator frequency f0) of the three-dimensional isotropic harmonic quantum oscillator. See the comment by A. Murthy above: n = n1 + n2 + n3 with positive integers and ordered. Proof from the o.g.f. See the A. Messiah reference. - Wolfdieter Lang, Jun 29 2007
From Hieronymus Fischer, Aug 06 2007: (Start)
Numbers m >= 0 such that round(sqrt(2m+1)) - round(sqrt(2m)) = 1.
Numbers m >= 0 such that ceiling(2*sqrt(2m+1)) - 1 = 1 + floor(2*sqrt(2m)).
Numbers m >= 0 such that fract(sqrt(2m+1)) > 1/2 and fract(sqrt(2m)) < 1/2, where fract(x) is the fractional part of x (i.e., x - floor(x), x >= 0). (End)
If Y and Z are 3-blocks of an n-set X, then, for n >= 6, a(n-1) is the number of (n-2)-subsets of X intersecting both Y and Z. - Milan Janjic, Nov 09 2007
Equals row sums of triangle A143320, n > 0. - Gary W. Adamson, Aug 07 2008
a(n) is also an even perfect number in A000396 iff n is a Mersenne prime A000668. - Omar E. Pol, Sep 05 2008. Unnecessary assumption removed and clarified by Rick L. Shepherd, Apr 14 2025
Equals row sums of triangle A152204. - Gary W. Adamson, Nov 29 2008
The number of matches played in a round robin tournament: n*(n-1)/2 gives the number of matches needed for n players. Everyone plays against everyone else exactly once. - Georg Wrede (georg(AT)iki.fi), Dec 18 2008
-a(n+1) = E(2)*binomial(n+2,2) (n >= 0) where E(n) are the Euler numbers in the enumeration A122045. Viewed this way, a(n) is the special case k=2 in the sequence of diagonals in the triangle A153641. - Peter Luschny, Jan 06 2009
Equivalent to the first differences of successive tetrahedral numbers. See A000292. - Jeremy Cahill (jcahill(AT)inbox.com), Apr 15 2009
The general formula for alternating sums of powers is in terms of the Swiss-Knife polynomials P(n,x) A153641 2^(-n-1)(P(n,1)-(-1)^k P(n,2k+1)). Thus a(k) = |2^(-3)(P(2,1)-(-1)^k P(2,2k+1))|. - Peter Luschny, Jul 12 2009
a(n) is the smallest number > a(n-1) such that gcd(n,a(n)) = gcd(n,a(n-1)). If n is odd this gcd is n; if n is even it is n/2. - Franklin T. Adams-Watters, Aug 06 2009
Partial sums of A001477. - Juri-Stepan Gerasimov, Jan 25 2010. [A-number corrected by Omar E. Pol, Jun 05 2012]
The numbers along the right edge of Floyd's triangle are 1, 3, 6, 10, 15, .... - Paul Muljadi, Jan 25 2010
From Charlie Marion, Dec 03 2010: (Start)
More generally, a(2k+1) == j*(2j-1) (mod 2k+2j+1) and
a(2k) == [-k + 2j*(j-1)] (mod 2k+2j).
Column sums of:
1 3 5 7 9 ...
1 3 5 ...
1 ...
...............
---------------
1 3 6 10 15 ...
Sum_{n>=1} 1/a(n)^2 = 4*Pi^2/3-12 = 12 less than the volume of a sphere with radius Pi^(1/3).
(End)
A004201(a(n)) = A000290(n); A004202(a(n)) = A002378(n). - Reinhard Zumkeller, Feb 12 2011
1/a(n+1), n >= 0, has e.g.f. -2*(1+x-exp(x))/x^2, and o.g.f. 2*(x+(1-x)*log(1-x))/x^2 (see the Stephen Crowley formula line). -1/(2*a(n+1)) is the z-sequence for the Sheffer triangle of the coefficients of the Bernoulli polynomials A196838/A196839. - Wolfdieter Lang, Oct 26 2011
From Charlie Marion, Feb 23 2012: (Start)
a(n) + a(A002315(k)*n + A001108(k+1)) = (A001653(k+1)*n + A001109(k+1))^2. For k=0 we obtain a(n) + a(n+1) = (n+1)^2 (identity added by N. J. A. Sloane on Feb 19 2004).
a(n) + a(A002315(k)*n - A055997(k+1)) = (A001653(k+1)*n - A001109(k))^2.
(End)
Plot the three points (0,0), (a(n), a(n+1)), (a(n+1), a(n+2)) to form a triangle. The area will be a(n+1)/2. - J. M. Bergot, May 04 2012
The sum of four consecutive triangular numbers, beginning with a(n)=n*(n+1)/2, minus 2 is 2*(n+2)^2. a(n)*a(n+2)/2 = a(a(n+1)-1). - J. M. Bergot, May 17 2012
(a(n)*a(n+3) - a(n+1)*a(n+2))*(a(n+1)*a(n+4) - a(n+2)*a(n+3))/8 = a((n^2+5*n+4)/2). - J. M. Bergot, May 18 2012
a(n)*a(n+1) + a(n+2)*a(n+3) + 3 = a(n^2 + 4*n + 6). - J. M. Bergot, May 22 2012
In general, a(n)*a(n+1) + a(n+k)*a(n+k+1) + a(k-1)*a(k) = a(n^2 + (k+2)*n + k*(k+1)). - Charlie Marion, Sep 11 2012
a(n)*a(n+3) + a(n+1)*a(n+2) = a(n^2 + 4*n + 2). - J. M. Bergot, May 22 2012
In general, a(n)*a(n+k) + a(n+1)*a(n+k-1) = a(n^2 + (k+1)*n + k-1). - Charlie Marion, Sep 11 2012
a(n)*a(n+2) + a(n+1)*a(n+3) = a(n^2 + 4*n + 3). - J. M. Bergot, May 22 2012
Three points (a(n),a(n+1)), (a(n+1),a(n)) and (a(n+2),a(n+3)) form a triangle with area 4*a(n+1). - J. M. Bergot, May 23 2012
a(n) + a(n+k) = (n+k)^2 - (k^2 + (2n-1)*k -2n)/2. For k=1 we obtain a(n) + a(n+1) = (n+1)^2 (see below). - Charlie Marion, Oct 02 2012
In n-space we can define a(n-1) nontrivial orthogonal projections. For example, in 3-space there are a(2)=3 (namely point onto line, point onto plane, line onto plane). - Douglas Latimer, Dec 17 2012
From James East, Jan 08 2013: (Start)
For n >= 1, a(n) is equal to the rank (minimal cardinality of a generating set) and idempotent rank (minimal cardinality of an idempotent generating set) of the semigroup P_n\S_n, where P_n and S_n denote the partition monoid and symmetric group on [n].
For n >= 3, a(n-1) is equal to the rank and idempotent rank of the semigroup T_n\S_n, where T_n and S_n denote the full transformation semigroup and symmetric group on [n].
(End)
For n >= 3, a(n) is equal to the rank and idempotent rank of the semigroup PT_n\S_n, where PT_n and S_n denote the partial transformation semigroup and symmetric group on [n]. - James East, Jan 15 2013
Conjecture: For n > 0, there is always a prime between A000217(n) and A000217(n+1). Sequence A065383 has the first 1000 of these primes. - Ivan N. Ianakiev, Mar 11 2013
The formula, a(n)*a(n+4k+2)/2 + a(k) = a(a(n+2k+1) - (k^2+(k+1)^2)), is a generalization of the formula a(n)*a(n+2)/2 = a(a(n+1)-1) in Bergot's comment dated May 17 2012. - Charlie Marion, Mar 28 2013
The series Sum_{k>=1} 1/a(k) = 2, given in a formula below by Jon Perry, Jul 13 2003, has partial sums 2*n/(n+1) (telescopic sum) = A022998(n)/A026741(n+1). - Wolfdieter Lang, Apr 09 2013
For odd m = 2k+1, we have the recurrence a(m*n + k) = m^2*a(n) + a(k). Corollary: If number T is in the sequence then so is 9*T+1. - Lekraj Beedassy, May 29 2013
Euler, in Section 87 of the Opera Postuma, shows that whenever T is a triangular number then 9*T + 1, 25*T + 3, 49*T + 6 and 81*T + 10 are also triangular numbers. In general, if T is a triangular number then (2*k + 1)^2*T + k*(k + 1)/2 is also a triangular number. - Peter Bala, Jan 05 2015
Using 1/b and 1/(b+2) will give a Pythagorean triangle with sides 2*b + 2, b^2 + 2*b, and b^2 + 2*b + 2. Set b=n-1 to give a triangle with sides of lengths 2*n,n^2-1, and n^2 + 1. One-fourth the perimeter = a(n) for n > 1. - J. M. Bergot, Jul 24 2013
a(n) = A028896(n)/6, where A028896(n) = s(n) - s(n-1) are the first differences of s(n) = n^3 + 3*n^2 + 2*n - 8. s(n) can be interpreted as the sum of the 12 edge lengths plus the sum of the 6 face areas plus the volume of an n X (n-1) X (n-2) rectangular prism. - J. M. Bergot, Aug 13 2013
Dimension of orthogonal group O(n+1). - Eric M. Schmidt, Sep 08 2013
Number of positive roots in the root system of type A_n (for n > 0). - Tom Edgar, Nov 05 2013
A formula for the r-th successive summation of k, for k = 1 to n, is binomial(n+r,r+1) [H. W. Gould]. - Gary Detlefs, Jan 02 2014
Also the alternating row sums of A095831. Also the alternating row sums of A055461, for n >= 1. - Omar E. Pol, Jan 26 2014
For n >= 3, a(n-2) is the number of permutations of 1,2,...,n with the distribution of up (1) - down (0) elements 0...011 (n-3 zeros), or, the same, a(n-2) is up-down coefficient {n,3} (see comment in A060351). - Vladimir Shevelev, Feb 14 2014
a(n) is the dimension of the vector space of symmetric n X n matrices. - Derek Orr, Mar 29 2014
Non-vanishing subdiagonal of A132440^2/2, aside from the initial zero. First subdiagonal of unsigned A238363. Cf. A130534 for relations to colored forests, disposition of flags on flagpoles, and colorings of the vertices of complete graphs. - Tom Copeland, Apr 05 2014
The number of Sidon subsets of {1,...,n+1} of size 2. - Carl Najafi, Apr 27 2014
Number of factors in the definition of the Vandermonde determinant V(x_1,x_2,...,x_n) = Product_{1 <= i < k <= n} x_i - x_k. - Tom Copeland, Apr 27 2014
Number of weak compositions of n into three parts. - Robert A. Beeler, May 20 2014
Suppose a bag contains a(n) red marbles and a(n+1) blue marbles, where a(n), a(n+1) are consecutive triangular numbers. Then, for n > 0, the probability of choosing two marbles at random and getting two red or two blue is 1/2. In general, for k > 2, let b(0) = 0, b(1) = 1 and, for n > 1, b(n) = (k-1)*b(n-1) - b(n-2) + 1. Suppose, for n > 0, a bag contains b(n) red marbles and b(n+1) blue marbles. Then the probability of choosing two marbles at random and getting two red or two blue is (k-1)/(k+1). See also A027941, A061278, A089817, A053142, A092521. - Charlie Marion, Nov 03 2014
Let O(n) be the oblong number n(n+1) = A002378 and S(n) the square number n^2 = A000290(n). Then a(4n) = O(3n) - O(n), a(4n+1) = S(3n+1) - S(n), a(4n+2) = S(3n+2) - S(n+1) and a(4n+3) = O(3n+2) - O(n). - Charlie Marion, Feb 21 2015
Consider the partition of the natural numbers into parts from the set S=(1,2,3,...,n). The length (order) of the signature of the resulting sequence is given by the triangular numbers. E.g., for n=10, the signature length is 55. - David Neil McGrath, May 05 2015
a(n) counts the partitions of (n-1) unlabeled objects into three (3) parts (labeled a,b,c), e.g., a(5)=15 for (n-1)=4. These are (aaaa),(bbbb),(cccc),(aaab),(aaac),(aabb),(aacc),(aabc),(abbc),(abcc),(abbb),(accc),(bbcc),(bccc),(bbbc). - David Neil McGrath, May 21 2015
Conjecture: the sequence is the genus/deficiency of the sinusoidal spirals of index n which are algebraic curves. The value 0 corresponds to the case of the Bernoulli Lemniscate n=2. So the formula conjectured is (n-1)(n-2)/2. - Wolfgang Tintemann, Aug 02 2015
Conjecture: Let m be any positive integer. Then, for each n = 1,2,3,... the set {Sum_{k=s..t} 1/k^m: 1 <= s <= t <= n} has cardinality a(n) = n*(n+1)/2; in other words, all the sums Sum_{k=s..t} 1/k^m with 1 <= s <= t are pairwise distinct. (I have checked this conjecture via a computer and found no counterexample.) - Zhi-Wei Sun, Sep 09 2015
The Pisano period lengths of reading the sequence modulo m seem to be A022998(m). - R. J. Mathar, Nov 29 2015
For n >= 1, a(n) is the number of compositions of n+4 into n parts avoiding the part 2. - Milan Janjic, Jan 07 2016
In this sequence only 3 is prime. - Fabian Kopp, Jan 09 2016
Suppose you are playing Bulgarian Solitaire (see A242424 and Chamberland's and Gardner's books) and, for n > 0, you are starting with a single pile of a(n) cards. Then the number of operations needed to reach the fixed state {n, n-1,...,1} is a(n-1). For example, {6}->{5,1}->{4,2}->{3,2,1}. - Charlie Marion, Jan 14 2016
Numbers k such that 8k + 1 is a square. - Juri-Stepan Gerasimov, Apr 09 2016
Every perfect cube is the difference of the squares of two consecutive triangular numbers. 1^2-0^2 = 1^3, 3^2-1^2 = 2^3, 6^2-3^2 = 3^3. - Miquel Cerda, Jun 26 2016
For n > 1, a(n) = tau_n(k*) where tau_n(k) is the number of ordered n-factorizations of k and k* is the square of a prime. For example, tau_3(4) = tau_3(9) = tau_3(25) = tau_3(49) = 6 (see A007425) since the number of divisors of 4, 9, 25, and 49's divisors is 6, and a(3) = 6. - Melvin Peralta, Aug 29 2016
In an (n+1)-dimensional hypercube, number of two-dimensional faces congruent with a vertex (see also A001788). - Stanislav Sykora, Oct 23 2016
Generalizations of the familiar formulas, a(n) + a(n+1) = (n+1)^2 (Feb 19 2004) and a(n)^2 + a(n+1)^2 = a((n+1)^2) (Nov 22 2006), follow: a(n) + a(n+2k-1) + 4a(k-1) = (n+k)^2 + 6a(k-1) and a(n)^2 + a(n+2k-1)^2 + (4a(k-1))^2 + 3a(k-1) = a((n+k)^2 + 6a(k-1)). - Charlie Marion, Nov 27 2016
a(n) is also the greatest possible number of diagonals in a polyhedron with n+4 vertices. - Vladimir Letsko, Dec 19 2016
For n > 0, 2^5 * (binomial(n+1,2))^2 represents the first integer in a sum of 2*(2*n + 1)^2 consecutive integers that equals (2*n + 1)^6. - Patrick J. McNab, Dec 25 2016
Does not satisfy Benford's law (cf. Ross, 2012). - N. J. A. Sloane, Feb 12 2017
Number of ordered triples (a,b,c) of positive integers not larger than n such that a+b+c = 2n+1. - Aviel Livay, Feb 13 2017
Number of inequivalent tetrahedral face colorings using at most n colors so that no color appears only once. - David Nacin, Feb 22 2017
Also the Wiener index of the complete graph K_{n+1}. - Eric W. Weisstein, Sep 07 2017
Number of intersections between the Bernstein polynomials of degree n. - Eric Desbiaux, Apr 01 2018
a(n) is the area of a triangle with vertices at (1,1), (n+1,n+2), and ((n+1)^2, (n+2)^2). - Art Baker, Dec 06 2018
For n > 0, a(n) is the smallest k > 0 such that n divides numerator of (1/a(1) + 1/a(2) + ... + 1/a(n-1) + 1/k). It should be noted that 1/1 + 1/3 + 1/6 + ... + 2/(n(n+1)) = 2n/(n+1). - Thomas Ordowski, Aug 04 2019
Upper bound of the number of lines in an n-homogeneous supersolvable line arrangement (see Theorem 1.1 in Dimca). - Stefano Spezia, Oct 04 2019
For n > 0, a(n+1) is the number of lattice points on a triangular grid with side length n. - Wesley Ivan Hurt, Aug 12 2020
From Michael Chu, May 04 2022: (Start)
Maximum number of distinct nonempty substrings of a string of length n.
Maximum cardinality of the sumset A+A, where A is a set of n numbers. (End)
a(n) is the number of parking functions of size n avoiding the patterns 123, 132, and 312. - Lara Pudwell, Apr 10 2023
Suppose two rows, each consisting of n evenly spaced dots, are drawn in parallel. Suppose we bijectively draw lines between the dots of the two rows. For n >= 1, a(n - 1) is the maximal possible number of intersections between the lines. Equivalently, the maximal number of inversions in a permutation of [n]. - Sela Fried, Apr 18 2023
The following equation complements the generalization in Bala's Comment (Jan 05 2015). (2k + 1)^2*a(n) + a(k) = a((2k + 1)*n + k). - Charlie Marion, Aug 28 2023
a(n) + a(n+k) + a(k-1) + (k-1)*n = (n+k)^2. For k = 1, we have a(n) + a(n+1) = (n+1)^2. - Charlie Marion, Nov 17 2023
a(n+1)/3 is the expected number of steps to escape from a linear row of n positions starting at a random location and randomly performing steps -1 or +1 with equal probability. - Hugo Pfoertner, Jul 22 2025
a(n+1) is the number of nonnegative integer solutions to p + q + r = n. By Sylvester's law of inertia, it is also the number of congruence classes of real symmetric n-by-n matrices or equivalently, the number of symmetric bilinear forms on a real n-dimensional vector space. - Paawan Jethva, Jul 24 2025

Examples

			G.f.: x + 3*x^2 + 6*x^3 + 10*x^4 + 15*x^5 + 21*x^6 + 28*x^7 + 36*x^8 + 45*x^9 + ...
When n=3, a(3) = 4*3/2 = 6.
Example(a(4)=10): ABCD where A, B, C and D are different links in a chain or different amino acids in a peptide possible fragments: A, B, C, D, AB, ABC, ABCD, BC, BCD, CD = 10.
a(2): hollyhock leaves on the Tokugawa Mon, a(4): points in Pythagorean tetractys, a(5): object balls in eight-ball billiards. - _Bradley Klee_, Aug 24 2015
From _Gus Wiseman_, Oct 28 2020: (Start)
The a(1) = 1 through a(5) = 15 ordered triples of positive integers summing to n + 2 [Beeler, McGrath above] are the following. These compositions are ranked by A014311.
  (111)  (112)  (113)  (114)  (115)
         (121)  (122)  (123)  (124)
         (211)  (131)  (132)  (133)
                (212)  (141)  (142)
                (221)  (213)  (151)
                (311)  (222)  (214)
                       (231)  (223)
                       (312)  (232)
                       (321)  (241)
                       (411)  (313)
                              (322)
                              (331)
                              (412)
                              (421)
                              (511)
The unordered version is A001399(n-3) = A069905(n), with Heinz numbers A014612.
The strict case is A001399(n-6)*6, ranked by A337453.
The unordered strict case is A001399(n-6), with Heinz numbers A007304.
(End)

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. 828.
  • C. Alsina and R. B. Nelson, Charming Proofs: A Journey into Elegant Mathematics, MAA, 2010. See Chapter 1.
  • T. M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976, page 2.
  • A. H. Beiler, Recreations in the Theory of Numbers, Dover, NY, 1964, p. 189.
  • A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, p. 109ff.
  • Marc Chamberland, Single Digits: In Praise of Small Numbers, Chapter 3, The Number Three, p. 72, Princeton University Press, 2015.
  • L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 155.
  • John H. Conway and Richard K. Guy, The Book of Numbers, New York: Springer-Verlag, 1996. See pp. 33, 38, 40, 70.
  • J. M. De Koninck and A. Mercier, 1001 Problèmes en Théorie Classique des Nombres, Problème 309 pp 46-196, Ellipses, Paris, 2004
  • E. Deza and M. M. Deza, Figurate numbers, World Scientific Publishing (2012), page 6.
  • L. E. Dickson, History of the Theory of Numbers. Carnegie Institute Public. 256, Washington, DC, Vol. 1, 1919; Vol. 2, 1920; Vol. 3, 1923, see vol. 2, p. 1.
  • Martin Gardner, Colossal Book of Mathematics, Chapter 34, Bulgarian Solitaire and Other Seemingly Endless Tasks, pp. 455-467, W. W. Norton & Company, 2001.
  • James Gleick, The Information: A History, A Theory, A Flood, Pantheon, 2011. [On page 82 mentions a table of the first 19999 triangular numbers published by E. de Joncort in 1762.]
  • Jan Gullberg, Mathematics from the Birth of Numbers, W. W. Norton & Co., NY & London, 1997, §4.6 Mathematical Proof and §8.6 Figurate Numbers, pp. 158-159, 289-290.
  • Cay S. Horstmann, Scala for the Impatient. Upper Saddle River, New Jersey: Addison-Wesley (2012): 171.
  • Elemer Labos, On the number of RGB-colors we can distinguish. Partition Spectra. Lecture at 7th Hungarian Conference on Biometry and Biomathematics. Budapest. Jul 06 2005.
  • A. Messiah, Quantum Mechanics, Vol.1, North Holland, Amsterdam, 1965, p. 457.
  • J. C. P. Miller, editor, Table of Binomial Coefficients. Royal Society Mathematical Tables, Vol. 3, Cambridge Univ. Press, 1954.
  • Alfred S. Posamentier, Math Charmers, Tantalizing Tidbits for the Mind, Prometheus Books, NY, 2003, pages 52-53, 129-132, 274.
  • 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).
  • James J. Tattersall, Elementary Number Theory in Nine Chapters, Cambridge University Press, 1999, pages 2-6, 13.
  • T. Trotter, Some Identities for the Triangular Numbers, Journal of Recreational Mathematics, Spring 1973, 6(2).
  • D. Wells, The Penguin Dictionary of Curious and Interesting Numbers, pp. 91-93 Penguin Books 1987.

Links

Crossrefs

The figurate numbers, with parameter k as in the second Python program: A001477 (k=0), this sequence (k=1), A000290 (k=2), A000326 (k=3), A000384 (k=4), A000566 (k=5), A000567 (k=6), A001106 (k=7), A001107 (k=8).
Cf. A000096, A000124, A000292, A000330, A000396, A000668, A001082, A001788, A002024, A002378, A002415, A003056 (inverse function), A004526, A006011, A007318, A008953, A008954, A010054 (characteristic function), A028347, A036666, A046092, A051942, A055998, A055999, A056000, A056115, A056119, A056121, A056126, A062717, A087475, A101859, A109613, A143320, A210569, A245031, A245300, A060544, A016754.
a(n) = A110449(n, 0).
a(n) = A110555(n+2, 2).
A diagonal of A008291.
Column 2 of A195152.
Numbers of the form n*t(n+k,h)-(n+k)*t(n,h), where t(i,h) = i*(i+2*h+1)/2 for any h (for A000217 is k=1): A005563, A067728, A140091, A140681, A212331.
Boustrophedon transforms: A000718, A000746.
Iterations: A007501 (start=2), A013589 (start=4), A050542 (start=5), A050548 (start=7), A050536 (start=8), A050909 (start=9).
Cf. A002817 (doubly triangular numbers), A075528 (solutions of a(n)=a(m)/2).
Cf. A104712 (first column, starting with a(1)).
Some generalized k-gonal numbers are A001318 (k=5), this sequence (k=6), A085787 (k=7), etc.
A001399(n-3) = A069905(n) = A211540(n+2) counts 3-part partitions.
A001399(n-6) = A069905(n-3) = A211540(n-1) counts 3-part strict partitions.
A011782 counts compositions of any length.
A337461 counts pairwise coprime triples, with unordered version A307719.
Cf. A000212, A001840, A007304, A156040, A220377, A337483, A337604.
Cf. A099174, A130534, A132440, A238363.

Programs

  • Haskell
    a000217 n = a000217_list !! n
a000217_list = scanl1 (+) [0..] -- Reinhard Zumkeller, Sep 23 2011
  • J
    a000217=: *-:@>: NB. Stephen Makdisi, May 02 2018
  • Magma
    [n*(n+1)/2: n in [0..60]]; // Bruno Berselli, Jul 11 2014
  • Magma
    [n: n in [0..1500] | IsSquare(8*n+1)]; // Juri-Stepan Gerasimov, Apr 09 2016
  • Maple
    A000217 := proc(n) n*(n+1)/2; end;
istriangular:=proc(n) local t1; t1:=floor(sqrt(2*n)); if n = t1*(t1+1)/2 then return true else return false; end if; end proc; # N. J. A. Sloane, May 25 2008
ZL := [S, {S=Prod(B, B, B), B=Set(Z, 1 <= card)}, unlabeled]:
seq(combstruct[count](ZL, size=n), n=2..55); # Zerinvary Lajos, Mar 24 2007
isA000217 := proc(n)
    issqr(1+8*n) ;
end proc: # R. J. Mathar, Nov 29 2015 [This is the recipe Leonhard Euler proposes in chapter VII of his "Vollständige Anleitung zur Algebra", 1765. Peter Luschny, Sep 02 2022]
  • Mathematica
    Array[ #*(# - 1)/2 &, 54] (* Zerinvary Lajos, Jul 10 2009 *)
FoldList[#1 + #2 &, 0, Range@ 50] (* Robert G. Wilson v, Feb 02 2011 *)
Accumulate[Range[0,70]] (* Harvey P. Dale, Sep 09 2012 *)
CoefficientList[Series[x / (1 - x)^3, {x, 0, 50}], x] (* Vincenzo Librandi, Jul 30 2014 *)
(* For Mathematica 10.4+ *) Table[PolygonalNumber[n], {n, 0, 53}] (* Arkadiusz Wesolowski, Aug 27 2016 *)
LinearRecurrence[{3, -3, 1}, {0, 1, 3}, 54] (* Robert G. Wilson v, Dec 04 2016 *)
(* The following Mathematica program, courtesy of Steven J. Miller, is useful for testing if a sequence is Benford. To test a different sequence only one line needs to be changed. This strongly suggests that the triangular numbers are not Benford, since the second and third columns of the output disagree. - N. J. A. Sloane, Feb 12 2017 *)
fd[x_] := Floor[10^Mod[Log[10, x], 1]]
benfordtest[num_] := Module[{},
   For[d = 1, d <= 9, d++, digit[d] = 0];
   For[n = 1, n <= num, n++,
    {
     d = fd[n(n+1)/2];
     If[d != 0, digit[d] = digit[d] + 1];
     }];
   For[d = 1, d <= 9, d++, digit[d] = 1.0 digit[d]/num];
   For[d = 1, d <= 9, d++,
    Print[d, " ", 100.0 digit[d], " ", 100.0 Log[10, (d + 1)/d]]];
   ];
benfordtest[20000]
Table[Length[Join@@Permutations/@IntegerPartitions[n,{3}]],{n,0,15}] (* Gus Wiseman, Oct 28 2020 *)
  • PARI
    A000217(n) = n * (n + 1) / 2;
  • PARI
    is_A000217(n)=n*2==(1+n=sqrtint(2*n))*n \\ M. F. Hasler, May 24 2012
  • PARI
    is(n)=ispolygonal(n,3) \\ Charles R Greathouse IV, Feb 28 2014
  • PARI
    list(lim)=my(v=List(),n,t); while((t=n*n++/2)<=lim,listput(v,t)); Vec(v) \\ Charles R Greathouse IV, Jun 18 2021
  • Python
    for n in range(0,60): print(n*(n+1)//2, end=', ') # Stefano Spezia, Dec 06 2018
  • Python
    # Intended to compute the initial segment of the sequence, not
# isolated terms. If in the iteration the line "x, y = x + y + 1, y + 1"
# is replaced by "x, y = x + y + k, y + k" then the figurate numbers are obtained,
# for k = 0 (natural A001477), k = 1 (triangular), k = 2 (squares), k = 3 (pentagonal), k = 4 (hexagonal), k = 5 (heptagonal), k = 6 (octagonal), etc.
def aList():
    x, y = 1, 1
    yield 0
    while True:
        yield x
        x, y = x + y + 1, y + 1
A000217 = aList()
print([next(A000217) for i in range(54)]) # Peter Luschny, Aug 03 2019
  • SageMath
    [n*(n+1)/2 for n in (0..60)] # Bruno Berselli, Jul 11 2014
  • Scala
    (1 to 53).scanLeft(0)( + ) // Horstmann (2012), p. 171
  • Scheme
    (define (A000217 n) (/ (* n (+ n 1)) 2)) ;; Antti Karttunen, Jul 08 2017

Formula

G.f.: x/(1-x)^3. - Simon Plouffe in his 1992 dissertation
E.g.f.: exp(x)*(x+x^2/2).
a(n) = a(-1-n).
a(n) + a(n-1)*a(n+1) = a(n)^2. - Terrel Trotter, Jr., Apr 08 2002
a(n) = (-1)^n*Sum_{k=1..n} (-1)^k*k^2. - Benoit Cloitre, Aug 29 2002
a(n+1) = ((n+2)/n)*a(n), Sum_{n>=1} 1/a(n) = 2. - Jon Perry, Jul 13 2003
For n > 0, a(n) = A001109(n) - Sum_{k=0..n-1} (2*k+1)*A001652(n-1-k); e.g., 10 = 204 - (1*119 + 3*20 + 5*3 + 7*0). - Charlie Marion, Jul 18 2003
With interpolated zeros, this is n*(n+2)*(1+(-1)^n)/16. - Benoit Cloitre, Aug 19 2003
a(n+1) is the determinant of the n X n symmetric Pascal matrix M_(i, j) = binomial(i+j+1, i). - Benoit Cloitre, Aug 19 2003
a(n) = ((n+1)^3 - n^3 - 1)/6. - Xavier Acloque, Oct 24 2003
a(n) = a(n-1) + (1 + sqrt(1 + 8*a(n-1)))/2. This recursive relation is inverted when taking the negative branch of the square root, i.e., a(n) is transformed into a(n-1) rather than a(n+1). - Carl R. White, Nov 04 2003
a(n) = Sum_{k=1..n} phi(k)*floor(n/k) = Sum_{k=1..n} A000010(k)*A010766(n, k) (R. Dedekind). - Vladeta Jovovic, Feb 05 2004
a(n) + a(n+1) = (n+1)^2. - N. J. A. Sloane, Feb 19 2004
a(n) = a(n-2) + 2*n - 1. - Paul Barry, Jul 17 2004
a(n) = sqrt(Sum_{i=1..n} Sum_{j=1..n} (i*j)) = sqrt(A000537(n)). - Alexander Adamchuk, Oct 24 2004
a(n) = sqrt(sqrt(Sum_{i=1..n} Sum_{j=1..n} (i*j)^3)) = (Sum_{i=1..n} Sum_{j=1..n} Sum_{k=1..n} (i*j*k)^3)^(1/6). - Alexander Adamchuk, Oct 26 2004
a(n) == 1 (mod n+2) if n is odd and a(n) == n/2+2 (mod n+2) if n is even. - Jon Perry, Dec 16 2004
a(0) = 0, a(1) = 1, a(n) = 2*a(n-1) - a(n-2) + 1. - Miklos Kristof, Mar 09 2005
a(n) = a(n-1) + n. - Zak Seidov, Mar 06 2005
a(n) = A108299(n+3,4) = -A108299(n+4,5). - Reinhard Zumkeller, Jun 01 2005
a(n) = A111808(n,2) for n > 1. - Reinhard Zumkeller, Aug 17 2005
a(n)*a(n+1) = A006011(n+1) = (n+1)^2*(n^2+2)/4 = 3*A002415(n+1) = 1/2*a(n^2+2*n). a(n-1)*a(n) = (1/2)*a(n^2-1). - Alexander Adamchuk, Apr 13 2006 [Corrected and edited by Charlie Marion, Nov 26 2010]
a(n) = floor((2*n+1)^2/8). - Paul Barry, May 29 2006
For positive n, we have a(8*a(n))/a(n) = 4*(2*n+1)^2 = (4*n+2)^2, i.e., a(A033996(n))/a(n) = 4*A016754(n) = (A016825(n))^2 = A016826(n). - Lekraj Beedassy, Jul 29 2006
a(n)^2 + a(n+1)^2 = a((n+1)^2) [R B Nelsen, Math Mag 70 (2) (1997), p. 130]. - R. J. Mathar, Nov 22 2006
a(n) = A126890(n,0). - Reinhard Zumkeller, Dec 30 2006
a(n)*a(n+k)+a(n+1)*a(n+1+k) = a((n+1)*(n+1+k)). Generalizes previous formula dated Nov 22 2006 [and comments by J. M. Bergot dated May 22 2012]. - Charlie Marion, Feb 04 2011
(sqrt(8*a(n)+1)-1)/2 = n. - David W. Cantrell (DWCantrell(AT)sigmaxi.net), Feb 26 2007
a(n) = A023896(n) + A067392(n). - Lekraj Beedassy, Mar 02 2007
Sum_{k=0..n} a(k)*A039599(n,k) = A002457(n-1), for n >= 1. - Philippe Deléham, Jun 10 2007
8*a(n)^3 + a(n)^2 = Y(n)^2, where Y(n) = n*(n+1)*(2*n+1)/2 = 3*A000330(n). - Mohamed Bouhamida, Nov 06 2007 [Edited by Derek Orr, May 05 2015]
A general formula for polygonal numbers is P(k,n) = (k-2)*(n-1)n/2 + n = n + (k-2)*A000217(n-1), for n >= 1, k >= 3. - Omar E. Pol, Apr 28 2008 and Mar 31 2013
a(3*n) = A081266(n), a(4*n) = A033585(n), a(5*n) = A144312(n), a(6*n) = A144314(n). - Reinhard Zumkeller, Sep 17 2008
a(n) = A022264(n) - A049450(n). - Reinhard Zumkeller, Oct 09 2008
If we define f(n,i,a) = Sum_{j=0..k-1} (binomial(n,k)*Stirling1(n-k,i)*Product_{j=0..k-1} (-a-j)), then a(n) = -f(n,n-1,1), for n >= 1. - Milan Janjic, Dec 20 2008
4*a(x) + 4*a(y) + 1 = (x+y+1)^2 + (x-y)^2. - Vladimir Shevelev, Jan 21 2009
a(n) = A000124(n-1) + n-1 for n >= 2. a(n) = A000124(n) - 1. - Jaroslav Krizek, Jun 16 2009
An exponential generating function for the inverse of this sequence is given by Sum_{m>=0} ((Pochhammer(1, m)*Pochhammer(1, m))*x^m/(Pochhammer(3, m)*factorial(m))) = ((2-2*x)*log(1-x)+2*x)/x^2, the n-th derivative of which has a closed form which must be evaluated by taking the limit as x->0. A000217(n+1) = (lim_{x->0} d^n/dx^n (((2-2*x)*log(1-x)+2*x)/x^2))^-1 = (lim_{x->0} (2*Gamma(n)*(-1/x)^n*(n*(x/(-1+x))^n*(-x+1+n)*LerchPhi(x/(-1+x), 1, n) + (-1+x)*(n+1)*(x/(-1+x))^n + n*(log(1-x)+log(-1/(-1+x)))*(-x+1+n))/x^2))^-1. - Stephen Crowley, Jun 28 2009
a(n) = A034856(n+1) - A005408(n) = A005843(n) + A000124(n) - A005408(n). - Jaroslav Krizek, Sep 05 2009
a(A006894(n)) = a(A072638(n-1)+1) = A072638(n) = A006894(n+1)-1 for n >= 1. For n=4, a(11) = 66. - Jaroslav Krizek, Sep 12 2009
With offset 1, a(n) = floor(n^3/(n+1))/2. - Gary Detlefs, Feb 14 2010
a(n) = 4*a(floor(n/2)) + (-1)^(n+1)*floor((n+1)/2). - Bruno Berselli, May 23 2010
a(n) = 3*a(n-1) - 3*a(n-2) + a(n-3); a(0)=0, a(1)=1. - Mark Dols, Aug 20 2010
From Charlie Marion, Oct 15 2010: (Start)
a(n) + 2*a(n-1) + a(n-2) = n^2 + (n-1)^2; and
a(n) + 3*a(n-1) + 3*a(n-2) + a(n-3) = n^2 + 2*(n-1)^2 + (n-2)^2.
In general, for n >= m > 2, Sum_{k=0..m} binomial(m,m-k)*a(n-k) = Sum_{k=0..m-1} binomial(m-1,m-1-k)*(n-k)^2.
a(n) - 2*a(n-1) + a(n-2) = 1, a(n) - 3*a(n-1) + 3*a(n-2) - a(n-3) = 0 and a(n) - 4*a(n-1) + 6*a(n-2) - 4*(a-3) + a(n-4) = 0.
In general, for n >= m > 2, Sum_{k=0..m} (-1)^k*binomial(m,m-k)*a(n-k) = 0.
(End)
a(n) = sqrt(A000537(n)). - Zak Seidov, Dec 07 2010
For n > 0, a(n) = 1/(Integral_{x=0..Pi/2} 4*(sin(x))^(2*n-1)*(cos(x))^3). - Francesco Daddi, Aug 02 2011
a(n) = A110654(n)*A008619(n). - Reinhard Zumkeller, Aug 24 2011
a(2*k-1) = A000384(k), a(2*k) = A014105(k), k > 0. - Omar E. Pol, Sep 13 2011
a(n) = A026741(n)*A026741(n+1). - Charles R Greathouse IV, Apr 01 2012
a(n) + a(a(n)) + 1 = a(a(n)+1). - J. M. Bergot, Apr 27 2012
a(n) = -s(n+1,n), where s(n,k) are the Stirling numbers of the first kind, A048994. - Mircea Merca, May 03 2012
a(n)*a(n+1) = a(Sum_{m=1..n} A005408(m))/2, for n >= 1. For example, if n=8, then a(8)*a(9) = a(80)/2 = 1620. - Ivan N. Ianakiev, May 27 2012
a(n) = A002378(n)/2 = (A001318(n) + A085787(n))/2. - Omar E. Pol, Jan 11 2013
G.f.: x * (1 + 3x + 6x^2 + ...) = x * Product_{j>=0} (1+x^(2^j))^3 = x * A(x) * A(x^2) * A(x^4) * ..., where A(x) = (1 + 3x + 3x^2 + x^3). - Gary W. Adamson, Jun 26 2012
G.f.: G(0) where G(k) = 1 + (2*k+3)*x/(2*k+1 - x*(k+2)*(2*k+1)/(x*(k+2) + (k+1)/G(k+1))); (continued fraction, 3rd kind, 3-step). - Sergei N. Gladkovskii, Nov 23 2012
a(n) = A002088(n) + A063985(n). - Reinhard Zumkeller, Jan 21 2013
G.f.: x + 3*x^2/(Q(0)-3*x) where Q(k) = 1 + k*(x+1) + 3*x - x*(k+1)*(k+4)/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, Mar 14 2013
a(n) + a(n+1) + a(n+2) + a(n+3) + n = a(2*n+4). - Ivan N. Ianakiev, Mar 16 2013
a(n) + a(n+1) + ... + a(n+8) + 6*n = a(3*n+15). - Charlie Marion, Mar 18 2013
a(n) + a(n+1) + ... + a(n+20) + 2*n^2 + 57*n = a(5*n+55). - Charlie Marion, Mar 18 2013
3*a(n) + a(n-1) = a(2*n), for n > 0. - Ivan N. Ianakiev, Apr 05 2013
In general, a(k*n) = (2*k-1)*a(n) + a((k-1)*n-1). - Charlie Marion, Apr 20 2015
Also, a(k*n) = a(k)*a(n) + a(k-1)*a(n-1). - Robert Israel, Apr 20 2015
a(n+1) = det(binomial(i+2,j+1), 1 <= i,j <= n). - Mircea Merca, Apr 06 2013
a(n) = floor(n/2) + ceiling(n^2/2) = n - floor(n/2) + floor(n^2/2). - Wesley Ivan Hurt, Jun 15 2013
a(n) = floor((n+1)/(exp(2/(n+1))-1)). - Richard R. Forberg, Jun 22 2013
Sum_{n>=1} a(n)/n! = 3*exp(1)/2 by the e.g.f. Also see A067764 regarding ratios calculated this way for binomial coefficients in general. - Richard R. Forberg, Jul 15 2013
Sum_{n>=1} (-1)^(n+1)/a(n) = 4*log(2) - 2 = 0.7725887... . - Richard R. Forberg, Aug 11 2014
2/(Sum_{n>=m} 1/a(n)) = m, for m > 0. - Richard R. Forberg, Aug 12 2014
A228474(a(n))=n; A248952(a(n))=0; A248953(a(n))=a(n); A248961(a(n))=A000330(n). - Reinhard Zumkeller, Oct 20 2014
a(a(n)-1) + a(a(n+2)-1) + 1 = A000124(n+1)^2. - Charlie Marion, Nov 04 2014
a(n) = 2*A000292(n) - A000330(n). - Luciano Ancora, Mar 14 2015
a(n) = A007494(n-1) + A099392(n) for n > 0. - Bui Quang Tuan, Mar 27 2015
Sum_{k=0..n} k*a(k+1) = a(A000096(n+1)). - Charlie Marion, Jul 15 2015
Let O(n) be the oblong number n(n+1) = A002378(n) and S(n) the square number n^2 = A000290(n). Then a(n) + a(n+2k) = O(n+k) + S(k) and a(n) + a(n+2k+1) = S(n+k+1) + O(k). - Charlie Marion, Jul 16 2015
A generalization of the Nov 22 2006 formula, a(n)^2 + a(n+1)^2 = a((n+1)^2), follows. Let T(k,n) = a(n) + k. Then for all k, T(k,n)^2 + T(k,n+1)^2 = T(k,(n+1)^2 + 2*k) - 2*k. - Charlie Marion, Dec 10 2015
a(n)^2 + a(n+1)^2 = a(a(n) + a(n+1)). Deducible from N. J. A. Sloane's a(n) + a(n+1) = (n+1)^2 and R. B. Nelson's a(n)^2 + a(n+1)^2 = a((n+1)^2). - Ben Paul Thurston, Dec 28 2015
Dirichlet g.f.: (zeta(s-2) + zeta(s-1))/2. - Ilya Gutkovskiy, Jun 26 2016
a(n)^2 - a(n-1)^2 = n^3. - Miquel Cerda, Jun 29 2016
a(n) = A080851(0,n-1). - R. J. Mathar, Jul 28 2016
a(n) = A000290(n-1) - A034856(n-4). - Peter M. Chema, Sep 25 2016
a(n)^2 + a(n+3)^2 + 19 = a(n^2 + 4*n + 10). - Charlie Marion, Nov 23 2016
2*a(n)^2 + a(n) = a(n^2+n). - Charlie Marion, Nov 29 2016
G.f.: x/(1-x)^3 = (x * r(x) * r(x^3) * r(x^9) * r(x^27) * ...), where r(x) = (1 + x + x^2)^3 = (1 + 3*x + 6*x^2 + 7*x^3 + 6*x^4 + 3*x^5 + x^6). - Gary W. Adamson, Dec 03 2016
a(n) = sum of the elements of inverse of matrix Q(n), where Q(n) has elements q_i,j = 1/(1-4*(i-j)^2). So if e = appropriately sized vector consisting of 1's, then a(n) = e'.Q(n)^-1.e. - Michael Yukish, Mar 20 2017
a(n) = Sum_{k=1..n} ((2*k-1)!!*(2*n-2*k-1)!!)/((2*k-2)!!*(2*n-2*k)!!). - Michael Yukish, Mar 20 2017
Sum_{i=0..k-1} a(n+i) = (3*k*n^2 + 3*n*k^2 + k^3 - k)/6. - Christopher Hohl, Feb 23 2019
a(n) = A060544(n + 1) - A016754(n). - Ralf Steiner, Nov 09 2019
a(n) == 0 (mod n) iff n is odd (see De Koninck reference). - Bernard Schott, Jan 10 2020
8*a(k)*a(n) + ((a(k)-1)*n + a(k))^2 = ((a(k)+1)*n + a(k))^2. This formula reduces to the well-known formula, 8*a(n) + 1 = (2*n+1)^2, when k = 1. - Charlie Marion, Jul 23 2020
a(k)*a(n) = Sum_{i = 0..k-1} (-1)^i*a((k-i)*(n-i)). - Charlie Marion, Dec 04 2020
From Amiram Eldar, Jan 20 2021: (Start)
Product_{n>=1} (1 + 1/a(n)) = cosh(sqrt(7)*Pi/2)/(2*Pi).
Product_{n>=2} (1 - 1/a(n)) = 1/3. (End)
a(n) = Sum_{k=1..2*n-1} (-1)^(k+1)*a(k)*a(2*n-k). For example, for n = 4, 1*28 - 3*21 + 6*15 - 10*10 + 15*6 - 21*3 + 28*1 = 10. - Charlie Marion, Mar 23 2022
2*a(n) = A000384(n) - n^2 + 2*n. In general, if P(k,n) = the n-th k-gonal number, then (j+1)*a(n) = P(5 + j, n) - n^2 + (j+1)*n. More generally, (j+1)*P(k,n) = P(2*k + (k-2)*(j-1),n) - n^2 + (j+1)*n. - Charlie Marion, Mar 14 2023
a(n) = A109613(n) * A004526(n+1). - Torlach Rush, Nov 10 2023
a(n) = (1/6)* Sum_{k = 0..3*n} (-1)^(n+k+1) * k*(k + 1) * binomial(3*n+k, 2*k). - Peter Bala, Nov 03 2024
From Peter Bala, Jul 05 2025: (Start)
The following series telescope: for k >= 0,
Sum_{n >= 1} a(n)*a(n+2)*...*a(n+2*k)/(a(n+1)*a(n+3)*...*a(n+2*k+3)) = 1/(2*k + 3);
Sum_{n >= 1} a(n+1)*a(n+3)*...*a(n+2*k+1)/(a(n)*a(n+2)*...*a(n+2*k+2)) = 2/(2*k + 3) * Sum_{i = 1..2*k+3} 1/i. (End)

Extensions

Edited by Derek Orr, May 05 2015

A000010 Euler totient function phi(n): count numbers <= n and prime to n.

Original entry on oeis.org

1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4, 12, 6, 8, 8, 16, 6, 18, 8, 12, 10, 22, 8, 20, 12, 18, 12, 28, 8, 30, 16, 20, 16, 24, 12, 36, 18, 24, 16, 40, 12, 42, 20, 24, 22, 46, 16, 42, 20, 32, 24, 52, 18, 40, 24, 36, 28, 58, 16, 60, 30, 36, 32, 48, 20, 66, 32, 44
Offset: 1

Views

Author

N. J. A. Sloane

Keywords

Comments

Number of elements in a reduced residue system modulo n.
Degree of the n-th cyclotomic polynomial (cf. A013595). - Benoit Cloitre, Oct 12 2002
Number of distinct generators of a cyclic group of order n. Number of primitive n-th roots of unity. (A primitive n-th root x is such that x^k is not equal to 1 for k = 1, 2, ..., n - 1, but x^n = 1.) - Lekraj Beedassy, Mar 31 2005
Also number of complex Dirichlet characters modulo n; Sum_{k=1..n} a(k) is asymptotic to (3/Pi^2)*n^2. - Steven Finch, Feb 16 2006
a(n) is the highest degree of irreducible polynomial dividing 1 + x + x^2 + ... + x^(n-1) = (x^n - 1)/(x - 1). - Alexander Adamchuk, Sep 02 2006, corrected Sep 27 2006
a(p) = p - 1 for prime p. a(n) is even for n > 2. For n > 2, a(n)/2 = A023022(n) = number of partitions of n into 2 ordered relatively prime parts. - Alexander Adamchuk, Jan 25 2007
Number of automorphisms of the cyclic group of order n. - Benoit Jubin, Aug 09 2008
a(n+2) equals the number of palindromic Sturmian words of length n which are "bispecial", prefix or suffix of two Sturmian words of length n + 1. - Fred Lunnon, Sep 05 2010
Suppose that a and n are coprime positive integers, then by Euler's totient theorem, any factor of n divides a^phi(n) - 1. - Lei Zhou, Feb 28 2012
If m has k prime factors, (p_1, p_2, ..., p_k), then phi(m*n) = (Product_{i=1..k} phi (p_i*n))/phi(n)^(k-1). For example, phi(42*n) = phi(2*n)*phi(3*n)*phi(7*n)/phi(n)^2. - Gary Detlefs, Apr 21 2012
Sum_{n>=1} a(n)/n! = 1.954085357876006213144... This sum is referenced in Plouffe's inverter. - Alexander R. Povolotsky, Feb 02 2013 (see A336334. - Hugo Pfoertner, Jul 22 2020)
The order of the multiplicative group of units modulo n. - Michael Somos, Aug 27 2013
A strong divisibility sequence, that is, gcd(a(n), a(m)) = a(gcd(n, m)) for all positive integers n and m. - Michael Somos, Dec 30 2016
From Eric Desbiaux, Jan 01 2017: (Start)
a(n) equals the Ramanujan sum c_n(n) (last term on n-th row of triangle A054533).
a(n) equals the Jordan function J_1(n) (cf. A007434, A059376, A059377, which are the Jordan functions J_2, J_3, J_4, respectively). (End)
For n > 1, a(n) appears to be equal to the number of semi-meander solutions for n with top arches containing exactly 2 mountain ranges and exactly 2 arches of length 1. - Roger Ford, Oct 11 2017
a(n) is the minimum dimension of a lattice able to generate, via cut-and-project, the quasilattice whose diffraction pattern features n-fold rotational symmetry. The case n=15 is the first n > 1 in which the following simpler definition fails: "a(n) is the minimum dimension of a lattice with n-fold rotational symmetry". - Felix Flicker, Nov 08 2017
Number of cyclic Latin squares of order n with the first row in ascending order. - Eduard I. Vatutin, Nov 01 2020
a(n) is the number of rational numbers p/q >= 0 (in lowest terms) such that p + q = n. - Rémy Sigrist, Jan 17 2021
From Richard L. Ollerton, May 08 2021: (Start)
Formulas for the numerous OEIS entries involving Dirichlet convolution of a(n) and some sequence h(n) can be derived using the following (n >= 1):
Sum_{d|n} phi(d)*h(n/d) = Sum_{k=1..n} h(gcd(n,k)) [see P. H. van der Kamp link] = Sum_{d|n} h(d)*phi(n/d) = Sum_{k=1..n} h(n/gcd(n,k))*phi(gcd(n,k))/phi(n/gcd(n,k)). Similarly,
Sum_{d|n} phi(d)*h(d) = Sum_{k=1..n} h(n/gcd(n,k)) = Sum_{k=1..n} h(gcd(n,k))*phi(gcd(n,k))/phi(n/gcd(n,k)).
More generally,
Sum_{d|n} h(d) = Sum_{k=1..n} h(gcd(n,k))/phi(n/gcd(n,k)) = Sum_{k=1..n} h(n/gcd(n,k))/phi(n/gcd(n,k)).
In particular, for sequences involving the Möbius transform:
Sum_{d|n} mu(d)*h(n/d) = Sum_{k=1..n} h(gcd(n,k))*mu(n/gcd(n,k))/phi(n/gcd(n,k)) = Sum_{k=1..n} h(n/gcd(n,k))*mu(gcd(n,k))/phi(n/gcd(n,k)), where mu = A008683.
Use of gcd(n,k)*lcm(n,k) = n*k and phi(gcd(n,k))*phi(lcm(n,k)) = phi(n)*phi(k) provide further variations. (End)
From Richard L. Ollerton, Nov 07 2021: (Start)
Formulas for products corresponding to the sums above may found using the substitution h(n) = log(f(n)) where f(n) > 0 (for example, cf. formulas for the sum A018804 and product A067911 of gcd(n,k)):
Product_{d|n} f(n/d)^phi(d) = Product_{k=1..n} f(gcd(n,k)) = Product_{d|n} f(d)^phi(n/d) = Product_{k=1..n} f(n/gcd(n,k))^(phi(gcd(n,k))/phi(n/gcd(n,k))),
Product_{d|n} f(d)^phi(d) = Product_{k=1..n} f(n/gcd(n,k)) = Product_{k=1..n} f(gcd(n,k))^(phi(gcd(n,k))/phi(n/gcd(n,k))),
Product_{d|n} f(d) = Product_{k=1..n} f(gcd(n,k))^(1/phi(n/gcd(n,k))) = Product_{k=1..n} f(n/gcd(n,k))^(1/phi(n/gcd(n,k))),
Product_{d|n} f(n/d)^mu(d) = Product_{k=1..n} f(gcd(n,k))^(mu(n/gcd(n,k))/phi(n/gcd(n,k))) = Product_{k=1..n} f(n/gcd(n,k))^(mu(gcd(n,k))/phi(n/gcd(n,k))), where mu = A008683. (End)
a(n+1) is the number of binary words with exactly n distinct subsequences (when n > 0). - Radoslaw Zak, Nov 29 2021

Examples

			G.f. = x + x^2 + 2*x^3 + 2*x^4 + 4*x^5 + 2*x^6 + 6*x^7 + 4*x^8 + 6*x^9 + 4*x^10 + ...
a(8) = 4 with {1, 3, 5, 7} units modulo 8. a(10) = 4 with {1, 3, 7, 9} units modulo 10. - _Michael Somos_, Aug 27 2013
From _Eduard I. Vatutin_, Nov 01 2020: (Start)
The a(5)=4 cyclic Latin squares with the first row in ascending order are:
  0 1 2 3 4   0 1 2 3 4   0 1 2 3 4   0 1 2 3 4
  1 2 3 4 0   2 3 4 0 1   3 4 0 1 2   4 0 1 2 3
  2 3 4 0 1   4 0 1 2 3   1 2 3 4 0   3 4 0 1 2
  3 4 0 1 2   1 2 3 4 0   4 0 1 2 3   2 3 4 0 1
  4 0 1 2 3   3 4 0 1 2   2 3 4 0 1   1 2 3 4 0
(End)

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 24.
  • M. Baake and U. Grimm, Aperiodic Order Vol. 1: A Mathematical Invitation, Encyclopedia of Mathematics and its Applications 149, Cambridge University Press, 2013: see Tables 3.1 and 3.2.
  • Florian Cajori, A History of Mathematical Notations, Dover edition (2012), par. 409.
  • L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 193.
  • John H. Conway and Richard K. Guy, The Book of Numbers, New York: Springer-Verlag, 1996. See pp. 154-156.
  • C. W. Curtis, Pioneers of Representation Theory ..., Amer. Math. Soc., 1999; see p. 3.
  • J.-M. De Koninck & A. Mercier, 1001 Problèmes en Théorie Classique des Nombres, Ellipses, Paris, 2004, Problème 529, pp. 71-257.
  • L. E. Dickson, History of the Theory of Numbers. Carnegie Institute Public. 256, Washington, DC, Vol. 1, 1919; Vol. 2, 1920; Vol. 3, 1923, see vol. 1, Chapter V.
  • S. R. Finch, Mathematical Constants, Cambridge, 2003, pp. 115-119.
  • Carl Friedrich Gauss, "Disquisitiones Arithmeticae", Yale University Press, 1965; see p. 21.
  • Ronald L. Graham, Donald E. Knuth and Oren Patashnik, Concrete Math., 2n-d ed.; Addison-Wesley, 1994, p. 137.
  • R. K. Guy, Unsolved Problems in Number Theory, Springer, 1st edition, 1981. See section B36.
  • G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 5th ed., Oxford Univ. Press, 1979, th. 60, 62, 63, 288, 323, 328, 330.
  • Peter Hilton and Jean Pedersen, A Mathematical Tapestry, Demonstrating the Beautiful Unity of Mathematics, Cambridge University Press, pages 261-264, the Coach theorem.
  • Jean-Marie Monier, Analyse, Exercices corrigés, 2ème année MP, Dunod, 1997, Exercice 3.2.21 pp. 281-294.
  • G. Pólya and G. Szegő, Problems and Theorems in Analysis, Springer-Verlag, New York, Heidelberg, Berlin, 2 vols., 1976, Vol. II, problem 71, p. 126.
  • Paulo Ribenboim, The New Book of Prime Number Records.
  • Paulo Ribenboim, The Little Book of Bigger Primes, Springer-Verlag NY 2004. See pp. 28-33.
  • 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).
  • James J. Tattersall, Elementary Number Theory in Nine Chapters, Cambridge University Press, 1999, pages 162-167.

Links

Crossrefs

Cf. A002088 (partial sums), A008683, A003434 (steps to reach 1), A007755, A049108, A002202 (values), A011755 (Sum k*phi(k)).
Cf. also A005277 (nontotient numbers). For inverse see A002181, A006511, A058277.
Jordan function J_k(n) is a generalization - see A059379 and A059380 (triangle of values of J_k(n)), this sequence (J_1), A007434 (J_2), A059376 (J_3), A059377 (J_4), A059378 (J_5).
Cf. A054521, A023022, A054525.
Row sums of triangles A134540, A127448, A143239, A143353 and A143276.
Equals right and left borders of triangle A159937. - Gary W. Adamson, Apr 26 2009
Values for prime powers p^e: A006093 (e=1), A036689 (e=2), A135177 (e=3), A138403 (e=4), A138407 (e=5), A138412 (e=6).
Values for perfect powers n^e: A002618 (e=2), A053191 (e=3), A189393 (e=4), A238533 (e=5), A306411 (e=6), A239442 (e=7), A306412 (e=8), A239443 (e=9).
Cf. A003558, A135303.
Cf. A152455, A080737.
Cf. A076479.
Cf. A023900 (Dirichlet inverse of phi), A306633 (Dgf at s=3).

Programs

  • Axiom
    [eulerPhi(n) for n in 1..100]
  • Haskell
    a n = length (filter (==1) (map (gcd n) [1..n])) -- Allan C. Wechsler, Dec 29 2014
  • Julia
    # Computes the first N terms of the sequence.
function A000010List(N)
    phi = [i for i in 1:N + 1]
    for i in 2:N + 1
        if phi[i] == i
            for j in i:i:N + 1
                phi[j] -= div(phi[j], i)
    end end end
return phi end
println(A000010List(68))  # Peter Luschny, Sep 03 2023
  • Magma
    [ EulerPhi(n) : n in [1..100] ]; // Sergei Haller (sergei(AT)sergei-haller.de), Dec 21 2006
  • Maple
    with(numtheory): A000010 := phi; [ seq(phi(n), n=1..100) ]; # version 1
with(numtheory): phi := proc(n) local i,t1,t2; t1 := ifactors(n)[2]; t2 := n*mul((1-1/t1[i][1]),i=1..nops(t1)); end; # version 2
# Alternative without library function:
A000010List := proc(N) local i, j, phi;
    phi := Array([seq(i, i = 1 .. N+1)]);
    for i from 2 to N + 1 do
        if phi[i] = i then
            for j from i by i to N + 1 do
                phi[j] := phi[j] - iquo(phi[j], i) od
        fi od;
return phi end:
A000010List(68);  # Peter Luschny, Sep 03 2023
  • Mathematica
    Array[EulerPhi, 70]
  • Maxima
    makelist(totient(n),n,0,1000); /* Emanuele Munarini, Mar 26 2011 */
  • PARI
    {a(n) = if( n==0, 0, eulerphi(n))}; /* Michael Somos, Feb 05 2011 */
  • Python
    from sympy.ntheory import totient
print([totient(i) for i in range(1, 70)])  # Indranil Ghosh, Mar 17 2017
  • Python
    # Note also the implementation in A365339.
  • Sage
    def A000010(n): return euler_phi(n) # Jaap Spies, Jan 07 2007
  • Sage
    [euler_phi(n) for n in range(1, 70)]  # Zerinvary Lajos, Jun 06 2009

Formula

phi(n) = n*Product_{distinct primes p dividing n} (1 - 1/p).
Sum_{d divides n} phi(d) = n.
phi(n) = Sum_{d divides n} mu(d)*n/d, i.e., the Moebius transform of the natural numbers; mu() = Moebius function A008683().
Dirichlet generating function Sum_{n>=1} phi(n)/n^s = zeta(s-1)/zeta(s). Also Sum_{n >= 1} phi(n)*x^n/(1 - x^n) = x/(1 - x)^2.
Multiplicative with a(p^e) = (p - 1)*p^(e-1). - David W. Wilson, Aug 01 2001
Sum_{n>=1} (phi(n)*log(1 - x^n)/n) = -x/(1 - x) for -1 < x < 1 (cf. A002088) - Henry Bottomley, Nov 16 2001
a(n) = binomial(n+1, 2) - Sum_{i=1..n-1} a(i)*floor(n/i) (see A000217 for inverse). - Jon Perry, Mar 02 2004
It is a classical result (certainly known to Landau, 1909) that lim inf n/phi(n) = 1 (taking n to be primes), lim sup n/(phi(n)*log(log(n))) = e^gamma, with gamma = Euler's constant (taking n to be products of consecutive primes starting from 2 and applying Mertens' theorem). See e.g. Ribenboim, pp. 319-320. - Pieter Moree, Sep 10 2004
a(n) = Sum_{i=1..n} |k(n, i)| where k(n, i) is the Kronecker symbol. Also a(n) = n - #{1 <= i <= n : k(n, i) = 0}. - Benoit Cloitre, Aug 06 2004 [Corrected by Jianing Song, Sep 25 2018]
Conjecture: Sum_{i>=2} (-1)^i/(i*phi(i)) exists and is approximately 0.558 (A335319). - Orges Leka (oleka(AT)students.uni-mainz.de), Dec 23 2004
From Enrique Pérez Herrero, Sep 07 2010: (Start)
a(n) = Sum_{i=1..n} floor(sigma_k(i*n)/sigma_k(i)*sigma_k(n)), where sigma_2 is A001157.
a(n) = Sum_{i=1..n} floor(tau_k(i*n)/tau_k(i)*tau_k(n)), where tau_3 is A007425.
a(n) = Sum_{i=1..n} floor(rad(i*n)/rad(i)*rad(n)), where rad is A007947. (End)
a(n) = A173557(n)*A003557(n). - R. J. Mathar, Mar 30 2011
a(n) = A096396(n) + A096397(n). - Reinhard Zumkeller, Mar 24 2012
phi(p*n) = phi(n)*(floor(((n + p - 1) mod p)/(p - 1)) + p - 1), for primes p. - Gary Detlefs, Apr 21 2012
For odd n, a(n) = 2*A135303((n-1)/2)*A003558((n-1)/2) or phi(n) = 2*c*k; the Coach theorem of Pedersen et al. Cf. A135303. - Gary W. Adamson, Aug 15 2012
G.f.: Sum_{n>=1} mu(n)*x^n/(1 - x^n)^2, where mu(n) = A008683(n). - Mamuka Jibladze, Apr 05 2015
a(n) = n - cototient(n) = n - A051953(n). - Omar E. Pol, May 14 2016
a(n) = lim_{s->1} n*zeta(s)*(Sum_{d divides n} A008683(d)/(e^(1/d))^(s-1)), for n > 1. - Mats Granvik, Jan 26 2017
Conjecture: a(n) = Sum_{a=1..n} Sum_{b=1..n} Sum_{c=1..n} 1 for n > 1. The sum is over a,b,c such that n*c - a*b = 1. - Benedict W. J. Irwin, Apr 03 2017
a(n) = Sum_{j=1..n} gcd(j, n) cos(2*Pi*j/n) = Sum_{j=1..n} gcd(j, n) exp(2*Pi*i*j/n) where i is the imaginary unit. Notice that the Ramanujan's sum c_n(k) := Sum_{j=1..n, gcd(j, n) = 1} exp(2*Pi*i*j*k/n) gives a(n) = Sum_{k|n} k*c_(n/k)(1) = Sum_{k|n} k*mu(n/k). - Michael Somos, May 13 2018
G.f.: x*d/dx(x*d/dx(log(Product_{k>=1} (1 - x^k)^(-mu(k)/k^2)))), where mu(n) = A008683(n). - Mamuka Jibladze, Sep 20 2018
a(n) = Sum_{d|n} A007431(d). - Steven Foster Clark, May 29 2019
G.f. A(x) satisfies: A(x) = x/(1 - x)^2 - Sum_{k>=2} A(x^k). - Ilya Gutkovskiy, Sep 06 2019
a(n) >= sqrt(n/2) (Nicolas). - Hugo Pfoertner, Jun 01 2020
a(n) > n/(exp(gamma)*log(log(n)) + 5/(2*log(log(n)))), except for n=223092870 (Rosser, Schoenfeld). - Hugo Pfoertner, Jun 02 2020
From Bernard Schott, Nov 28 2020: (Start)
Sum_{m=1..n} 1/a(m) = A028415(n)/A048049(n) -> oo when n->oo.
Sum_{n >= 1} 1/a(n)^2 = A109695.
Sum_{n >= 1} 1/a(n)^3 = A335818.
Sum_{n >= 1} 1/a(n)^k is convergent iff k > 1.
a(2n) = a(n) iff n is odd, and, a(2n) > a(n) iff n is even. (End) [Actually, a(2n) = 2*a(n) for even n. - Jianing Song, Sep 18 2022]
a(n) = 2*A023896(n)/n, n > 1. - Richard R. Forberg, Feb 03 2021
From Richard L. Ollerton, May 09 2021: (Start)
For n > 1, Sum_{k=1..n} phi^{(-1)}(n/gcd(n,k))*a(gcd(n,k))/a(n/gcd(n,k)) = 0, where phi^{(-1)} = A023900.
For n > 1, Sum_{k=1..n} a(gcd(n,k))*mu(rad(gcd(n,k)))*rad(gcd(n,k))/gcd(n,k) = 0.
For n > 1, Sum_{k=1..n} a(gcd(n,k))*mu(rad(n/gcd(n,k)))*rad(n/gcd(n,k))*gcd(n,k) = 0.
Sum_{k=1..n} a(gcd(n,k))/a(n/gcd(n,k)) = n. (End)
a(n) = Sum_{d|n, e|n} gcd(d, e)*mobius(n/d)*mobius(n/e) (the sum is a multiplicative function of n by Tóth, and takes the value p^e - p^(e-1) for n = p^e, a prime power). - Peter Bala, Jan 22 2024
Sum_{n >= 1} phi(n)*x^n/(1 + x^n) = x + 3*x^3 + 5*x^5 + 7*x^7 + ... = Sum_{n >= 1} phi(2*n-1)*x^(2*n-1)/(1 - x^(4*n-2)). For the first equality see Pólya and Szegő, problem 71, p. 126. - Peter Bala, Feb 29 2024
Conjecture: a(n) = lim_{k->oo} (n^(k + 1))/A000203(n^k). - Velin Yanev, Dec 04 2024 [A000010(p) = p-1, A000203(p^k) = (p^(k+1)-1)/(p-1), so the conjecture is true if n is prime. - Vaclav Kotesovec, Dec 19 2024]

A008966 a(n) = 1 if n is squarefree, otherwise 0.

Original entry on oeis.org

1, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0
Offset: 1

Views

Author

N. J. A. Sloane

Keywords

Comments

a(n) depends only on prime signature of n (cf. A025487). So a(24) = a(375) since 24 = 2^3*3 and 375 = 3*5^3 both have prime signature (3, 1).
The infinite lower triangular matrix with A008966 on the main diagonal and the rest zeros is the square of triangle A143255. - Gary W. Adamson, Aug 02 2008

Links

Crossrefs

Cf. A005117, A008836 (Dirichlet inverse), A013928 (partial sums).
Cf. A179211, A179212, A179213, A179214, A179215.
Cf. A020639, A073576, A087188.
Cf. A124010, A212793, A085357, A156552.
Parity of A002033.
Cf. A047999, A036987
Cf. A082020 (Dgf at s=2), A157289 (Dgf at s=3), A157290 (Dgf at s=4).

Programs

  • Haskell
    a008966 = abs . a008683
-- Reinhard Zumkeller, Dec 13 2015, Dec 15 2014, May 27 2012, Jan 25 2012
  • Magma
    [ Abs(MoebiusMu(n)) : n in [1..100]];
  • Maple
    A008966 := proc(n) if numtheory[issqrfree](n) then 1 ; else 0 ; end if; end proc: # R. J. Mathar, Mar 14 2011
  • Mathematica
    A008966[n_] := Abs[MoebiusMu[n]]; Table[A008966[n], {n, 100}] (* Enrique Pérez Herrero, Apr 15 2010 *)
Table[If[SquareFreeQ[n],1,0],{n,100}] (* or *) Boole[SquareFreeQ/@ Range[ 100]] (* Harvey P. Dale, Feb 28 2015 *)
  • MuPAD
    func(abs(numlib::moebius(n)), n):
  • PARI
    a(n)=if(n<1,0,direuler(p=2,n,1+X))[n]
  • PARI
    a(n)=issquarefree(n) \\ Michel Marcus, Feb 22 2015
  • Python
    from sympy import factorint
def A008966(n): return int(max(factorint(n).values(),default=1)==1) # Chai Wah Wu, Apr 05 2023

Formula

Dirichlet g.f.: zeta(s)/zeta(2s).
a(n) = abs(mu(n)), where mu is the Moebius function (A008683).
a(n) = 0^(bigomega(n) - omega(n)), where bigomega(n) and omega(n) are the numbers of prime factors of n with and without repetition (A001222, A001221, A046660). - Reinhard Zumkeller, Apr 05 2003
Multiplicative with p^e -> 0^(e - 1), p prime and e > 0. - Reinhard Zumkeller, Jul 15 2003
a(n) = 0^(A046951(n) - 1). - Reinhard Zumkeller, May 20 2007
a(n) = 1 - A107078(n). - Reinhard Zumkeller, Oct 03 2008
a(n) = floor(rad(n)/n), where rad() is A007947. - Enrique Pérez Herrero, Nov 13 2009
A175046(n) = a(n)*A073311(n). - Reinhard Zumkeller, Apr 05 2010
a(n) = floor(A000005(n^2)/A007425(n)). - Enrique Pérez Herrero, Apr 15 2010
a(A005117(n)) = 1; a(A013929(n)) = 0; a(n) = A013928(n + 1) - A013928(n). - Reinhard Zumkeller, Jul 05 2010
a(n) * A112526(n) = A063524(n). - Reinhard Zumkeller, Sep 16 2011
a(n) = mu(n) * lambda(n) = A008836(n) * A008683(n). - Enrique Pérez Herrero, Nov 29 2013
a(n) = Sum_{d|n} 2^omega(d)*mu(n/d). - Geoffrey Critzer, Feb 22 2015
a(n) = A085357(A156552(n)). - Antti Karttunen, Mar 06 2017
Limit_{n->oo} (1/n)*Sum_{j=1..n} a(j) = 6/Pi^2. - Andres Cicuttin, Aug 13 2017
a(1) = 1; a(n) = -Sum_{d|n, d < n} (-1)^bigomega(n/d) * a(d). - Ilya Gutkovskiy, Mar 10 2021

Extensions

Deleted an unclear comment. - N. J. A. Sloane, May 30 2021

A063834 Twice partitioned numbers: the number of ways a number can be partitioned into not necessarily different parts and each part is again so partitioned.

Original entry on oeis.org

1, 1, 3, 6, 15, 28, 66, 122, 266, 503, 1027, 1913, 3874, 7099, 13799, 25501, 48508, 88295, 165942, 299649, 554545, 997281, 1817984, 3245430, 5875438, 10410768, 18635587, 32885735, 58399350, 102381103, 180634057, 314957425, 551857780, 958031826, 1667918758
Offset: 0

Views

Author

Wouter Meeussen, Aug 21 2001

Keywords

Comments

These are different from plane partitions.
For ordered partitions of partitions see A055887 which may be computed from A036036 and A048996. - Alford Arnold, May 19 2006
Twice partitioned numbers correspond to triangles (or compositions) in the multiorder of integer partitions. - Gus Wiseman, Oct 28 2015

Examples

			G.f. = 1 + x + 3*x^2 + 6*x^3 + 15*x^4 + 28*x^5 + 66*x^6 + 122*x^7 + 266*x^8 + ...
If n=6, a possible first partitioning is (3+3), resulting in the following second partitionings: ((3),(3)), ((3),(2+1)), ((3),(1+1+1)), ((2+1),(3)), ((2+1),(2+1)), ((2+1),(1+1+1)), ((1+1+1),(3)), ((1+1+1),(2+1)), ((1+1+1),(1+1+1)).

Links

Crossrefs

Cf. A063835, A196545.
Cf. A036036, A048996, A055887.
Cf. A006906, A270995.
Cf. A007425, A047966, A047968, A271619, A279375, A279784-A279791.
The strict case is A296122.
Row sums of A321449.
Column k=2 of A323718.
Without singletons we have A327769, A358828, A358829.
For odd lengths we have A358823, A358824.
For distinct lengths we have A358830, A358912.
For strict partitions see A358914, A382524.
A000041 counts integer partitions, strict A000009.
A001970 counts multiset partitions of integer partitions.
Cf. A075900, A358831, A358833, A358906, A358908, A358909.

Programs

  • Maple
    with(combinat):
b:= proc(n, i) option remember; `if`(n=0 or i=1, 1,
      b(n, i-1)+`if`(i>n, 0, numbpart(i)*b(n-i, i)))
    end:
a:= n-> b(n$2):
seq(a(n), n=0..50);  # Alois P. Heinz, Nov 26 2015
  • Mathematica
    Table[Plus @@ Apply[Times, IntegerPartitions[i] /. i_Integer :> PartitionsP[i], 2], {i, 36}]
(* second program: *)
b[n_, i_] := b[n, i] = If[n==0 || i==1, 1, b[n, i-1] + If[i > n, 0, PartitionsP[i]*b[n-i, i]]]; a[n_] := b[n, n]; Table[a[n], {n, 0, 50}] (* Jean-François Alcover, Jan 20 2016, after Alois P. Heinz *)
  • PARI
    {a(n) = if( n<0, 0, polcoeff( 1 / prod(k=1, n, 1 - numbpart(k) * x^k, 1 + x * O(x^n)), n))}; /* Michael Somos, Dec 19 2016 */

Formula

G.f.: 1/Product_{k>0} (1-A000041(k)*x^k). n*a(n) = Sum_{k=1..n} b(k)*a(n-k), a(0) = 1, where b(k) = Sum_{d|k} d*A000041(d)^(k/d) = 1, 5, 10, 29, 36, 110, 106, ... . - Vladeta Jovovic, Jun 19 2003
From Vaclav Kotesovec, Mar 27 2016: (Start)
a(n) ~ c * 5^(n/4), where
c = 96146522937.7161898848278970039269600938032826... if n mod 4 = 0
c = 96146521894.9433858914667933636782092683849082... if n mod 4 = 1
c = 96146522937.2138934755566928890704687838407524... if n mod 4 = 2
c = 96146521894.8218716328341714149619262713426755... if n mod 4 = 3
(End)

Extensions

a(0)=1 prepended by Alois P. Heinz, Nov 26 2015

A074206 Kalmár's [Kalmar's] problem: number of ordered factorizations of n.

Original entry on oeis.org

0, 1, 1, 1, 2, 1, 3, 1, 4, 2, 3, 1, 8, 1, 3, 3, 8, 1, 8, 1, 8, 3, 3, 1, 20, 2, 3, 4, 8, 1, 13, 1, 16, 3, 3, 3, 26, 1, 3, 3, 20, 1, 13, 1, 8, 8, 3, 1, 48, 2, 8, 3, 8, 1, 20, 3, 20, 3, 3, 1, 44, 1, 3, 8, 32, 3, 13, 1, 8, 3, 13, 1, 76, 1, 3, 8, 8, 3, 13, 1, 48, 8, 3, 1, 44, 3, 3, 3, 20, 1, 44, 3, 8, 3, 3, 3, 112
Offset: 0

Views

Author

N. J. A. Sloane, Apr 29 2003

Keywords

Comments

a(0)=0, a(1)=1; thereafter a(n) is the number of ordered factorizations of n as a product of integers greater than 1.
Kalmár (1931) seems to be the earliest reference that mentions this sequence (as opposed to A002033). - N. J. A. Sloane, May 05 2016
a(n) is the permanent of the n-1 X n-1 matrix A with (i,j) entry = 1 if j|i+1 and = 0 otherwise. This is because ordered factorizations correspond to nonzero elementary products in the permanent. For example, with n=6, 3*2 -> 1,3,6 [partial products] -> 6,3,1 [reverse list] -> (6,3)(3,1) [partition into pairs with offset 1] -> (5,3)(2,1) [decrement first entry] -> (5,3)(2,1)(1,2)(3,4)(4,5) [append pairs (i,i+1) to get a permutation] -> elementary product A(1,2)A(2,1)A(3,4)A(4,5)A(5,3). - David Callan, Oct 19 2005
This sequence is important in describing the amount of energy in all wave structures in the Universe according to harmonics theory. - Ray Tomes (ray(AT)tomes.biz), Jul 22 2007
a(n) appears to be the number of permutation matrices contributing to the Moebius function. See A008683 for more information. Also a(n) appears to be the Moebius transform of A067824. Furthermore it appears that except for the first term a(n)=A067824(n)*(1/2). Are there other sequences such that when the Moebius transform is applied, the new sequence is also a constant factor times the starting sequence? - Mats Granvik, Jan 01 2009
Numbers divisible by n distinct primes appear to have ordered factorization values that can be found in an n-dimensional summatory Pascal triangle. For example, the ordered factorization values for numbers divisible by two distinct primes can be found in table A059576. - Mats Granvik, Sep 06 2009
Inverse Mobius transform of A174725 and also except for the first term, inverse Mobius transform of A174726. - Mats Granvik, Mar 28 2010
a(n) is a lower bound on the worst-case number of solutions to the probed partial digest problem for n fragments of DNA; see the Newberg & Naor reference, below. - Lee A. Newberg, Aug 02 2011
All integers greater than 1 are perfect numbers over this sequence (for definition of A-perfect numbers, see comment to A175522). - Vladimir Shevelev, Aug 03 2011
If n is squarefree, then a(n) = A000670(A001221(n)) = A000670(A001222(n)). - Vladimir Shevelev and Franklin T. Adams-Watters, Aug 05 2011
A034776 lists the values taken by this sequence. - Robert G. Wilson v, Jun 02 2012
From Gus Wiseman, Aug 25 2020: (Start)
Also the number of strict chains of divisors from n to 1. For example, the a(n) chains for n = 1, 2, 4, 6, 8, 12, 30 are:
1 2/1 4/1 6/1 8/1 12/1 30/1
4/2/1 6/2/1 8/2/1 12/2/1 30/2/1
6/3/1 8/4/1 12/3/1 30/3/1
8/4/2/1 12/4/1 30/5/1
12/6/1 30/6/1
12/4/2/1 30/10/1
12/6/2/1 30/15/1
12/6/3/1 30/6/2/1
30/6/3/1
30/10/2/1
30/10/5/1
30/15/3/1
30/15/5/1
(End)
a(n) is also the number of ways to tile a strip of length log(n) with tiles having lengths {log(k) : k>=2}. - David Bevan, Jan 07 2025

Examples

			G.f. = x + x^2 + x^3 + 2*x^4 + x^5 + 3*x^6 + x^7 + 4*x^8 + 2*x^9 + 3*x^10 + ...
Number of ordered factorizations of 8 is 4: 8 = 2*4 = 4*2 = 2*2*2.

References

  • L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 126, see #27.
  • R. Honsberger, Mathematical Gems III, M.A.A., 1985, p. 141.
  • Kalmár, Laszlo, A "factorisatio numerorum" problemajarol [Hungarian], Matemat. Fizik. Lapok, 38 (1931), 1-15.
  • J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 124.

Links

Crossrefs

Apart from initial term, same as A002033.
a(A002110) = A000670, row sums of A251683.
A173382 (and A025523) gives partial sums.
Cf. A008683, A050324, A027751, A001221, A034776, A000670, A050369.
A124433 has these as unsigned row sums.
A334996 has these as row sums.
A001055 counts factorizations.
A001222 counts prime factors with multiplicity.
A008480 counts ordered prime factorizations.
A067824 counts strict chains of divisors starting with n.
A122651 counts strict chains of divisors summing to n.
A253249 counts strict chains of divisors.
Cf. A000005, A025487, A046523, A059576, A122408, A124010, A153881 (Dirichlet inverse), A167865, A174725, A174726, A175522, A181819, A320390, A334997, A337105, A361665.

Programs

  • Haskell
    a074206 n | n <= 1 = n
| otherwise = 1 + (sum $ map (a074206 . (div n)) $
tail $ a027751_row n)
-- Reinhard Zumkeller, Oct 01 2012
  • Maple
    a := array(1..150): for k from 1 to 150 do a[k] := 0 od: a[1] := 1: for j from 2 to 150 do for m from 1 to j-1 do if j mod m = 0 then a[j] := a[j]+a[m] fi: od: od: for k from 1 to 150 do printf(`%d,`,a[k]) od: # James Sellers, Dec 07 2000
A074206:= proc(n) option remember; if n > 1 then `+`(op(apply(A074206, numtheory[divisors](n)[1..-2]))) else n fi end: # M. F. Hasler, Oct 12 2018
  • Mathematica
    a[0] = 0; a[1] = 1; a[n_] := a[n] = a /@ Most[Divisors[n]] // Total; a /@ Range[20000] (* N. J. A. Sloane, May 04 2016, based on program in A002033 *)
ccc[n_]:=Switch[n,0,{},1,{{1}},,Join@@Table[Prepend[#,n]&/@ccc[d],{d,Most[Divisors[n]]}]]; Table[Length[ccc[n]],{n,0,100}] (* _Gus Wiseman, Aug 25 2020 *)
  • PARI
    A=vector(100);A[1]=1; for(n=2,#A,A[n]=1+sumdiv(n,d,A[d])); A/=2; A[1]=1; concat(0,A) \\ Charles R Greathouse IV, Nov 20 2012
  • PARI
    {a(n) = if( n<2, n>0, my(A = divisors(n)); sum(k=1, #A-1, a(A[k])))}; /* Michael Somos, Dec 26 2016 */
  • PARI
    A074206(n)=if(n>1, sumdiv(n, i, if(iA074206(i))),n) \\ M. F. Hasler, Oct 12 2018
  • PARI
    A74206=[1]; A074206(n)={if(#A74206A074206(i)))} \\ Use memoization for computing many values. - M. F. Hasler, Oct 12 2018
  • PARI
    first(n) = {my(res = vector(n, i, 1)); for(i = 2, n, for(j = 2, n \ i, res[i*j] += res[i])); concat(0, res)} \\ David A. Corneth, Oct 13 2018
  • PARI
    first(n) = {my(res = vector(n, i, 1)); for(i = 2, n, d = divisors(i); res[i] += sum(j = 1, #d-1, res[d[j]])); concat(0, res)} \\ somewhat faster than progs above for finding first terms of n. \\ David A. Corneth, Oct 12 2018
  • PARI
    a(n)={if(!n, 0, my(sig=factor(n)[,2], m=vecsum(sig)); sum(k=0, m, prod(i=1, #sig, binomial(sig[i]+k-1, k-1))*sum(r=k, m, binomial(r,k)*(-1)^(r-k))))} \\ Andrew Howroyd, Aug 30 2020
  • Python
    from math import prod
from functools import lru_cache
from sympy import divisors, factorint, prime
@lru_cache(maxsize=None)
def A074206(n): return sum(A074206(d) for d in divisors(prod(prime(i+1)**e for i,e in enumerate(sorted(factorint(n).values(),reverse=True))),generator=True,proper=True)) if n > 1 else n # Chai Wah Wu, Sep 16 2022
  • SageMath
    @cached_function
def minus_mu(n):
    if n < 2: return n
    return sum(minus_mu(d) for d in divisors(n)[:-1])
# Note that changing the sign of the sum gives the Möbius function A008683.
print([minus_mu(n) for n in (0..96)]) # Peter Luschny, Dec 26 2016

Formula

With different offset: a(n) = sum of all a(i) such that i divides n and i < n. - Clark Kimberling
a(p^k) = 2^(k-1) if k>0 and p is a prime.
Dirichlet g.f.: 1/(2-zeta(s)). - Herbert S. Wilf, Apr 29 2003
a(n) = A067824(n)/2 for n>1; a(A122408(n)) = A122408(n)/2. - Reinhard Zumkeller, Sep 03 2006
If p,q,r,... are distinct primes, then a(p*q)=3, a(p^2*q)=8, a(p*q*r)=13, a(p^3*q)=20, etc. - Vladimir Shevelev, Aug 03 2011 [corrected by Charles R Greathouse IV, Jun 02 2012]
a(0) = 0, a(1) = 1; a(n) = [x^n] Sum_{k=1..n-1} a(k)*x^k/(1 - x^k). - Ilya Gutkovskiy, Dec 11 2017
a(n) = a(A046523(n)); a(A025487(n)) = A050324(n): a(n) depends only on the nonzero exponents in the prime factorization of n, more precisely prime signature of n, cf. A124010 and A320390. - M. F. Hasler, Oct 12 2018
a(n) = A000670(A001221(n)) for squarefree n. In particular a(A002110(n)) = A000670(n). - Amiram Eldar, May 13 2019
a(n) = A050369(n)/n, for n>=1. - Ridouane Oudra, Aug 31 2019
a(n) = A361665(A181819(n)). - Pontus von Brömssen, Mar 25 2023
From Ridouane Oudra, Nov 02 2023: (Start)
If p,q are distinct primes, and n,m>0 then we have:
a(p^n*q^m) = Sum_{k=0..min(n,m)} 2^(n+m-k-1)*binomial(n,k)*binomial(m,k);
More generally: let tau[k](n) denote the number of ordered factorizations of n as a product of k terms, also named the k-th Piltz function (see A007425), then we have for n>1:
a(n) = Sum_{j=1..bigomega(n)} Sum_{k=1..j} (-1)^(j-k)*binomial(j,k)*tau[k](n), or
a(n) = Sum_{j=1..bigomega(n)} Sum_{k=0..j-1} (-1)^k*binomial(j,k)*tau[j-k](n). (End)

Extensions

Originally this sequence was merged with A002033, the number of perfect partitions. Herbert S. Wilf suggested that it warrants an entry of its own.

A063524 Characteristic function of 1.

Original entry on oeis.org

0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
Offset: 0

Views

Author

Labos Elemer, Jul 30 2001

Keywords

Comments

The identity function for Dirichlet multiplication (see Apostol).
Sum of the Moebius function mu(d) of the divisors d of n. - Robert G. Wilson v, Sep 30 2006
-a(n) is the Hankel transform of A000045(n), n >= 0 (Fibonacci numbers). See A055879 for the definition of Hankel transform. - Wolfdieter Lang, Jan 23 2007
a(A000012(n)) = 1; a(A087156(n)) = 0. - Reinhard Zumkeller, Oct 11 2008
a(n) for n >= 1 is the Dirichlet convolution of following functions b(n), c(n), a(n) = Sum_{d|n} b(d)*c(n/d): a(n) = A008683(n) * A000012(n), a(n) = A007427(n) * A000005(n), a(n) = A007428(n) * A007425(n). - Jaroslav Krizek, Mar 03 2009
From Christopher Hunt Gribble, Jul 11 2013: (Start)
a(n) for 1 <= n <= 4 and conjectured for n > 4 is the number of Hamiltonian circuits in a 2n X 2n square lattice of nodes, reduced for symmetry, where the orbits under the symmetry group of the square, D4, have 1 element: When n=1, there is only 1 Hamiltonian circuit in a 2 X 2 square lattice, as illustrated below. The circuit is the same when rotated and/or reflected and so has only 1 orbital element under the symmetry group of the square.
o--o
| |
o--o (End)
Convolution property: For any sequence b(n), the sequence c(n)=b(n)*a(n) has the following values: c(1)=0, c(n+1)=b(n) for all n > 1. In other words, the sequence b(n) is shifted 1 step to the right. - David Neil McGrath, Nov 10 2014

References

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

Links

Crossrefs

Cf. A000007 (same sequence shifted once left).
Cf. A000005, A000010, A000012, A000027, A003763, A008683, A007427, A007428, A007425, A023900, A055615, A101296, A227005, A227257, A227301, A209077.

Programs

Formula

From Philippe Deléham, Nov 25 2008: (Start)
G.f.: x.
E.g.f.: x. (End)
a(n) = mu(n^2). - Enrique Pérez Herrero, Sep 04 2009
a(n) = floor(n/A000203(n)) for n > 0. - Enrique Pérez Herrero, Nov 11 2009
a(n) = (1-(-1)^(2^abs(n-1)))/2 = (1-(-1)^(2^((n-1)^2)))/2. - Luce ETIENNE, Jun 05 2015
a(n) = n*(A057427(n) - A057427(n-1)) = A000007(abs(n-1)). - Chayim Lowen, Aug 01 2015
a(n) = A010051(p*n) for any prime p (where A010051(0)=0). - Chayim Lowen, Aug 05 2015
From Antti Karttunen, Jun 04 2022: (Start)
For n >= 1:
a(n) = Sum_{d|n} A000010(n/d) * A023900(d), and similarly for any pair of sequences that are Dirichlet inverses of each other, like for example A000027 & A055615 and those mentioned in Krizek's Mar 03 2009 comment above.
a(n) = [A101296(n) == 1], where [ ] is the Iverson bracket.
Fully multiplicative with a(p^e) = 0. (End)

A211422 Number of ordered triples (w,x,y) with all terms in {-n,...,0,...,n} and w^2 + x*y = 0.

Original entry on oeis.org

1, 9, 17, 25, 41, 49, 57, 65, 81, 105, 113, 121, 137, 145, 153, 161, 193, 201, 225, 233, 249, 257, 265, 273, 289, 329, 337, 361, 377, 385, 393, 401, 433, 441, 449, 457, 505, 513, 521, 529, 545, 553, 561, 569, 585, 609, 617, 625, 657, 713, 753, 761
Offset: 0

Views

Author

Clark Kimberling, Apr 10 2012

Keywords

Comments

Suppose that S={-n,...,0,...,n} and that f(w,x,y,n) is a function, where w,x,y are in S. The number of ordered triples (w,x,y) satisfying f(w,x,y,n)=0, regarded as a function of n, is a sequence t of nonnegative integers. Sequences such as t/4 may also be integer sequences for all except certain initial values of n. In the following guide, such sequences are indicated in the related sequences column and may be included in the corresponding Mathematica programs.
...
sequence... f(w,x,y,n) ..... related sequences
A211415 ... w^2+x*y-1 ...... t+2, t/4, (t/4-1)/4
A211422 ... w^2+x*y ........ (t-1)/8, A120486
A211423 ... w^2+2x*y ....... (t-1)/4
A211424 ... w^2+3x*y ....... (t-1)/4
A211425 ... w^2+4x*y ....... (t-1)/4
A211426 ... 2w^2+x*y ....... (t-1)/4
A211427 ... 3w^2+x*y ....... (t-1)/4
A211428 ... 2w^2+3x*y ...... (t-1)/4
A211429 ... w^3+x*y ........ (t-1)/4
A211430 ... w^2+x+y ........ (t-1)/2
A211431 ... w^3+(x+y)^2 .... (t-1)/2
A211432 ... w^2-x^2-y^2 .... (t-1)/8
A003215 ... w+x+y .......... (t-1)/2, A045943
A202253 ... w+2x+3y ........ (t-1)/2, A143978
A211433 ... w+2x+4y ........ (t-1)/2
A211434 ... w+2x+5y ........ (t-1)/4
A211435 ... w+4x+5y ........ (t-1)/2
A211436 ... 2w+3x+4y ....... (t-1)/2
A211435 ... 2w+3x+5y ....... (t-1)/2
A211438 ... w+2x+2y ....... (t-1)/2, A118277
A001844 ... w+x+2y ......... (t-1)/4, A000217
A211439 ... w+3x+3y ........ (t-1)/2
A211440 ... 2w+3x+3y ....... (t-1)/2
A028896 ... w+x+y-1 ........ t/6, A000217
A211441 ... w+x+y-2 ........ t/3, A028387
A182074 ... w^2+x*y-n ...... t/4, A028387
A000384 ... w+x+y-n
A000217 ... w+x+y-2n
A211437 ... w*x*y-n ........ t/4, A007425
A211480 ... w+2x+3y-1
A211481 ... w+2x+3y-n
A211482 ... w*x+w*y+x*y-w*x*y
A211483 ... (n+w)^2-x-y
A182112 ... (n+w)^2-x-y-w
...
For the following sequences, S={1,...,n}, rather than
{-n,...,0,...n}. If f(w,x,y,n) is linear in w,x,y,n, then the sequence is a linear recurrence sequence.
A132188 ... w^2-x*y
A211506 ... w^2-x*y-n
A211507 ... w^2-x*y+n
A211508 ... w^2+x*y-n
A211509 ... w^2+x*y-2n
A211510 ... w^2-x*y+2n
A211511 ... w^2-2x*y ....... t/2
A211512 ... w^2-3x*y ....... t/2
A211513 ... 2w^2-x*y ....... t/2
A211514 ... 3w^2-x*y ....... t/2
A211515 ... w^3-x*y
A211516 ... w^2-x-y
A211517 ... w^3-(x+y)^2
A063468 ... w^2-x^2-y^2 .... t/2
A000217 ... w+x-y
A001399 ... w-2x-3y
A211519 ... w-2x+3y
A008810 ... w+2x-3y
A001399 ... w-2x-3y
A008642 ... w-2x-4y
A211520 ... w-2x+4y
A211521 ... w+2x-4y
A000115 ... w-2x-5y
A211522 ... w-2x+5y
A211523 ... w+2x-5y
A211524 ... w-3x-5y
A211533 ... w-3x+5y
A211523 ... w+3x-5y
A211535 ... w-4x-5y
A211536 ... w-4x+5y
A008812 ... w+4x-5y
A055998 ... w+x+y-2n
A074148 ... 2w+x+y-2n
A211538 ... 2w+2x+y-2n
A211539 ... 2w+2x-y-2n
A211540 ... 2w-3x-4y
A211541 ... 2w-3x+4y
A211542 ... 2w+3x-4y
A211543 ... 2w-3x-5y
A211544 ... 2w-3x+5y
A008812 ... 2w+3x-5y
A008805 ... w-2x-2y (repeated triangular numbers)
A001318 ... w-2x+2y
A000982 ... w+x-2y
A211534 ... w-3x-3y
A211546 ... w-3x+3y (triply repeated triangular numbers)
A211547 ... 2w-3x-3y (triply repeated squares)
A082667 ... 2w-3x+3y
A055998 ... w-x-y+2
A001399 ... w-2x-3y+1
A108579 ... w-2x-3y+n
...
Next, S={-n,...-1,1,...,n}, and the sequence counts the cases (w,x,y) satisfying the indicated inequality. If f(w,x,y,n) is linear in w,x,y,n, then the sequence is a linear recurrence sequence.
A211545 ... w+x+y>0; recurrence degree: 4
A211612 ... w+x+y>=0
A211613 ... w+x+y>1
A211614 ... w+x+y>2
A211615 ... |w+x+y|<=1
A211616 ... |w+x+y|<=2
A211617 ... 2w+x+y>0; recurrence degree: 5
A211618 ... 2w+x+y>1
A211619 ... 2w+x+y>2
A211620 ... |2w+x+y|<=1
A211621 ... w+2x+3y>0
A211622 ... w+2x+3y>1
A211623 ... |w+2x+3y|<=1
A211624 ... w+2x+2y>0; recurrence degree: 6
A211625 ... w+3x+3y>0; recurrence degree: 8
A211626 ... w+4x+4y>0; recurrence degree: 10
A211627 ... w+5x+5y>0; recurrence degree: 12
A211628 ... 3w+x+y>0; recurrence degree: 6
A211629 ... 4w+x+y>0; recurrence degree: 7
A211630 ... 5w+x+y>0; recurrence degree: 8
A211631 ... w^2>x^2+y^2; all terms divisible by 8
A211632 ... 2w^2>x^2+y^2; all terms divisible by 8
A211633 ... w^2>2x^2+2y^2; all terms divisible by 8
...
Next, S={1,...,n}, and the sequence counts the cases (w,x,y) satisfying the indicated relation.
A211634 ... w^2<=x^2+y^2
A211635 ... w^2A211790
A211636 ... w^2>=x^2+y^2
A211637 ... w^2>x^2+y^2
A211638 ... w^2+x^2+y^2
A211639 ... w^2+x^2+y^2<=n
A211640 ... w^2+x^2+y^2>n
A211641 ... w^2+x^2+y^2>=n
A211642 ... w^2+x^2+y^2<2n
A211643 ... w^2+x^2+y^2<=2n
A211644 ... w^2+x^2+y^2>2n
A211645 ... w^2+x^2+y^2>=2n
A211646 ... w^2+x^2+y^2<3n
A211647 ... w^2+x^2+y^2<=3n
A063691 ... w^2+x^2+y^2=n
A211649 ... w^2+x^2+y^2=2n
A211648 ... w^2+x^2+y^2=3n
A211650 ... w^3A211790
A211651 ... w^3>x^3+y^3; see Comments at A211790
A211652 ... w^4A211790
A211653 ... w^4>x^4+y^4; see Comments at A211790

Examples

			a(1) counts these 9 triples: (-1,-1,1), (-1, 1,-1), (0, -1, 0), (0, 0, -1), (0,0,0), (0,0,1), (0,1,0), (1,-1,1), (1,1,-1).

Links

Crossrefs

Cf. A120486.

Programs

  • Mathematica
    t[n_] := t[n] = Flatten[Table[w^2 + x*y, {w, -n, n}, {x, -n, n}, {y, -n, n}]]
c[n_] := Count[t[n], 0]
t = Table[c[n], {n, 0, 70}] (* A211422 *)
(t - 1)/8                   (* A120486 *)

A007426 d_4(n), or tau_4(n), the number of ordered factorizations of n as n = rstu.

Original entry on oeis.org

1, 4, 4, 10, 4, 16, 4, 20, 10, 16, 4, 40, 4, 16, 16, 35, 4, 40, 4, 40, 16, 16, 4, 80, 10, 16, 20, 40, 4, 64, 4, 56, 16, 16, 16, 100, 4, 16, 16, 80, 4, 64, 4, 40, 40, 16, 4, 140, 10, 40, 16, 40, 4, 80, 16, 80, 16, 16, 4, 160, 4, 16, 40, 84, 16, 64, 4, 40, 16, 64, 4, 200, 4, 16, 40, 40, 16
Offset: 1

Views

Author

N. J. A. Sloane

Keywords

Comments

Inverse Möbius transform applied thrice to all 1's sequence; or, Dirichlet convolution of d(n) (A000005).
Let n = Product p_i^e_i. tau (A000005) is tau_2, A007425 is tau_3, this sequence is tau_4, where tau_k(n) (also written as d_k(n)) = Product_i binomial(k-1+e_i, k-1) is the k-th Piltz function. It gives the number of ordered factorizations of n as a product of k terms.
Appears to equal the number of solid partitions of n that can be extended in exactly 4 ways to a solid partition of n + 1 by adding one element. - Wouter Meeussen, Sep 11 2004
Equals row sums of A127172. - Gary W. Adamson, Nov 05 2007

References

  • A. Ivic, The Riemann Zeta-Function, Wiley, NY, 1985, see p. xv.
  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Crossrefs

Cf. A007425.
Cf. A127172, A051731, A061202 (partial sums).
Column k=4 of A077592.

Programs

  • Maple
    A007426 := proc(n) local e,j; e := ifactors(n)[2]: product(binomial(3+e[j][2],3), j=1..nops(e)); end;
  • Mathematica
    tau[n_, 1] = 1; tau[n_, k_] := tau[n, k] = Plus @@ (tau[ #, k - 1] & /@ Divisors[n]); Table[ tau[n, 4], {n, 77}] (* Robert G. Wilson v, Nov 02 2005 *)
a[n_] := DivisorSum[n, DivisorSigma[0, n/#]*DivisorSigma[0, #]&]; Array[a, 80] (* Jean-François Alcover, Dec 01 2015 *)
tau[1, k_] := 1; tau[n_, k_] := Times @@ (Binomial[Last[#]+k-1, k-1]& /@ FactorInteger[n]); Table[tau[n, 4], {n, 1, 100}] (* Amiram Eldar, Sep 13 2020 *)
  • PARI
    for(n=1,100,print1(sumdiv(n,k,sumdiv(k,x,numdiv(x))),","))
  • PARI
    a(n)=sumdiv(n,d,numdiv(n/d)*numdiv(d))
  • PARI
    a(n, f=factor(n))=f=f[, 2]; prod(i=1, #f, binomial(f[i]+3, 3)) \\ Charles R Greathouse IV, Oct 28 2017
  • PARI
    for(n=1, 100, print1(numerator(direuler(p=2, n, 1/(1-X)^4)[n]), ", ")) \\ Vaclav Kotesovec, May 06 2025
  • Python
    from math import prod, comb
from sympy import factorint
def A007426(n): return prod(comb(3+e,3) for e in factorint(n).values()) # Chai Wah Wu, Dec 22 2024

Formula

a(n) = Sum_{d dividing n} tau(d)*tau(n/d). - Benoit Cloitre, May 12 2003
Dirichlet g.f.: zeta^4(x).
G.f.: Sum_{k>=1} tau_3(k)*x^k/(1 - x^k). - Ilya Gutkovskiy, Oct 30 2018

Extensions

More terms from Robert G. Wilson v, Nov 02 2005

A034836 Number of ways to write n as n = x*y*z with 1 <= x <= y <= z.

Original entry on oeis.org

1, 1, 1, 2, 1, 2, 1, 3, 2, 2, 1, 4, 1, 2, 2, 4, 1, 4, 1, 4, 2, 2, 1, 6, 2, 2, 3, 4, 1, 5, 1, 5, 2, 2, 2, 8, 1, 2, 2, 6, 1, 5, 1, 4, 4, 2, 1, 9, 2, 4, 2, 4, 1, 6, 2, 6, 2, 2, 1, 10, 1, 2, 4, 7, 2, 5, 1, 4, 2, 5, 1, 12, 1, 2, 4, 4, 2, 5, 1, 9, 4, 2, 1, 10, 2, 2, 2, 6, 1, 10, 2, 4, 2, 2, 2, 12, 1, 4, 4, 8
Offset: 1

Views

Author

Erich Friedman

Keywords

Comments

Number of boxes with integer edge lengths and volume n.
Starts the same as, but is different from, A033273. First values of n such that a(n) differs from A033273(n) are 36,48,60,64,72,80,84,90,96,100. - Benoit Cloitre, Nov 25 2002
a(n) depends only on the signature of n; the sorted exponents of n. For instance, a(12) and a(18) are the same because both 12 and 18 have signature (1,2). - T. D. Noe, Nov 02 2011
Number of 3D grids of n congruent cubes, in a box, modulo rotation (cf. A007425 and A140773 for boxes instead of cubes; cf. A038548 for the 2D case). - Manfred Boergens, Apr 06 2021

Examples

			a(12) = 4 because we can write 12 = 1*1*12 = 1*2*6 = 1*3*4 = 2*2*3.
a(36) = 8 because we can write 36 = 1*1*36 = 1*2*18 = 1*3*12 = 1*4*9 = 1*6*6 = 2*2*9 = 2*3*6 = 3*3*4.
For n = p*q, p < q primes: a(n) = 2 because we can write n = 1*1*pq = 1*p*q.
For n = p^2, p prime: a(n) = 2 because we can write n = 1*1*p^2 = 1*p*p.

Links

Crossrefs

See also: writing n = x*y (A038548, unordered, A000005, ordered), n = x*y*z (this sequence, unordered, A007425, ordered), n = w*x*y*z (A007426, ordered)
Cf. A001358, A008578, A010057, A046951, A088432, A088433, A088434.
Differs from A033273 and A226378 for the first time at n=36.

Programs

  • Maple
    f:=proc(n) local t1,i,j,k; t1:=0; for i from 1 to n do for j from i to n do for k from j to n do if i*j*k = n then t1:=t1+1; fi; od: od: od: t1; end;
# second Maple program:
A034836:=proc(n)
   local a,b,i;
   a:=0;
   b:=(l,x,h)->l<=x and x<=h;
   for i in select(`<=`,NumberTheory:-Divisors(n),iroot(n,3)) do
      a:=a+nops(select[2](b,i,NumberTheory:-Divisors(n/i),isqrt(n/i)))
   od;
   return a
end proc;
seq(A034836(n),n=1..100); # Felix Huber, Oct 02 2024
  • Mathematica
    Table[c=0; Do[If[i<=j<=k && i*j*k==n,c++],{i,t=Divisors[n]},{j,t},{k,t}]; c,{n,100}] (* Jayanta Basu, May 23 2013 *)
(* Similar to the first Mathematica code but with fewer steps in Do[..] *)
b=0; d=Divisors[n]; r=Length[d];
Do[If[d[[h]] d[[i]] d[[j]]==n, b++], {h, r}, {i, h, r}, {j, i, r}]; b (* Manfred Boergens, Apr 06 2021 *)
a[1] = 1; a[n_] := Module[{e = FactorInteger[n][[;; , 2]]}, If[IntegerQ[Surd[n, 3]], 1/3, 0] + (Times @@ ((e + 1)*(e + 2)/2))/6 + (Times @@ (Floor[e/2] + 1))/2]; Array[a, 100] (* Amiram Eldar, Apr 19 2024 *)
  • PARI
    A038548(n)=sumdiv(n, d, d*d<=n) /* <== rhs from A038548 (Michael Somos) */
a(n)=sumdiv(n, d, if(d^3<=n, A038548(n/d) - sumdiv(n/d, d0, d0Rick L. Shepherd, Aug 27 2006
  • PARI
    a(n) = {my(e = factor(n)[,2]); (2 * ispower(n, 3) + vecprod(apply(x -> (x+1)*(x+2)/2, e)) + 3 * vecprod(apply(x -> x\2 + 1, e))) / 6;} \\ Amiram Eldar, Apr 19 2024

Formula

From Ton Biegstraaten, Jan 04 2016: (Start)
Given a number n, let s(1),...,s(m) be the signature list of n, and a(n) the resulting number in the sequence.
Then np = Product_{k=1..m} binomial(2+s(k),2) is the total number of products solely based on the combination of exponents. The multiplicity of powers is not taken into account (e.g., all combinations of 1,2,4 (6 times) but (2,2,2) only once). See next formulas to compute corrections for 3rd and 2nd powers.
Let ntp = Product_{k=1..m} (floor((s(k) - s(k) mod(3))/s(k))) if the number is a 3rd power or not resulting in 1 or 0.
Let nsq = Product_{k=1..m} (floor(s(k)/2) + 1) is the number of squares.
Conjecture: a(n) = (np + 3*(nsq - ntp) + 5*ntp)/6 = (np + 3*nsq + 2*ntp)/6.
Example: n = 1728; s = [3,6]; np = 10*28 = 280; nsq = 2*4 = 8; ntp = 1 so a(1728)=51 (as in the b-file).
(End)
a(n) >= A226378(n) for all n >= 1. - Antti Karttunen, Aug 30 2017
From Bernard Schott, Dec 12 2021: (Start)
a(n) = 1 iff n = 1 or n is prime (A008578).
a(n) = 2 iff n is semiprime (A001358) (see examples). (End)
a(n) = (2 * A010057(n) + A007425(n) + 3 * A046951(n))/6 (Andrica and Ionascu, 2013, p. 19, eq. 11). - Amiram Eldar, Apr 19 2024

Extensions

Definition simplified by Jonathan Sondow, Oct 03 2013

A334996 Irregular triangle read by rows: T(n, m) is the number of ways to distribute Omega(n) objects into precisely m distinct boxes, with no box empty (Omega(n) >= m).

Original entry on oeis.org

0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 2, 0, 1, 0, 1, 2, 1, 0, 1, 1, 0, 1, 2, 0, 1, 0, 1, 4, 3, 0, 1, 0, 1, 2, 0, 1, 2, 0, 1, 3, 3, 1, 0, 1, 0, 1, 4, 3, 0, 1, 0, 1, 4, 3, 0, 1, 2, 0, 1, 2, 0, 1, 0, 1, 6, 9, 4, 0, 1, 1, 0, 1, 2, 0, 1, 2, 1, 0, 1, 4, 3, 0, 1, 0, 1, 6, 6
Offset: 1

Views

Author

Stefano Spezia, May 19 2020

Keywords

Comments

n is the specification number for a set of Omega(n) objects (see Theorem 3 in Beekman's article).
The specification number of a multiset is also called its Heinz number. - Gus Wiseman, Aug 25 2020
From Gus Wiseman, Aug 25 2020: (Start)
For n > 1, T(n,k) is also the number of ordered factorizations of n into k factors > 1. For example, row n = 24 counts the following ordered factorizations (the first column is empty):
24 3*8 2*2*6 2*2*2*3
4*6 2*3*4 2*2*3*2
6*4 2*4*3 2*3*2*2
8*3 2*6*2 3*2*2*2
12*2 3*2*4
2*12 3*4*2
4*2*3
4*3*2
6*2*2
For n > 1, T(n,k) is also the number of strict length-k chains of divisors from n to 1. For example, row n = 36 counts the following chains (the first column is empty):
36/1 36/2/1 36/4/2/1 36/12/4/2/1
36/3/1 36/6/2/1 36/12/6/2/1
36/4/1 36/6/3/1 36/12/6/3/1
36/6/1 36/9/3/1 36/18/6/2/1
36/9/1 36/12/2/1 36/18/6/3/1
36/12/1 36/12/3/1 36/18/9/3/1
36/18/1 36/12/4/1
36/12/6/1
36/18/2/1
36/18/3/1
36/18/6/1
36/18/9/1
(End)

Examples

			The triangle T(n, m) begins
  n\m| 0     1     2     3     4
  ---+--------------------------
   1 | 0
   2 | 0     1
   3 | 0     1
   4 | 0     1     1
   5 | 0     1
   6 | 0     1     2
   7 | 0     1
   8 | 0     1     2     1
   9 | 0     1     1
  10 | 0     1     2
  11 | 0     1
  12 | 0     1     4     3
  13 | 0     1
  14 | 0     1     2
  15 | 0     1     2
  16 | 0     1     3     3     1
  ...
From _Gus Wiseman_, Aug 25 2020: (Start)
Row n = 36 counts the following distributions of {1,1,2,2} (the first column is empty):
  {1122}  {1}{122}  {1}{1}{22}  {1}{1}{2}{2}
          {11}{22}  {1}{12}{2}  {1}{2}{1}{2}
          {112}{2}  {11}{2}{2}  {1}{2}{2}{1}
          {12}{12}  {1}{2}{12}  {2}{1}{1}{2}
          {122}{1}  {12}{1}{2}  {2}{1}{2}{1}
          {2}{112}  {1}{22}{1}  {2}{2}{1}{1}
          {22}{11}  {12}{2}{1}
                    {2}{1}{12}
                    {2}{11}{2}
                    {2}{12}{1}
                    {2}{2}{11}
                    {22}{1}{1}
(End)

References

  • Richard Beekman, An Introduction to Number-Theoretic Combinatorics, Lulu Press 2017.

Links

Crossrefs

Cf. A000007 (1st column), A000012 (2nd column), A001222 (Omega function), A002033 (row sums shifted left), A007318.
A008480 gives rows ends.
A073093 gives row lengths.
A074206 gives row sums.
A112798 constructs the multiset with each specification number.
A124433 is a signed version.
A251683 is the version with zeros removed.
A334997 is the non-strict version.
A337107 is the restriction to factorial numbers.
A001055 counts factorizations.
A067824 counts strict chains of divisors starting with n.
A122651 counts strict chains of divisors summing to n.
A167865 counts strict chains of divisors > 1 summing to n.
A253249 counts strict chains of divisors.
A337105 counts strict chains of divisors from n! to 1.
Cf. A007425, A008683, A056239, A124010, A167865, A317144, A319001.

Programs

  • Mathematica
    tau[n_,k_]:=If[n==1,1,Product[Binomial[Extract[Extract[FactorInteger[n],i],2]+k,k],{i,1,Length[FactorInteger[n]]}]]; (* A334997 *)
T[n_,m_]:=Sum[(-1)^k*Binomial[m,k]*tau[n,m-k-1],{k,0,m-1}]; Table[T[n,m],{n,1,30},{m,0,PrimeOmega[n]}]//Flatten
(* second program *)
chc[n_]:=If[n==1,{{}},Prepend[Join@@Table[Prepend[#,n]&/@chc[d],{d,DeleteCases[Divisors[n],1|n]}],{n}]]; (* change {{}} to {} if a(1) = 0 *)
Table[Length[Select[chc[n],Length[#]==k&]],{n,30},{k,0,PrimeOmega[n]}] (* Gus Wiseman, Aug 25 2020 *)
  • PARI
    TT(n, k) = if (k==0, 1, sumdiv(n, d, TT(d, k-1))); \\ A334997
T(n, m) = sum(k=0, m-1, (-1)^k*binomial(m, k)*TT(n, m-k-1));
tabf(nn) = {for (n=1, nn, print(vector(bigomega(n)+1, k, T(n, k-1))););} \\ Michel Marcus, May 20 2020

Formula

T(n, m) = Sum_{k=0..m-1} (-1)^k*binomial(m,k)*tau_{m-k-1}(n), where tau_s(r) = A334997(r, s) (see Theorem 3, Lemma 1 and Lemma 2 in Beekman's article).
Conjecture: Sum_{m=0..Omega(n)} T(n, m) = A002033(n-1) for n > 1.
The above conjecture is true since T(n, m) is also the number of ordered factorizations of n into m factors (see Comments) and A002033(n-1) is the number of ordered factorizations of n. - Stefano Spezia, Aug 21 2025
Previous Showing 21-30 of 146 results. Next

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

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