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.

Showing 1-10 of 132 results. Next

A137173 A006516 at positions with even indices, A007582 at positions with odd indices.

Original entry on oeis.org

0, 1, 1, 3, 6, 10, 28, 36, 120, 136, 496, 528, 2016, 2080, 8128, 8256, 32640, 32896, 130816, 131328, 523776, 524800, 2096128, 2098176, 8386560, 8390656, 33550336, 33558528, 134209536, 134225920, 536854528, 536887296, 2147450880, 2147516416
Offset: 0

Views

Author

Paul Curtz, May 11 2008

Keywords

Formula

a(2n)=A006516(n). a(2n+1)=A007582(n).
a(2n)+a(2n+1) = A000302(n). a(2n+1)-a(2n)=A000079(n).
G.f.: -x*(-1-x+3*x^2) / ( (2*x+1)*(2*x-1)*(2*x^2-1) ). - R. J. Mathar, Nov 22 2018

Extensions

Edited by R. J. Mathar, Jul 16 2008

A007318 Pascal's triangle read by rows: C(n,k) = binomial(n,k) = n!/(k!*(n-k)!), 0 <= k <= n.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 6, 4, 1, 1, 5, 10, 10, 5, 1, 1, 6, 15, 20, 15, 6, 1, 1, 7, 21, 35, 35, 21, 7, 1, 1, 8, 28, 56, 70, 56, 28, 8, 1, 1, 9, 36, 84, 126, 126, 84, 36, 9, 1, 1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1, 1, 11, 55, 165, 330, 462, 462, 330, 165, 55, 11, 1
Offset: 0

Views

Author

N. J. A. Sloane and Mira Bernstein, Apr 28 1994

Keywords

Comments

A. W. F. Edwards writes: "It [the triangle] was first written down long before 1654, the year in which Blaise Pascal wrote his Traité du triangle arithmétique, but it was this work that brought together all the different aspects of the numbers for the first time. In it Pascal developed the properties of the number as a piece of pure mathematics ... and then, in a series of appendices, showed how these properties were relevant to the study of the figurate numbers, to the theory of combinations, to the expansion of binomial expressions, and to the solution of an important problem in the theory of probability." (A. W. F. Edwards, Pascal's Arithmetical Triangle, Johns Hopkins University Press (2002), p. xiii)
Edwards reports that the naming of the triangle after Pascal was done first by Montmort in 1708 as the "Table de M. Pascal pour les combinaisons" and then by De Moivre in 1730 as the "Triangulum Arithmeticum PASCALANIUM". (Edwards, p. xiv)
In China, Yang Hui in 1261 listed the coefficients of (a+b)^n up to n=6, crediting the expansion to Chia Hsein's Shih-so suan-shu circa 1100. Another prominent early use was in Chu Shih-Chieh's Precious Mirror of the Four Elements in 1303. (Edwards, p. 51)
In Persia, Al-Karaji discovered the binomial triangle "some time soon after 1007", and Al-Samawal published it in the Al-bahir some time before 1180. (Edwards, p. 52)
In India, Halayuda's commentary (circa 900) on Pingala's treatise on syllabic combinations (circa 200 B.C.E.) contains a clear description of the additive computation of the triangle. (Amulya Kumar Bag, Binomial Theorem in Ancient India, p. 72)
Also in India, the multiplicative formula for C(n,k) was known to Mahavira in 850 and restated by Bhaskara in 1150. (Edwards, p. 27)
In Italy, Tartaglia published the triangle in his General trattato (1556), and Cardano published it in his Opus novum (1570). (Edwards, p. 39, 44) - Russ Cox, Mar 29 2022
Also sometimes called Omar Khayyam's triangle.
Also sometimes called Yang Hui's triangle.
C(n,k) = number of k-element subsets of an n-element set.
Row n gives coefficients in expansion of (1+x)^n.
Binomial(n+k-1,n-1) is the number of ways of placing k indistinguishable balls into n boxes (the "bars and stars" argument - see Feller).
Binomial(n-1,k-1) is the number of compositions (ordered partitions) of n with k summands.
Binomial(n+k-1,k-1) is the number of weak compositions (ordered weak partitions) of n into exactly k summands. - Juergen Will, Jan 23 2016
Binomial(n,k) is the number of lattice paths from (0,0) to (n,k) using steps (1,0) and (1,1). - Joerg Arndt, Jul 01 2011
If thought of as an infinite lower triangular matrix, inverse begins:
+1
-1 +1
+1 -2 +1
-1 +3 -3 +1
+1 -4 +6 -4 +1
All 2^n palindromic binomial coefficients starting after the A006516(n)-th entry are odd. - Lekraj Beedassy, May 20 2003
Binomial(n+k-1,n-1) is the number of standard tableaux of shape (n,1^k). - Emeric Deutsch, May 13 2004
Can be viewed as an array, read by antidiagonals, where the entries in the first row and column are all 1's and A(i,j) = A(i-1,j) + A(i,j-1) for all other entries. The determinant of each of its n X n subarrays starting at (0,0) is 1. - Gerald McGarvey, Aug 17 2004
Also the lower triangular readout of the exponential of a matrix whose entry {j+1,j} equals j+1 (and all other entries are zero). - Joseph Biberstine (jrbibers(AT)indiana.edu), May 26 2006
Binomial(n-3,k-1) counts the permutations in S_n which have zero occurrences of the pattern 231 and one occurrence of the pattern 132 and k descents. Binomial(n-3,k-1) also counts the permutations in S_n which have zero occurrences of the pattern 231 and one occurrence of the pattern 213 and k descents. - David Hoek (david.hok(AT)telia.com), Feb 28 2007
Inverse of A130595 (as an infinite lower triangular matrix). - Philippe Deléham, Aug 21 2007
Consider integer lists LL of lists L of the form LL = [m#L] = [m#[k#2]] (where '#' means 'times') like LL(m=3,k=3) = [[2,2,2],[2,2,2],[2,2,2]]. The number of the integer list partitions of LL(m,k) is equal to binomial(m+k,k) if multiple partitions like [[1,1],[2],[2]] and [[2],[2],[1,1]] and [[2],[1,1],[2]] are counted only once. For the example, we find 4*5*6/3! = 20 = binomial(6,3). - Thomas Wieder, Oct 03 2007
The infinitesimal generator for Pascal's triangle and its inverse is A132440. - Tom Copeland, Nov 15 2007
Row n>=2 gives the number of k-digit (k>0) base n numbers with strictly decreasing digits; e.g., row 10 for A009995. Similarly, row n-1>=2 gives the number of k-digit (k>1) base n numbers with strictly increasing digits; see A009993 and compare A118629. - Rick L. Shepherd, Nov 25 2007
From Lee Naish (lee(AT)cs.mu.oz.au), Mar 07 2008: (Start)
Binomial(n+k-1, k) is the number of ways a sequence of length k can be partitioned into n subsequences (see the Naish link).
Binomial(n+k-1, k) is also the number of n- (or fewer) digit numbers written in radix at least k whose digits sum to k. For example, in decimal, there are binomial(3+3-1,3)=10 3-digit numbers whose digits sum to 3 (see A052217) and also binomial(4+2-1,2)=10 4-digit numbers whose digits sum to 2 (see A052216). This relationship can be used to generate the numbers of sequences A052216 to A052224 (and further sequences using radix greater than 10). (End)
From Milan Janjic, May 07 2008: (Start)
Denote by sigma_k(x_1,x_2,...,x_n) the elementary symmetric polynomials. Then:
Binomial(2n+1,2k+1) = sigma_{n-k}(x_1,x_2,...,x_n), where x_i = tan^2(i*Pi/(2n+1)), (i=1,2,...,n).
Binomial(2n,2k+1) = 2n*sigma_{n-1-k}(x_1,x_2,...,x_{n-1}), where x_i = tan^2(i*Pi/(2n)), (i=1,2,...,n-1).
Binomial(2n,2k) = sigma_{n-k}(x_1,x_2,...,x_n), where x_i = tan^2((2i-1)Pi/(4n)), (i=1,2,...,n).
Binomial(2n+1,2k) = (2n+1)sigma_{n-k}(x_1,x_2,...,x_n), where x_i = tan^2((2i-1)Pi/(4n+2)), (i=1,2,...,n). (End)
Given matrices R and S with R(n,k) = binomial(n,k)*r(n-k) and S(n,k) = binomial(n,k)*s(n-k), then R*S = T where T(n,k) = binomial(n,k)*[r(.)+s(.)]^(n-k), umbrally. And, the e.g.f.s for the row polynomials of R, S and T are, respectively, exp(x*t)*exp[r(.)*x], exp(x*t)*exp[s(.)*x] and exp(x*t)*exp[r(.)*x]*exp[s(.)*x] = exp{[t+r(.)+s(.)]*x}. The row polynomials are essentially Appell polynomials. See A132382 for an example. - Tom Copeland, Aug 21 2008
As the rectangle R(m,n) = binomial(m+n-2,m-1), the weight array W (defined generally at A144112) of R is essentially R itself, in the sense that if row 1 and column 1 of W=A144225 are deleted, the remaining array is R. - Clark Kimberling, Sep 15 2008
If A007318 = M as an infinite lower triangular matrix, M^n gives A130595, A023531, A007318, A038207, A027465, A038231, A038243, A038255, A027466, A038279, A038291, A038303, A038315, A038327, A133371, A147716, A027467 for n=-1,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15 respectively. - Philippe Deléham, Nov 11 2008
The coefficients of the polynomials with e.g.f. exp(x*t)*(cosh(t)+sinh(t)). - Peter Luschny, Jul 09 2009
The triangle or chess sums, see A180662 for their definitions, link Pascal's triangle with twenty different sequences, see the crossrefs. All sums come in pairs due to the symmetrical nature of this triangle. The knight sums Kn14 - Kn110 have been added. It is remarkable that all knight sums are related to the Fibonacci numbers, i.e., A000045, but none of the others. - Johannes W. Meijer, Sep 22 2010
Binomial(n,k) is also the number of ways to distribute n+1 balls into k+1 urns so that each urn gets at least one ball. See example in the example section below. - Dennis P. Walsh, Jan 29 2011
Binomial(n,k) is the number of increasing functions from {1,...,k} to {1,...,n} since there are binomial(n,k) ways to choose the k distinct, ordered elements of the range from the codomain {1,...,n}. See example in the example section below. - Dennis P. Walsh, Apr 07 2011
Central binomial coefficients: T(2*n,n) = A000984(n), T(n, floor(n/2)) = A001405(n). - Reinhard Zumkeller, Nov 09 2011
Binomial(n,k) is the number of subsets of {1,...,n+1} with k+1 as median element. To see this, note that Sum_{j=0..min(k,n-k)}binomial(k,j)*binomial(n-k,j) = binomial(n,k). See example in Example section below. - Dennis P. Walsh, Dec 15 2011
This is the coordinator triangle for the lattice Z^n, see Conway-Sloane, 1997. - N. J. A. Sloane, Jan 17 2012
One of three infinite families of integral factorial ratio sequences of height 1 (see Bober, Theorem 1.2). The other two are A046521 and A068555. For real r >= 0, C_r(n,k) := floor(r*n)!/(floor(r*k)!*floor(r*(n-k))!) is integral. See A211226 for the case r = 1/2. - Peter Bala, Apr 10 2012
Define a finite triangle T(m,k) with n rows such that T(m,0) = 1 is the left column, T(m,m) = binomial(n-1,m) is the right column, and the other entries are T(m,k) = T(m-1,k-1) + T(m-1,k) as in Pascal's triangle. The sum of all entries in T (there are A000217(n) elements) is 3^(n-1). - J. M. Bergot, Oct 01 2012
The lower triangular Pascal matrix serves as a representation of the operator exp(RLR) in a basis composed of a sequence of polynomials p_n(x) characterized by ladder operators defined by R p_n(x) = p_(n+1)(x) and L p_n(x) = n p_(n-1)(x). See A132440, A218272, A218234, A097805, and A038207. The transposed and padded Pascal matrices can be associated to the special linear group SL2. - Tom Copeland, Oct 25 2012
See A193242. - Alexander R. Povolotsky, Feb 05 2013
A permutation p_1...p_n of the set {1,...,n} has a descent at position i if p_i > p_(i+1). Let S(n) denote the subset of permutations p_1...p_n of {1,...,n} such that p_(i+1) - p_i <= 1 for i = 1,...,n-1. Then binomial(n,k) gives the number of permutations in S(n+1) with k descents. Alternatively, binomial(n,k) gives the number of permutations in S(n+1) with k+1 increasing runs. - Peter Bala, Mar 24 2013
Sum_{n=>0} binomial(n,k)/n! = e/k!, where e = exp(1), while allowing n < k where binomial(n,k) = 0. Also Sum_{n>=0} binomial(n+k-1,k)/n! = e * A000262(k)/k!, and for k>=1 equals e * A067764(k)/A067653(k). - Richard R. Forberg, Jan 01 2014
The square n X n submatrix (first n rows and n columns) of the Pascal matrix P(x) defined in the formulas below when multiplying on the left the Vandermonde matrix V(x_1,...,x_n) (with ones in the first row) translates the matrix to V(x_1+x,...,x_n+x) while leaving the determinant invariant. - Tom Copeland, May 19 2014
For k>=2, n>=k, k/((k/(k-1) - Sum_{n=k..m} 1/binomial(n,k))) = m!/((m-k+1)!*(k-2)!). Note: k/(k-1) is the infinite sum. See A000217, A000292, A000332 for examples. - Richard R. Forberg, Aug 12 2014
Let G_(2n) be the subgroup of the symmetric group S_(2n) defined by G_(2n) = {p in S_(2n) | p(i) = i (mod n) for i = 1,2,...,2n}. G_(2n) has order 2^n. Binomial(n,k) gives the number of permutations in G_(2n) having n + k cycles. Cf. A130534 and A246117. - Peter Bala, Aug 15 2014
C(n,k) = the number of Dyck paths of semilength n+1, with k+1 "u"'s in odd numbered positions and k+1 returns to the x axis. Example: {U = u in odd position and = return to x axis} binomial(3,0)=1 (Uudududd); binomial(3,1)=3 [(Uududd_Ud_), (Ud_Uududd_), (Uudd_Uudd_)]; binomial(3,2)=3 [(Ud_Ud_Uudd_), (Uudd_Ud_Ud_), (Ud_Uudd_Ud_)]; binomial(3,3)=1 (Ud_Ud_Ud_Ud_). - Roger Ford, Nov 05 2014
From Daniel Forgues, Mar 12 2015: (Start)
The binomial coefficients binomial(n,k) give the number of individuals of the k-th generation after n population doublings. For each doubling of population, each individual's clone has its generation index incremented by 1, and thus goes to the next row. Just tally up each row from 0 to 2^n - 1 to get the binomial coefficients.
0 1 3 7 15
0: O | . | . . | . . . . | . . . . . . . . |
1: | O | O . | O . . . | O . . . . . . . |
2: | | O | O O . | O O . O . . . |
3: | | | O | O O O . |
4: | | | | O |
This is a fractal process: to get the pattern from 0 to 2^n - 1, append a shifted down (by one row) copy of the pattern from 0 to 2^(n-1) - 1 to the right of the pattern from 0 to 2^(n-1) - 1. (Inspired by the "binomial heap" data structure.)
Sequence of generation indices: 1's-counting sequence: number of 1's in binary expansion of n (or the binary weight of n) (see A000120):
{0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, ...}
Binary expansion of 0 to 15:
0 1 10 11 100 101 110 111 1000 1001 1010 1011 1100 1101 1111
(End)
A258993(n,k) = T(n+k,n-k), n > 0. - Reinhard Zumkeller, Jun 22 2015
T(n,k) is the number of set partitions w of [n+1] that avoid 1/2/3 with rb(w)=k. The same holds for ls(w)=k, where avoidance is in the sense of Klazar and ls,rb defined by Wachs and White.
Satisfies Benford's law [Diaconis, 1977] - N. J. A. Sloane, Feb 09 2017
Let {A(n)} be a set with exactly n identical elements, with {A(0)} being the empty set E. Let {A(n,k)} be the k-th iteration of {A(n)}, with {A(n,0)} = {A(n)}. {A(n,1)} = The set of all the subsets of A{(n)}, including {A(n)} and E. {A(n,k)} = The set of all subsets of {A(n,k-1)}, including all of the elements of {A(n,k-1)}. Let A(n,k) be the number of elements in {A(n,k)}. Then A(n,k) = C(n+k,k), with each successive iteration replicating the members of the k-th diagonal of Pascal's Triangle. See examples. - Gregory L. Simay, Aug 06 2018
Binomial(n-1,k) is also the number of permutations avoiding both 213 and 312 with k ascents. - Lara Pudwell, Dec 19 2018
Binomial(n-1,k) is also the number of permutations avoiding both 132 and 213 with k ascents. - Lara Pudwell, Dec 19 2018
Binomial(n,k) is the dimension of the k-th exterior power of a vector space of dimension n. - Stefano Spezia, Dec 22 2018
C(n,k-1) is the number of unoriented colorings of the facets (or vertices) of an n-dimensional simplex using exactly k colors. Each chiral pair is counted as one when enumerating unoriented arrangements. - Robert A. Russell, Oct 20 2020
From Dilcher and Stolarsky: "Two of the most ubiquitous objects in mathematics are the sequence of prime numbers and the binomial coefficients (and thus Pascal's triangle). A connection between the two is given by a well-known characterization of the prime numbers: Consider the entries in the k-th row of Pascal's triangle, without the initial and final entries. They are all divisible by k if and only if k is a prime." - Tom Copeland, May 17 2021
Named "Table de M. Pascal pour les combinaisons" by Pierre Remond de Montmort (1708) after the French mathematician, physicist and philosopher Blaise Pascal (1623-1662). - Amiram Eldar, Jun 11 2021
Consider the n-th diagonal of the triangle as a sequence b(n) with n starting at 0. From it form a new sequence by leaving the 0th term as is, and thereafter considering all compositions of n, taking the product of b(i) over the respective numbers i in each composition, adding terms corresponding to compositions with an even number of parts subtracting terms corresponding to compositions with an odd number of parts. Then the n-th row of the triangle is obtained, with every second term multiplied by -1, followed by infinitely many zeros. For sequences starting with 1, this operation is a special case of a self-inverse operation, and therefore the converse is true. - Thomas Anton, Jul 05 2021
C(n,k) is the number of vertices in an n-dimensional unit hypercube, at an L1 distance of k (or: with a shortest path of k 1d-edges) from a given vertex. - Eitan Y. Levine, May 01 2023
C(n+k-1,k-1) is the number of vertices at an L1 distance from a given vertex in an infinite-dimensional box, which has k sides of length 2^m for each m >= 0. Equivalently, given a set of tokens containing k distinguishable tokens with value 2^m for each m >= 0, C(n+k-1,k-1) is the number of subsets of tokens with a total value of n. - Eitan Y. Levine, Jun 11 2023
Numbers in the k-th column, i.e., numbers of the form C(n,k) for n >= k, are known as k-simplex numbers. - Pontus von Brömssen, Jun 26 2023
Let r(k) be the k-th row and c(k) the k-th column. Denote convolution by * and repeated convolution by ^. Then r(k)*r(m)=r(k+m) and c(k)*c(m)=c(k+m+1). This is because r(k) = r(1) ^ k and c(k) = c(0) ^ k+1. - Eitan Y. Levine, Jul 23 2023
Number of permutations of length n avoiding simultaneously the patterns 231 and 312(resp., 213 and 231; 213 and 312) with k descents (equivalently, with k ascents). An ascent (resp., descent) in a permutation a(1)a(2)...a(n) is position i such that a(i)a(i+1)). - Tian Han, Nov 25 2023
C(n,k) are generalized binomial coefficients of order m=0. Calculated by the formula C(n,k) = Sum_{i=0..n-k} binomial(n+1, n-k-i)*Stirling2(i+ m+ 1, i+1) *(-1)^i, where m = 0 for n>= 0, 0 <= k <= n. - Igor Victorovich Statsenko, Feb 26 2023
The Akiyama-Tanigawa algorithm applied to the diagonals, binomial(n+k,k), yields the powers of n. - Shel Kaphan, May 03 2024

Examples

			Triangle T(n,k) begins:
   n\k 0   1   2   3   4   5   6   7   8   9  10  11 ...
   0   1
   1   1   1
   2   1   2   1
   3   1   3   3   1
   4   1   4   6   4   1
   5   1   5  10  10   5   1
   6   1   6  15  20  15   6   1
   7   1   7  21  35  35  21   7   1
   8   1   8  28  56  70  56  28   8   1
   9   1   9  36  84 126 126  84  36   9   1
  10   1  10  45 120 210 252 210 120  45  10   1
  11   1  11  55 165 330 462 462 330 165  55  11   1
  ...
There are C(4,2)=6 ways to distribute 5 balls BBBBB, among 3 different urns, < > ( ) [ ], so that each urn gets at least one ball, namely, <BBB>(B)[B], <B>(BBB)[B], <B>(B)[BBB], <BB>(BB)[B], <BB>(B)[BB], and <B>(BB)[BB].
There are C(4,2)=6 increasing functions from {1,2} to {1,2,3,4}, namely, {(1,1),(2,2)},{(1,1),(2,3)}, {(1,1),(2,4)}, {(1,2),(2,3)}, {(1,2),(2,4)}, and {(1,3),(2,4)}. - _Dennis P. Walsh_, Apr 07 2011
There are C(4,2)=6 subsets of {1,2,3,4,5} with median element 3, namely, {3}, {1,3,4}, {1,3,5}, {2,3,4}, {2,3,5}, and {1,2,3,4,5}. - _Dennis P. Walsh_, Dec 15 2011
The successive k-iterations of {A(0)} = E are E;E;E;...; the corresponding number of elements are 1,1,1,... The successive k-iterations of {A(1)} = {a} are (omitting brackets) a;a,E; a,E,E;...; the corresponding number of elements are 1,2,3,... The successive k-iterations of {A(2)} = {a,a} are aa; aa,a,E; aa, a, E and a,E and E;...; the corresponding number of elements are 1,3,6,... - _Gregory L. Simay_, Aug 06 2018
Boas-Buck type recurrence for column k = 4: T(8, 4) = (5/4)*(1 + 5 + 15 + 35) = 70. See the Boas-Buck comment above. - _Wolfdieter Lang_, Nov 12 2018

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.
  • Amulya Kumar Bag, Binomial theorem in ancient India, Indian Journal of History of Science, vol. 1 (1966), pp. 68-74.
  • Arthur T. Benjamin and Jennifer Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, p. 63ff.
  • Boris A. Bondarenko, Generalized Pascal Triangles and Pyramids (in Russian), FAN, Tashkent, 1990, ISBN 5-648-00738-8.
  • Louis Comtet, Advanced Combinatorics, Reidel, 1974, p. 306.
  • John H. Conway and Richard K. Guy, The Book of Numbers, New York: Springer-Verlag, 1996. See pp. 68-74.
  • Paul Curtz, Intégration numérique des systèmes différentiels à conditions initiales, Centre de Calcul Scientifique de l'Armement, Arcueil, 1969.
  • A. W. F. Edwards, Pascal's Arithmetical Triangle, 2002.
  • William Feller, An Introduction to Probability Theory and Its Application, Vol. 1, 2nd ed. New York: Wiley, p. 36, 1968.
  • Ronald L. Graham, Donald E. Knuth, and Oren Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 2nd. ed., 1994, p. 155.
  • Jan Gullberg, Mathematics from the Birth of Numbers, W. W. Norton & Co., NY & London, 1997, §4.4 Powers and Roots, pp. 140-141.
  • David Hök, Parvisa mönster i permutationer [Swedish], 2007.
  • Donald E. Knuth, The Art of Computer Programming, Vol. 1, 2nd ed., p. 52.
  • Sergei K. Lando, Lecture on Generating Functions, Amer. Math. Soc., Providence, R.I., 2003, pp. 60-61.
  • Blaise Pascal, Traité du triangle arithmétique, avec quelques autres petits traitez sur la mesme matière, Desprez, Paris, 1665.
  • Clifford A. Pickover, A Passion for Mathematics, Wiley, 2005; see p. 71.
  • Alfred S. Posamentier, Math Charmers, Tantalizing Tidbits for the Mind, Prometheus Books, NY, 2003, pages 271-275.
  • A. P. Prudnikov, Yu. A. Brychkov, and O. I. Marichev, "Integrals and Series", Volume 1: "Elementary Functions", Chapter 4: "Finite Sums", New York, Gordon and Breach Science Publishers, 1986-1992.
  • John Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 6.
  • John Riordan, Combinatorial Identities, Wiley, 1968, p. 2.
  • Robert Sedgewick and Philippe Flajolet, An Introduction to the Analysis of Algorithms, Addison-Wesley, Reading, MA, 1996, p. 143.
  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
  • Jerome Spanier and Keith B. Oldham, "Atlas of Functions", Hemisphere Publishing Corp., 1987, chapter 6, pages 43-52.
  • James J. Tattersall, Elementary Number Theory in Nine Chapters, Cambridge University Press, 1999, pages 13, 30-33.
  • David Wells, The Penguin Dictionary of Curious and Interesting Numbers, Penguin Books, 1987, pp. 115-118.
  • Douglas B. West, Combinatorial Mathematics, Cambridge, 2021, p. 25.

Links

Crossrefs

Equals differences between consecutive terms of A102363. - David G. Williams (davidwilliams(AT)Paxway.com), Jan 23 2006
Row sums give A000079 (powers of 2).
Cf. A083093 (triangle read mod 3), A214292 (first differences of rows).
Partial sums of rows give triangle A008949.
The triangle of the antidiagonals is A011973.
Infinite matrix squared: A038207, cubed: A027465.
Cf. A101164. If rows are sorted we get A061554 or A107430.
Another version: A108044.
Cf. A008277, A132311, A132312, A052216, A052217, A052218, A052219, A052220, A052221, A052222, A052223, A144225, A202750, A211226, A047999, A026729, A052553, A051920, A193242.
Triangle sums (see the comments): A000079 (Row1); A000007 (Row2); A000045 (Kn11 & Kn21); A000071 (Kn12 & Kn22); A001924 (Kn13 & Kn23); A014162 (Kn14 & Kn24); A014166 (Kn15 & Kn25); A053739 (Kn16 & Kn26); A053295 (Kn17 & Kn27); A053296 (Kn18 & Kn28); A053308 (Kn19 & Kn29); A053309 (Kn110 & Kn210); A001519 (Kn3 & Kn4); A011782 (Fi1 & Fi2); A000930 (Ca1 & Ca2); A052544 (Ca3 & Ca4); A003269 (Gi1 & Gi2); A055988 (Gi3 & Gi4); A034943 (Ze1 & Ze2); A005251 (Ze3 & Ze4). - Johannes W. Meijer, Sep 22 2010
Fibonacci-Pascal triangles: A027926, A036355, A037027, A074829, A105809, A109906, A111006, A114197, A162741, A228074, A228196, A228576.
Cf. A137948, A245334.
Cf. A085478, A258993.
Cf. A115940 (pandigital binomial coefficients C(m,k) with k>1).
Cf. (simplex colorings) A325002 (oriented), [k==n+1] (chiral), A325003 (achiral), A325000 (k or fewer colors), A325009 (orthotope facets, orthoplex vertices), A325017 (orthoplex facets, orthotope vertices).
Triangles of generalized binomial coefficients (n,k)_m (or generalized Pascal triangles) for m = 2..12: A001263, A056939, A056940, A056941, A142465, A142467, A142468, A174109, A342889, A342890, A342891.

Programs

  • Axiom
    -- (start)
)set expose add constructor OutputForm
pascal(0,n) == 1
pascal(n,n) == 1
pascal(i,j | 0 < i and i < j) == pascal(i-1,j-1) + pascal(i,j-1)
pascalRow(n) == [pascal(i,n) for i in 0..n]
displayRow(n) == output center blankSeparate pascalRow(n)
for i in 0..20 repeat displayRow i -- (end)
  • GAP
    Flat(List([0..12],n->List([0..n],k->Binomial(n,k)))); # Stefano Spezia, Dec 22 2018
  • Haskell
    a007318 n k = a007318_tabl !! n !! k
a007318_row n = a007318_tabl !! n
a007318_list = concat a007318_tabl
a007318_tabl = iterate (\row -> zipWith (+) ([0] ++ row) (row ++ [0])) [1]
-- Cf. http://www.haskell.org/haskellwiki/Blow_your_mind#Mathematical_sequences
-- Reinhard Zumkeller, Nov 09 2011, Oct 22 2010
  • Magma
    /* As triangle: */ [[Binomial(n, k): k in [0..n]]: n in [0.. 10]]; // Vincenzo Librandi, Jul 29 2015
  • Maple
    A007318 := (n,k)->binomial(n,k);
  • Mathematica
    Flatten[Table[Binomial[n, k], {n, 0, 11}, {k, 0, n}]] (* Robert G. Wilson v, Jan 19 2004 *)
Flatten[CoefficientList[CoefficientList[Series[1/(1 - x - x*y), {x, 0, 12}], x], y]] (* Mats Granvik, Jul 08 2014 *)
  • Maxima
    create_list(binomial(n,k),n,0,12,k,0,n); /* Emanuele Munarini, Mar 11 2011 */
  • PARI
    C(n,k)=binomial(n,k) \\ Charles R Greathouse IV, Jun 08 2011
  • Python
    # See Hobson link. Further programs:
from math import prod,factorial
def C(n,k): return prod(range(n,n-k,-1))//factorial(k) # M. F. Hasler, Dec 13 2019, updated Apr 29 2022, Feb 17 2023
  • Python
    from math import comb, isqrt
def A007318(n): return comb(r:=(m:=isqrt(k:=n+1<<1))-(k<=m*(m+1)),n-comb(r+1,2)) # Chai Wah Wu, Nov 11 2024
  • Sage
    def C(n,k): return Subsets(range(n), k).cardinality() # Ralf Stephan, Jan 21 2014

Formula

a(n, k) = C(n,k) = binomial(n, k).
C(n, k) = C(n-1, k) + C(n-1, k-1).
The triangle is symmetric: C(n,k) = C(n,n-k).
a(n+1, m) = a(n, m) + a(n, m-1), a(n, -1) := 0, a(n, m) := 0, n
C(n, k) = n!/(k!(n-k)!) if 0<=k<=n, otherwise 0.
C(n, k) = ((n-k+1)/k) * C(n, k-1) with C(n, 0) = 1. - Michael B. Porter, Mar 23 2025
G.f.: 1/(1-y-x*y) = Sum_(C(n, k)*x^k*y^n, n, k>=0)
G.f.: 1/(1-x-y) = Sum_(C(n+k, k)*x^k*y^n, n, k>=0).
G.f. for row n: (1+x)^n = Sum_{k=0..n} C(n, k)*x^k.
G.f. for column k: x^k/(1-x)^(k+1); [corrected by Werner Schulte, Jun 15 2022].
E.g.f.: A(x, y) = exp(x+x*y).
E.g.f. for column n: x^n*exp(x)/n!.
In general the m-th power of A007318 is given by: T(0, 0) = 1, T(n, k) = T(n-1, k-1) + m*T(n-1, k), where n is the row-index and k is the column; also T(n, k) = m^(n-k)*C(n, k).
Triangle T(n, k) read by rows; given by A000007 DELTA A000007, where DELTA is Deléham's operator defined in A084938.
Let P(n+1) = the number of integer partitions of (n+1); let p(i) = the number of parts of the i-th partition of (n+1); let d(i) = the number of different parts of the i-th partition of (n+1); let m(i, j) = multiplicity of the j-th part of the i-th partition of (n+1). Define the operator Sum_{i=1..P(n+1), p(i)=k+1} as the sum running from i=1 to i=P(n+1) but taking only partitions with p(i)=(k+1) parts into account. Define the operator Product_{j=1..d(i)} = product running from j=1 to j=d(i). Then C(n, k) = Sum_{p(i)=(k+1), i=1..P(n+1)} p(i)! / [Product_{j=1..d(i)} m(i, j)!]. E.g., C(5, 3) = 10 because n=6 has the following partitions with m=3 parts: (114), (123), (222). For their multiplicities one has: (114): 3!/(2!*1!) = 3; (123): 3!/(1!*1!*1!) = 6; (222): 3!/3! = 1. The sum is 3 + 6 + 1 = 10 = C(5, 3). - Thomas Wieder, Jun 03 2005
C(n, k) = Sum_{j=0..k} (-1)^j*C(n+1+j, k-j)*A000108(j). - Philippe Deléham, Oct 10 2005
G.f.: 1 + x*(1 + x) + x^3*(1 + x)^2 + x^6*(1 + x)^3 + ... . - Michael Somos, Sep 16 2006
Sum_{k=0..floor(n/2)} x^(n-k)*T(n-k,k) = A000007(n), A000045(n+1), A002605(n), A030195(n+1), A057087(n), A057088(n), A057089(n), A057090(n), A057091(n), A057092(n), A057093(n) for x = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, respectively. Sum_{k=0..floor(n/2)} (-1)^k*x^(n-k)*T(n-k,k) = A000007(n), A010892(n), A009545(n+1), A057083(n), A001787(n+1), A030191(n), A030192(n), A030240(n), A057084(n), A057085(n+1), A057086(n), A084329(n+1) for x = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, respectively. - Philippe Deléham, Sep 16 2006
C(n,k) <= A062758(n) for n > 1. - Reinhard Zumkeller, Mar 04 2008
C(t+p-1, t) = Sum_{i=0..t} C(i+p-2, i) = Sum_{i=1..p} C(i+t-2, t-1). A binomial number is the sum of its left parent and all its right ancestors, which equals the sum of its right parent and all its left ancestors. - Lee Naish (lee(AT)cs.mu.oz.au), Mar 07 2008
From Paul D. Hanna, Mar 24 2011: (Start)
Let A(x) = Sum_{n>=0} x^(n*(n+1)/2)*(1+x)^n be the g.f. of the flattened triangle:
A(x) = 1 + (x + x^2) + (x^3 + 2*x^4 + x^5) + (x^6 + 3*x^7 + 3*x^8 + x^9) + ...
then A(x) equals the series Sum_{n>=0} (1+x)^n*x^n*Product_{k=1..n} (1-(1+x)*x^(2*k-1))/(1-(1+x)*x^(2*k));
also, A(x) equals the continued fraction 1/(1- x*(1+x)/(1+ x*(1-x)*(1+x)/(1- x^3*(1+x)/(1+ x^2*(1-x^2)*(1+x)/(1- x^5*(1+x)/(1+ x^3*(1-x^3)*(1+x)/(1- x^7*(1+x)/(1+ x^4*(1-x^4)*(1+x)/(1- ...))))))))).
These formulas are due to (1) a q-series identity and (2) a partial elliptic theta function expression. (End)
For n > 0: T(n,k) = A029600(n,k) - A029635(n,k), 0 <= k <= n. - Reinhard Zumkeller, Apr 16 2012
Row n of the triangle is the result of applying the ConvOffs transform to the first n terms of the natural numbers (1, 2, 3, ..., n). See A001263 or A214281 for a definition of this transformation. - Gary W. Adamson, Jul 12 2012
From L. Edson Jeffery, Aug 02 2012: (Start)
Row n (n >= 0) of the triangle is given by the n-th antidiagonal of the infinite matrix P^n, where P = (p_{i,j}), i,j >= 0, is the production matrix
0, 1,
1, 0, 1,
0, 1, 0, 1,
0, 0, 1, 0, 1,
0, 0, 0, 1, 0, 1,
0, 0, 0, 0, 1, 0, 1,
0, 0, 0, 0, 0, 1, 0, 1,
0, 0, 0, 0, 0, 0, 1, 0, 1,
... (End)
Row n of the triangle is also given by the n+1 coefficients of the polynomial P_n(x) defined by the recurrence P_0(x) = 1, P_1(x) = x + 1, P_n(x) = x*P_{n-1}(x) + P_{n-2}(x), n > 1. - L. Edson Jeffery, Aug 12 2013
For a closed-form formula for arbitrary left and right borders of Pascal-like triangles see A228196. - Boris Putievskiy, Aug 18 2013
For a closed-form formula for generalized Pascal's triangle see A228576. - Boris Putievskiy, Sep 04 2013
(1+x)^n = Sum_{k=0..n} (-1)^(n-k)*binomial(n,k)*Sum_{i=0..k} k^(n-i)*binomial(k,i)*x^(n-i)/(n-i)!. - Vladimir Kruchinin, Oct 21 2013
E.g.f.: A(x,y) = exp(x+x*y) = 1 + (x+y*x)/( E(0)-(x+y*x)), where E(k) = 1 + (x+y*x)/(1 + (k+1)/E(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Nov 08 2013
E.g.f.: E(0) -1, where E(k) = 2 + x*(1+y)/(2*k+1 - x*(1+y)/E(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Dec 24 2013
G.f.: 1 + x*(1+x)*(1+x^2*(1+x)/(W(0)-x^2-x^3)), where W(k) = 1 + (1+x)*x^(k+2) - (1+x)*x^(k+3)/W(k+1); (continued fraction). - Sergei N. Gladkovskii, Dec 24 2013
Sum_{n>=0} C(n,k)/n! = e/k!, where e = exp(1), while allowing n < k where C(n,k) = 0. Also Sum_{n>=0} C(n+k-1,k)/n! = e * A000262(k)/k!, and for k>=1 equals e * A067764(k)/A067653(k). - Richard R. Forberg, Jan 01 2014
Sum_{n>=k} 1/C(n,k) = k/(k-1) for k>=1. - Richard R. Forberg, Feb 10 2014
From Tom Copeland, Apr 26 2014: (Start)
Multiply each n-th diagonal of the Pascal lower triangular matrix by x^n and designate the result by A007318(x) = P(x). Then with :xD:^n = x^n*(d/dx)^n and B(n,x), the Bell polynomials (A008277),
A) P(x)= exp(x*dP) = exp[x*(e^M-I)] = exp[M*B(.,x)] = (I+dP)^B(.,x)
with dP = A132440, M = A238385-I, and I = identity matrix, and
B) P(:xD:) = exp(dP:xD:) = exp[(e^M-I):xD:] = exp[M*B(.,:xD:)] = exp[M*xD] = (I+dP)^(xD) with action P(:xD:)g(x) = exp(dP:xD:)g(x) = g[(I+dP)*x] (cf. also A238363).
C) P(x)^y = P(y*x). P(2x) = A038207(x) = exp[M*B(.,2x)], the face vectors of the n-dim hypercubes.
D) P(x) = [St2]*exp(x*M)*[St1] = [St2]*(I+dP)^x*[St1]
E) = [St1]^(-1)*(I+dP)^x*[St1] = [St2]*(I+dP)^x*[St2]^(-1)
where [St1]=padded A008275 just as [St2]=A048993=padded A008277 and exp(x*M) = (I+dP)^x = Sum_{k>=0} C(x,k) dP^k. (End)
T(n,k) = A245334(n,k) / A137948(n,k), 0 <= k <= n. - Reinhard Zumkeller, Aug 31 2014
From Peter Bala, Dec 21 2014: (Start)
Recurrence equation: T(n,k) = T(n-1,k)*(n + k)/(n - k) - T(n-1,k-1) for n >= 2 and 1 <= k < n, with boundary conditions T(n,0) = T(n,n) = 1. Note, changing the minus sign in the recurrence to a plus sign gives a recurrence for the square of the binomial coefficients - see A008459.
There is a relation between the e.g.f.'s of the rows and the diagonals of the triangle, namely, exp(x) * e.g.f. for row n = e.g.f. for diagonal n. For example, for n = 3 we have exp(x)*(1 + 3*x + 3*x^2/2! + x^3/3!) = 1 + 4*x + 10*x^2/2! + 20*x^3/3! + 35*x^4/4! + .... This property holds more generally for the Riordan arrays of the form ( f(x), x/(1 - x) ), where f(x) is an o.g.f. of the form 1 + f_1*x + f_2*x^2 + .... See, for example, A055248 and A106516.
Let P denote the present triangle. For k = 0,1,2,... define P(k) to be the lower unit triangular block array
/I_k 0\
\ 0 P/ having the k X k identity matrix I_k as the upper left block; in particular, P(0) = P. The infinite product P(0)*P(1)*P(2)*..., which is clearly well-defined, is equal to the triangle of Stirling numbers of the second kind A008277. The infinite product in the reverse order, that is, ...*P(2)*P(1)*P(0), is equal to the triangle of Stirling cycle numbers A130534. (End)
C(a+b,c) = Sum_{k=0..a} C(a,k)*C(b,b-c+k). This is a generalization of equation 1 from section 4.2.5 of the Prudnikov et al. reference, for a=b=c=n: C(2*n,n) = Sum_{k=0..n} C(n,k)^2. See Links section for animation of new formula. - Hermann Stamm-Wilbrandt, Aug 26 2015
The row polynomials of the Pascal matrix P(n,x) = (1+x)^n are related to the Bernoulli polynomials Br(n,x) and their umbral compositional inverses Bv(n,x) by the umbral relation P(n,x) = (-Br(.,-Bv(.,x)))^n = (-1)^n Br(n,-Bv(.,x)), which translates into the matrix relation P = M * Br * M * Bv, where P is the Pascal matrix, M is the diagonal matrix diag(1,-1,1,-1,...), Br is the matrix for the coefficients of the Bernoulli polynomials, and Bv that for the umbral inverse polynomials defined umbrally by Br(n,Bv(.,x)) = x^n = Bv(n,Br(.,x)). Note M = M^(-1). - Tom Copeland, Sep 05 2015
1/(1-x)^k = (r(x) * r(x^2) * r(x^4) * ...) where r(x) = (1+x)^k. - Gary W. Adamson, Oct 17 2016
Boas-Buck type recurrence for column k for Riordan arrays (see the Aug 10 2017 remark in A046521, also for the reference) with the Boas-Buck sequence b(n) = {repeat(1)}. T(n, k) = ((k+1)/(n-k))*Sum_{j=k..n-1} T(j, k), for n >= 1, with T(n, n) = 1. This reduces, with T(n, k) = binomial(n, k), to a known binomial identity (e.g, Graham et al. p. 161). - Wolfdieter Lang, Nov 12 2018
C((p-1)/a, b) == (-1)^b * fact_a(a*b-a+1)/fact_a(a*b) (mod p), where fact_n denotes the n-th multifactorial, a divides p-1, and the denominator of the fraction on the right side of the equation represents the modular inverse. - Isaac Saffold, Jan 07 2019
C(n,k-1) = A325002(n,k) - [k==n+1] = (A325002(n,k) + A325003(n,k)) / 2 = [k==n+1] + A325003(n,k). - Robert A. Russell, Oct 20 2020
From Hermann Stamm-Wilbrandt, May 13 2021: (Start)
Binomial sums are Fibonacci numbers A000045:
Sum_{k=0..n} C(n + k, 2*k + 1) = F(2*n).
Sum_{k=0..n} C(n + k, 2*k) = F(2*n + 1). (End)
C(n,k) = Sum_{i=0..k} A000108(i) * C(n-2i-1, k-i), for 0 <= k <= floor(n/2)-1. - Tushar Bansal, May 17 2025

Extensions

Checked all links, deleted 8 that seemed lost forever and were probably not of great importance. - N. J. A. Sloane, May 08 2018

A011782 Coefficients of expansion of (1-x)/(1-2*x) in powers of x.

Original entry on oeis.org

1, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824, 2147483648, 4294967296, 8589934592
Offset: 0

Views

Author

Lee D. Killough (killough(AT)wagner.convex.com)

Keywords

Comments

Apart from initial term, same as A000079 (powers of 2).
Number of compositions (ordered partitions) of n. - Toby Bartels, Aug 27 2003
Number of ways of putting n unlabeled items into (any number of) labeled boxes where every box contains at least one item. Also "unimodal permutations of n items", i.e., those which rise then fall. (E.g., for three items: ABC, ACB, BCA and CBA are unimodal.) - Henry Bottomley, Jan 17 2001
Number of permutations in S_n avoiding the patterns 213 and 312. - Tuwani Albert Tshifhumulo, Apr 20 2001. More generally (see Simion and Schmidt), the number of permutations in S_n avoiding (i) the 123 and 132 patterns; (ii) the 123 and 213 patterns; (iii) the 132 and 213 patterns; (iv) the 132 and 231 patterns; (v) the 132 and 312 patterns; (vi) the 213 and 231 patterns; (vii) the 213 and 312 patterns; (viii) the 231 and 312 patterns; (ix) the 231 and 321 patterns; (x) the 312 and 321 patterns.
a(n+2) is the number of distinct Boolean functions of n variables under action of symmetric group.
Number of unlabeled (1+2)-free posets. - Detlef Pauly, May 25 2003
Image of the central binomial coefficients A000984 under the Riordan array ((1-x), x*(1-x)). - Paul Barry, Mar 18 2005
Binomial transform of (1, 0, 1, 0, 1, 0, 1, 0, 1, 0, ...); inverse binomial transform of A007051. - Philippe Deléham, Jul 04 2005
Also, number of rationals in [0, 1) whose binary expansions terminate after n bits. - Brad Chalfan, May 29 2006
Equals row sums of triangle A144157. - Gary W. Adamson, Sep 12 2008
Prepend A089067 with a 1, getting (1, 1, 3, 5, 13, 23, 51, ...) as polcoeff A(x); then (1, 1, 2, 4, 8, 16, ...) = A(x)/A(x^2). - Gary W. Adamson, Feb 18 2010
An elephant sequence, see A175655. For the central square four A[5] vectors, with decimal values 2, 8, 32 and 128, lead to this sequence. For the corner squares these vectors lead to the companion sequence A094373. - Johannes W. Meijer, Aug 15 2010
From Paul Curtz, Jul 20 2011: (Start)
Array T(m,n) = 2*T(m,n-1) + T(m-1,n):
1, 1, 2, 4, 8, 16, ... = a(n)
1, 3, 8, 20, 48, 112, ... = A001792,
1, 5, 18, 56, 160, 432, ... = A001793,
1, 7, 32, 120, 400, 1232, ... = A001794,
1, 9, 50, 220, 840, 2912, ... = A006974, followed with A006975, A006976, gives nonzero coefficients of Chebyshev polynomials of first kind A039991 =
1,
1, 0,
2, 0, -1,
4, 0, -3, 0,
8, 0, -8, 0, 1.
T(m,n) third vertical: 2*n^2, n positive (A001105).
Fourth vertical appears in Janet table even rows, last vertical (A168342 array, A138509, rank 3, 13, = A166911)). (End)
A131577(n) and differences are:
0, 1, 2, 4, 8, 16,
1, 1, 2, 4, 8, 16, = a(n),
0, 1, 2, 4, 8, 16,
1, 1, 2, 4, 8, 16.
Number of 2-color necklaces of length 2n equal to their complemented reversal. For length 2n+1, the number is 0. - David W. Wilson, Jan 01 2012
Edges and also central terms of triangle A198069: a(0) = A198069(0,0) and for n > 0: a(n) = A198069(n,0) = A198069(n,2^n) = A198069(n,2^(n-1)). - Reinhard Zumkeller, May 26 2013
These could be called the composition numbers (see the second comment) since the equivalent sequence for partitions is A000041, the partition numbers. - Omar E. Pol, Aug 28 2013
Number of self conjugate integer partitions with exactly n parts for n>=1. - David Christopher, Aug 18 2014
The sequence is the INVERT transform of (1, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...). - Gary W. Adamson, Jul 16 2015
Number of threshold graphs on n nodes [Hougardy]. - Falk Hüffner, Dec 03 2015
Number of ternary words of length n in which binary subwords appear in the form 10...0. - Milan Janjic, Jan 25 2017
a(n) is the number of words of length n over an alphabet of two letters, of which one letter appears an even number of times (the empty word of length 0 is included). See the analogous odd number case in A131577, and the Balakrishnan reference in A006516 (the 4-letter odd case), pp. 68-69, problems 2.66, 2.67 and 2.68. - Wolfdieter Lang, Jul 17 2017
Number of D-equivalence classes of Łukasiewicz paths. Łukasiewicz paths are D-equivalent iff the positions of pattern D are identical in these paths. - Sergey Kirgizov, Apr 08 2018
Number of color patterns (set partitions) for an oriented row of length n using two or fewer colors (subsets). Two color patterns are equivalent if we permute the colors. For a(4)=8, the 4 achiral patterns are AAAA, AABB, ABAB, and ABBA; the 4 chiral patterns are the 2 pairs AAAB-ABBB and AABA-ABAA. - Robert A. Russell, Oct 30 2018
The determinant of the symmetric n X n matrix M defined by M(i,j) = (-1)^max(i,j) for 1 <= i,j <= n is equal to a(n) * (-1)^(n*(n+1)/2). - Bernard Schott, Dec 29 2018
For n>=1, a(n) is the number of permutations of length n whose cyclic representations can be written in such a way that when the cycle parentheses are removed what remains is 1 through n in natural order. For example, a(4)=8 since there are exactly 8 permutations of this form, namely, (1 2 3 4), (1)(2 3 4), (1 2)(3 4), (1 2 3)(4), (1)(2)(3 4), (1)(2 3)(4), (1 2)(3)(4), and (1)(2)(3)(4). Our result follows readily by conditioning on k, the number of parentheses pairs of the form ")(" in the cyclic representation. Since there are C(n-1,k) ways to insert these in the cyclic representation and since k runs from 0 to n-1, we obtain a(n) = Sum_{k=0..n-1} C(n-1,k) = 2^(n-1). - Dennis P. Walsh, May 23 2020
Maximum number of preimages that a permutation of length n + 1 can have under the consecutive-231-avoiding stack-sorting map. - Colin Defant, Aug 28 2020
a(n) is the number of occurrences of the empty set {} in the von Neumann ordinals from 0 up to n. Each ordinal k is defined as the set of all smaller ordinals: 0 = {}, 1 = {0}, 2 = {0,1}, etc. Since {} is the foundational element of all ordinals, the total number of times it appears grows as powers of 2. - Kyle Wyonch, Mar 30 2025

Examples

			G.f. = 1 + x + 2*x^2 + 4*x^3 + 8*x^4 + 16*x^5 + 32*x^6 + 64*x^7 + 128*x^8 + ...
    ( -1   1  -1)
det (  1   1   1)  = 4
    ( -1  -1  -1)

References

  • Mohammad K. Azarian, A Generalization of the Climbing Stairs Problem, Mathematics and Computer Education Journal, Vol. 31, No. 1, pp. 24-28, Winter 1997.
  • S. Kitaev, Patterns in Permutations and Words, Springer-Verlag, 2011. see p. 399 Table A.7
  • Xavier Merlin, Methodix Algèbre, Ellipses, 1995, p. 153.

Links

Crossrefs

Cf. A000670, A051486, A053120, A057711, A080929, A080961, A082138.
Cf. A082139, A082140, A082141, A089067, A144157, A131577, A211216.
Sequences with g.f.'s of the form ((1-x)/(1-2*x))^k: this sequence (k=1), A045623 (k=2), A058396 (k=3), A062109 (k=4), A169792 (k=5), A169793 (k=6), A169794 (k=7), A169795 (k=8), A169796 (k=9), A169797 (k=10).
Cf. A005418 (unoriented), A122746(n-3) (chiral), A016116 (achiral).
Row sums of triangle A100257.
A row of A160232.
Row 2 of A278984.

Programs

  • Haskell
    a011782 n = a011782_list !! n
a011782_list = 1 : scanl1 (+) a011782_list
-- Reinhard Zumkeller, Jul 21 2013
  • Magma
    [Floor((1+2^n)/2): n in [0..35]]; // Vincenzo Librandi, Aug 21 2011
  • Maple
    A011782:= n-> ceil(2^(n-1)): seq(A011782(n), n=0..50); # Wesley Ivan Hurt, Feb 21 2015
with(PolynomialTools):  A011782:=seq(coeftayl((1-x)/(1-2*x), x = 0, k),k=0..10^2); # Muniru A Asiru, Sep 26 2017
  • Mathematica
    f[s_] := Append[s, Ceiling[Plus @@ s]]; Nest[f, {1}, 32] (* Robert G. Wilson v, Jul 07 2006 *)
CoefficientList[ Series[(1-x)/(1-2x), {x, 0, 32}], x] (* Robert G. Wilson v, Jul 07 2006 *)
Table[Sum[StirlingS2[n, k], {k,0,2}], {n, 0, 30}] (* Robert A. Russell, Apr 25 2018 *)
Join[{1},NestList[2#&,1,40]] (* Harvey P. Dale, Dec 06 2018 *)
  • PARI
    {a(n) = if( n<1, n==0, 2^(n-1))};
  • PARI
    Vec((1-x)/(1-2*x) + O(x^30)) \\ Altug Alkan, Oct 31 2015
  • Python
    def A011782(n): return 1 if n == 0 else 2**(n-1) # Chai Wah Wu, May 11 2022
  • Sage
    [sum(stirling_number2(n,j) for j in (0..2)) for n in (0..35)] # G. C. Greubel, Jun 02 2020

Formula

a(0) = 1, a(n) = 2^(n-1).
G.f.: (1 - x) / (1 - 2*x) = 1 / (1 - x / (1 - x)). - Michael Somos, Apr 18 2012
E.g.f.: cosh(z)*exp(z) = (exp(2*z) + 1)/2.
a(0) = 1 and for n>0, a(n) = sum of all previous terms.
a(n) = Sum_{k=0..n} binomial(n, 2*k). - Paul Barry, Feb 25 2003
a(n) = Sum_{k=0..n} binomial(n,k)*(1+(-1)^k)/2. - Paul Barry, May 27 2003
a(n) = floor((1+2^n)/2). - Toby Bartels (toby+sloane(AT)math.ucr.edu), Aug 27 2003
G.f.: Sum_{i>=0} x^i/(1-x)^i. - Jon Perry, Jul 10 2004
a(n) = Sum_{k=0..n} (-1)^(n-k)*binomial(k+1, n-k)*binomial(2*k, k). - Paul Barry, Mar 18 2005
a(n) = Sum_{k=0..floor(n/2)} A055830(n-k, k). - Philippe Deléham, Oct 22 2006
a(n) = Sum_{k=0..n} A098158(n,k). - Philippe Deléham, Dec 04 2006
G.f.: 1/(1 - (x + x^2 + x^3 + ...)). - Geoffrey Critzer, Aug 30 2008
a(n) = A000079(n) - A131577(n).
a(n) = A173921(A000079(n)). - Reinhard Zumkeller, Mar 04 2010
a(n) = Sum_{k=2^n..2^(n+1)-1} A093873(k)/A093875(k), sums of rows of the full tree of Kepler's harmonic fractions. - Reinhard Zumkeller, Oct 17 2010
E.g.f.: (exp(2*x)+1)/2 = (G(0) + 1)/2; G(k) = 1 + 2*x/(2*k+1 - x*(2*k+1)/(x + (k+1)/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, Dec 03 2011
A051049(n) = p(n+1) where p(x) is the unique degree-n polynomial such that p(k) = a(k) for k = 0, 1, ..., n. - Michael Somos, Apr 18 2012
A008619(n) = p(-1) where p(x) is the unique degree-n polynomial such that p(k) = a(k) for k = 0, 1, ..., n. - Michael Somos, Apr 18 2012
INVERT transform is A122367. MOBIUS transform is A123707. EULER transform of A059966. PSUM transform is A000079. PSUMSIGN transform is A078008. BINOMIAL transform is A007051. REVERT transform is A105523. A002866(n) = a(n)*n!. - Michael Somos, Apr 18 2012
G.f.: U(0), where U(k) = 1 + x*(k+3) - x*(k+2)/U(k+1); (continued fraction, 1-step). - Sergei N. Gladkovskii, Oct 10 2012
a(n) = A000041(n) + A056823(n). - Omar E. Pol, Aug 31 2013
E.g.f.: E(0), where E(k) = 1 + x/( 2*k+1 - x/E(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Dec 25 2013
G.f.: 1 + x/(1 + x)*( 1 + 3*x/(1 + 3*x)*( 1 + 5*x/(1 + 5*x)*( 1 + 7*x/(1 + 7*x)*( 1 + ... )))). - Peter Bala, May 27 2017
a(n) = Sum_{k=0..2} stirling2(n, k).
G.f.: Sum_{j=0..k} A248925(k,j)*x^j / Product_{j=1..k} 1-j*x with k=2. - Robert A. Russell, Apr 25 2018
a(n) = A053120(n, n), n >= 0, (main diagonal of triangle of Chebyshev's T polynomials). - Wolfdieter Lang, Nov 26 2019

Extensions

Additional comments from Emeric Deutsch, May 14 2001
Typo corrected by Philippe Deléham, Oct 25 2008

A000265 Remove all factors of 2 from n; or largest odd divisor of n; or odd part of n.

Original entry on oeis.org

1, 1, 3, 1, 5, 3, 7, 1, 9, 5, 11, 3, 13, 7, 15, 1, 17, 9, 19, 5, 21, 11, 23, 3, 25, 13, 27, 7, 29, 15, 31, 1, 33, 17, 35, 9, 37, 19, 39, 5, 41, 21, 43, 11, 45, 23, 47, 3, 49, 25, 51, 13, 53, 27, 55, 7, 57, 29, 59, 15, 61, 31, 63, 1, 65, 33, 67, 17, 69, 35, 71, 9, 73, 37, 75, 19, 77
Offset: 1

Views

Author

N. J. A. Sloane

Keywords

Comments

When n > 0 is written as k*2^j with k odd then k = A000265(n) and j = A007814(n), so: when n is written as k*2^j - 1 with k odd then k = A000265(n+1) and j = A007814(n+1), when n > 1 is written as k*2^j + 1 with k odd then k = A000265(n-1) and j = A007814(n-1).
Also denominator of 2^n/n (numerator is A075101(n)). - Reinhard Zumkeller, Sep 01 2002
Slope of line connecting (o, a(o)) where o = (2^k)(n-1) + 1 is 2^k and (by design) starts at (1, 1). - Josh Locker (joshlocker(AT)macfora.com), Apr 17 2004
Numerator of n/2^(n-1). - Alexander Adamchuk, Feb 11 2005
From Marco Matosic, Jun 29 2005: (Start)
"The sequence can be arranged in a table:
1
1 3 1
1 5 3 7 1
1 9 5 11 3 13 7 15 1
1 17 9 19 5 21 11 23 3 25 13 27 7 29 15 31 1
Every new row is the previous row interspaced with the continuation of the odd numbers.
Except for the ones; the terms (t) in each column are t+t+/-s = t_+1. Starting from the center column of threes and working to the left the values of s are given by A000265 and working to the right by A000265." (End)
This is a fractal sequence. The odd-numbered elements give the odd natural numbers. If these elements are removed, the original sequence is recovered. - Kerry Mitchell, Dec 07 2005
2k + 1 is the k-th and largest of the subsequence of k terms separating two successive equal entries in a(n). - Lekraj Beedassy, Dec 30 2005
It's not difficult to show that the sum of the first 2^n terms is (4^n + 2)/3. - Nick Hobson, Jan 14 2005
In the table, for each row, (sum of terms between 3 and 1) - (sum of terms between 1 and 3) = A020988. - Eric Desbiaux, May 27 2009
This sequence appears in the analysis of A160469 and A156769, which resemble the numerator and denominator of the Taylor series for tan(x). - Johannes W. Meijer, May 24 2009
Indices n such that a(n) divides 2^n - 1 are listed in A068563. - Max Alekseyev, Aug 25 2013
From Alexander R. Povolotsky, Dec 17 2014: (Start)
With regard to the tabular presentation described in the comment by Marco Matosic: in his drawing, starting with the 3rd row, the first term in the row, which is equal to 1 (or, alternatively the last term in the row, which is also equal to 1), is not in the actual sequence and is added to the drawing as a fictitious term (for the sake of symmetry); an actual A000265(n) could be considered to be a(j,k) (where j >= 1 is the row number and k>=1 is the column subscript), such that a(j,1) = 1:
1
1 3
1 5 3 7
1 9 5 11 3 13 7 15
1 17 9 19 5 21 11 23 3 25 13 27 7 29 15 31
and so on ... .
The relationship between k and j for each row is 1 <= k <= 2^(j-1). In this corrected tabular representation, Marco's notion that "every new row is the previous row interspaced with the continuation of the odd numbers" remains true. (End)
Partitions natural numbers to the same equivalence classes as A064989. That is, for all i, j: a(i) = a(j) <=> A064989(i) = A064989(j). There are dozens of other such sequences (like A003602) for which this also holds: In general, all sequences for which a(2n) = a(n) and the odd bisection is injective. - Antti Karttunen, Apr 15 2017
From Paul Curtz, Feb 19 2019: (Start)
This sequence is the truncated triangle:
1, 1;
3, 1, 5;
3, 7, 1, 9;
5, 11, 3, 13, 7;
15, 1, 17, 9, 19, 5;
21, 11, 23, 3, 25, 13, 27;
7, 29, 15, 31, 1, 33, 17, 35;
...
The first column is A069834. The second column is A213671. The main diagonal is A236999. The first upper diagonal is A125650 without 0.
c(n) = ((n*(n+1)/2))/A069834 = 1, 1, 2, 2, 1, 1, 4, 4, 1, 1, 2, 2, 1, 1, 8, 8, 1, 1, ... for n > 0. n*(n+1)/2 is the rank of A069834. (End)
As well as being multiplicative, a(n) is a strong divisibility sequence, that is, gcd(a(n),a(m)) = a(gcd(n,m)) for n, m >= 1. In particular, a(n) is a divisibility sequence: if n divides m then a(n) divides a(m). - Peter Bala, Feb 27 2019
a(n) is also the map n -> A026741(n) applied at least A007814(n) times. - Federico Provvedi, Dec 14 2021

Examples

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

References

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

Links

Crossrefs

Cf. A000004, A000010, A000123, A000217, A000225, A000265, A001227.
Cf. A003602, A003961, A006516, A006519, A007814, A008683, A014577.
Cf. A020988, A025480, A026741, A027750, A035263, A038502, A049606.
Cf. A064989, A065330, A068563, A069834, A075101, A111929, A111930.
Cf. A111918, A111919, A111920, A111921, A111922, A111923, A125650.
Cf. A127793, A132739, A132740, A156769, A160469, A182469, A209308.
Cf. A213671, A220466, A236999, A242603.
Cf. A049606 (partial products), A135013 (partial sums), A099545 (mod 4), A326937 (Dirichlet inverse).
Cf. A026741 (map), A001511 (converging steps), A038550 (prime index).
Cf. A195056 (Dgf at s=3).

Programs

  • Haskell
    a000265 = until odd (`div` 2)
-- Reinhard Zumkeller, Jan 08 2013, Apr 08 2011, Oct 14 2010
  • Java
    int A000265(n){
    while(n%2==0) n>>=1;
    return n;
}
/* Aidan Simmons, Feb 24 2019 */
  • Julia
    using IntegerSequences
[OddPart(n) for n in 1:77] |> println  # Peter Luschny, Sep 25 2021
  • Magma
    A000265:= func< n | n/2^Valuation(n,2) >;
[A000265(n): n in [1..120]]; // G. C. Greubel, Jul 31 2024
  • Maple
    A000265:=proc(n) local t1,d; t1:=1; for d from 1 by 2 to n do if n mod d = 0 then t1:=d; fi; od; t1; end: seq(A000265(n), n=1..77);
A000265 := n -> n/2^padic[ordp](n,2): seq(A000265(n), n=1..77); # Peter Luschny, Nov 26 2010
  • Mathematica
    a[n_Integer /; n > 0] := n/2^IntegerExponent[n, 2]; Array[a, 77] (* Josh Locker *)
a[ n_] := If[ n == 0, 0, n / 2^IntegerExponent[ n, 2]]; (* Michael Somos, Dec 17 2014 *)
  • PARI
    {a(n) = n >> valuation(n, 2)}; /* Michael Somos, Aug 09 2006, edited by M. F. Hasler, Dec 18 2014 */
  • Python
    from _future_ import division
def A000265(n):
    while not n % 2:
        n //= 2
    return n # Chai Wah Wu, Mar 25 2018
  • Python
    def a(n):
    while not n&1: n >>= 1
    return n
print([a(n) for n in range(1, 78)]) # Michael S. Branicky, Jun 26 2025
  • SageMath
    def A000265(n): return n//2^valuation(n,2)
[A000265(n) for n in (1..121)] # G. C. Greubel, Jul 31 2024
  • Scheme
    (define (A000265 n) (let loop ((n n)) (if (odd? n) n (loop (/ n 2))))) ;; Antti Karttunen, Apr 15 2017

Formula

a(n) = if n is odd then n, otherwise a(n/2). - Reinhard Zumkeller, Sep 01 2002
a(n) = n/A006519(n) = 2*A025480(n-1) + 1.
Multiplicative with a(p^e) = 1 if p = 2, p^e if p > 2. - David W. Wilson, Aug 01 2001
a(n) = Sum_{d divides n and d is odd} phi(d). - Vladeta Jovovic, Dec 04 2002
G.f.: -x/(1 - x) + Sum_{k>=0} (2*x^(2^k)/(1 - 2*x^(2^(k+1)) + x^(2^(k+2)))). - Ralf Stephan, Sep 05 2003
(a(k), a(2k), a(3k), ...) = a(k)*(a(1), a(2), a(3), ...) In general, a(n*m) = a(n)*a(m). - Josh Locker (jlocker(AT)mail.rochester.edu), Oct 04 2005
a(n) = Sum_{k=0..n} A127793(n,k)*floor((k+2)/2) (conjecture). - Paul Barry, Jan 29 2007
Dirichlet g.f.: zeta(s-1)*(2^s - 2)/(2^s - 1). - Ralf Stephan, Jun 18 2007
a(A132739(n)) = A132739(a(n)) = A132740(n). - Reinhard Zumkeller, Aug 27 2007
a(n) = 2*A003602(n) - 1. - Franklin T. Adams-Watters, Jul 02 2009
a(n) = n/gcd(2^n,n). (This also shows that the true offset is 0 and a(0) = 0.) - Peter Luschny, Nov 14 2009
a(-n) = -a(n) for all n in Z. - Michael Somos, Sep 19 2011
From Reinhard Zumkeller, May 01 2012: (Start)
A182469(n, k) = A027750(a(n), k), k = 1..A001227(n).
a(n) = A182469(n, A001227(n)). (End)
a((2*n-1)*2^p) = 2*n - 1, p >= 0 and n >= 1. - Johannes W. Meijer, Feb 05 2013
G.f.: G(0)/(1 - 2*x^2 + x^4) - 1/(1 - x), where G(k) = 1 + 1/(1 - x^(2^k)*(1 - 2*x^(2^(k+1)) + x^(2^(k+2)))/(x^(2^k)*(1 - 2*x^(2^(k+1)) + x^(2^(k+2))) + (1 - 2*x^(2^(k+2)) + x^(2^(k+3)))/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, Aug 06 2013
a(n) = A003961(A064989(n)). - Antti Karttunen, Apr 15 2017
Completely multiplicative with a(2) = 1 and a(p) = p for prime p > 2, i.e., the sequence b(n) = a(n) * A008683(n) for n > 0 is the Dirichlet inverse of a(n). - Werner Schulte, Jul 08 2018
From Peter Bala, Feb 27 2019: (Start)
O.g.f.: F(x) - F(x^2) - F(x^4) - F(x^8) - ..., where F(x) = x/(1 - x)^2 is the generating function for the positive integers.
O.g.f. for reciprocals: Sum_{n >= 1} x^n/a(n) = L(x) + (1/2)*L(x^2) + (1/2)*L(x^4) + (1/2)*L(x^8) + ..., where L(x) = log(1/(1 - x)).
Sum_{n >= 1} x^n/a(n) = 1/2*log(G(x)), where G(x) = 1 + 2*x + 4*x^2 + 6*x^3 + 10*x^4 + ... is the o.g.f. of A000123. (End)
O.g.f.: Sum_{n >= 1} phi(2*n-1)*x^(2*n-1)/(1 - x^(2*n-1)), where phi(n) is the Euler totient function A000010. - Peter Bala, Mar 22 2019
a(n) = A049606(n) / A049606(n-1). - Flávio V. Fernandes, Dec 08 2020
a(n) = numerator of n/2^(floor(n/2)). - Federico Provvedi, Dec 14 2021
a(n) = Sum_{d divides n} (-1)^(d+1)*phi(2*n/d). - Peter Bala, Jan 14 2024
a(n) = A030101(A030101(n)). - Darío Clavijo, Sep 19 2024

Extensions

Additional comments from Henry Bottomley, Mar 02 2000
More terms from Larry Reeves (larryr(AT)acm.org), Mar 14 2000
Name clarified by David A. Corneth, Apr 15 2017

A000043 Mersenne exponents: primes p such that 2^p - 1 is prime. Then 2^p - 1 is called a Mersenne prime.

Original entry on oeis.org

2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937, 21701, 23209, 44497, 86243, 110503, 132049, 216091, 756839, 859433, 1257787, 1398269, 2976221, 3021377, 6972593, 13466917, 20996011, 24036583, 25964951, 30402457, 32582657, 37156667, 42643801, 43112609, 57885161, 74207281
Offset: 1

Views

Author

N. J. A. Sloane

Keywords

Comments

Equivalently, integers k such that 2^k - 1 is prime.
It is believed (but unproved) that this sequence is infinite. The data suggest that the number of terms up to exponent N is roughly K log N for some constant K.
Length of prime repunits in base 2.
The associated perfect number N=2^(p-1)*M(p) (=A019279*A000668=A000396), has 2p (=A061645) divisors with harmonic mean p (and geometric mean sqrt(N)). - Lekraj Beedassy, Aug 21 2004
In one of his first publications Euler found the numbers up to 31 but erroneously included 41 and 47.
Equals number of bits in binary expansion of n-th Mersenne prime (A117293). - Artur Jasinski, Feb 09 2007
Number of divisors of n-th even perfect number, divided by 2. Number of divisors of n-th even perfect number that are powers of 2. Number of divisors of n-th even perfect number that are multiples of n-th Mersenne prime A000668(n). - Omar E. Pol, Feb 24 2008
Number of divisors of n-th even superperfect number A061652(n). Numbers of divisors of n-th superperfect number A019279(n), assuming there are no odd superperfect numbers. - Omar E. Pol, Mar 01 2008
Differences between exponents when the even perfect numbers are represented as differences of powers of 2, for example: The 5th even perfect number is 33550336 = 2^25 - 2^12 then a(5)=25-12=13 (see A135655, A133033, A090748). - Omar E. Pol, Mar 01 2008
Number of 1's in binary expansion of n-th even perfect number (see A135650). Number of 1's in binary expansion of divisors of n-th even perfect number that are multiples of n-th Mersenne prime A000668(n) (see A135652, A135653, A135654, A135655). - Omar E. Pol, May 04 2008
Indices of the numbers A006516 that are also even perfect numbers. - Omar E. Pol, Aug 30 2008
Indices of Mersenne numbers A000225 that are also Mersenne primes A000668. - Omar E. Pol, Aug 31 2008
The (prime) number p appears in this sequence if and only if there is no prime q<2^p-1 such that the order of 2 modulo q equals p; a special case is that if p=4k+3 is prime and also q=2p+1 is prime then the order of 2 modulo q is p so p is not a term of this sequence. - Joerg Arndt, Jan 16 2011
Primes p such that sigma(2^p) - sigma(2^p-1) = 2^p-1. - Jaroslav Krizek, Aug 02 2013
Integers k such that every degree k irreducible polynomial over GF(2) is also primitive, i.e., has order 2^k-1. Equivalently, the integers k such that A001037(k) = A011260(k). - Geoffrey Critzer, Dec 08 2019
Conjecture: for k > 1, 2^k-1 is (a Mersenne) prime or k = 2^(2^m)+1 (is a Fermat number) if and only if (k-1)^(2^k-2) == 1 (mod (2^k-1)k^2). - Thomas Ordowski, Oct 05 2023
Conjecture: for p prime, 2^p-1 is (a Mersenne) prime or p = 2^(2^m)+1 (is a Fermat number) if and only if (p-1)^(2^p-2) == 1 (mod 2^p-1). - David Barina, Nov 25 2024
Already as of Dec. 2020, all exponents up to 10^8 had been verified, implying that 74207281, 77232917 and 82589933 are indeed the next three terms. As of today, all exponents up to 130439863 have been tested at least once, see the GIMPS Milestones Report. - M. F. Hasler, Apr 11 2025
On June 23. 2025 all exponents up to 74340751 have been verified, confirming that 74207281 is the exponent of the 49th Mersenne Prime. - Rodolfo Ruiz-Huidobro, Jun 23 2025

Examples

			Corresponding to the initial terms 2, 3, 5, 7, 13, 17, 19, 31 ... we get the Mersenne primes 2^2 - 1 = 3, 2^3 - 1 = 7, 2^5 - 1 = 31, 127, 8191, 131071, 524287, 2147483647, ... (see A000668).

References

  • T. M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976, page 4.
  • J. Brillhart et al., Factorizations of b^n +- 1. Contemporary Mathematics, Vol. 22, Amer. Math. Soc., Providence, RI, 2nd edition, 1985; and later supplements.
  • Jan Gullberg, Mathematics from the Birth of Numbers, W. W. Norton & Co., NY & London, 1997, §3.2 Prime Numbers, p. 79.
  • R. K. Guy, Unsolved Problems in Number Theory, Section A3.
  • F. Lemmermeyer, Reciprocity Laws From Euler to Eisenstein, Springer-Verlag, 2000, p. 57.
  • Clifford A. Pickover, A Passion for Mathematics, Wiley, 2005; see p. 19.
  • Alfred S. Posamentier, Math Charmers, Tantalizing Tidbits for the Mind, Prometheus Books, NY, 2003, page 47.
  • 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 132-134.
  • B. Tuckerman, The 24th Mersenne prime, Notices Amer. Math. Soc., 18 (Jun, 1971), Abstract 684-A15, p. 608.

Links

Crossrefs

Cf. A000668 (Mersenne primes).
Cf. A028335 (integer lengths of Mersenne primes).
Cf. A000225 (Mersenne numbers).
Cf. A001348 (Mersenne numbers with n prime).
Cf. A016027, A046051, A057429, A057951-A057958, A066408, A117293, A127962, A127963, A127964, A127965, A127961, A000979, A000978, A124400, A124401, A127955, A127956, A127957, A127958, A127936, A134458, A000225, A000396, A090748, A133033, A135655, A006516, A019279, A061652, A133033, A135650, A135652, A135653, A135654, A260073, A050475, A379590.

Programs

  • Mathematica
    MersennePrimeExponent[Range[48]] (* Eric W. Weisstein, Jul 17 2017; updated Oct 21 2024 *)
  • PARI
    isA000043(n) = isprime(2^n-1) \\ Michael B. Porter, Oct 28 2009
  • PARI
    is(n)=my(h=Mod(2,2^n-1)); for(i=1, n-2, h=2*h^2-1); h==0||n==2 \\ Lucas-Lehmer test for exponent e. - Joerg Arndt, Jan 16 2011, and Charles R Greathouse IV, Jun 05 2013
forprime(e=2,5000,if(is(e),print1(e,", "))); /* terms < 5000 */
  • Python
    from sympy import isprime, prime
for n in range(1,100):
    if isprime(2**prime(n)-1):
        print(prime(n), end=', ') # Stefano Spezia, Dec 06 2018

Formula

a(n) = log((1/2)*(1+sqrt(1+8*A000396(n))))/log(2). - Artur Jasinski, Sep 23 2008 (under the assumption there are no odd perfect numbers, Joerg Arndt, Feb 23 2014)
a(n) = A000005(A061652(n)). - Omar E. Pol, Aug 26 2009
a(n) = A000120(A000396(n)), assuming there are no odd perfect numbers. - Omar E. Pol, Oct 30 2013

Extensions

Also in the sequence: p = 74207281. - Charles R Greathouse IV, Jan 19 2016
Also in the sequence: p = 77232917. - Eric W. Weisstein, Jan 03 2018
Also in the sequence: p = 82589933. - Gord Palameta, Dec 21 2018
a(46) = 42643801 and a(47) = 43112609, whose ordinal positions in the sequence are now confirmed, communicated by Eric W. Weisstein, Apr 12 2018
a(48) = 57885161, whose ordinal position in the sequence is now confirmed, communicated by Benjamin Przybocki, Jan 05 2022
Also in the sequence: p = 136279841. - Eric W. Weisstein, Oct 21 2024
As of Jan 31 2025, 48 terms are known, and are shown in the DATA section. Four additional numbers are known to be in the sequence, namely 74207281, 77232917, 82589933, and 136279841, but they may not be the next terms. See the GIMP website for the latest information. - N. J. A. Sloane, Jan 31 2025

A000396 Perfect numbers k: k is equal to the sum of the proper divisors of k.

Original entry on oeis.org

6, 28, 496, 8128, 33550336, 8589869056, 137438691328, 2305843008139952128, 2658455991569831744654692615953842176, 191561942608236107294793378084303638130997321548169216
Offset: 1

Views

Author

N. J. A. Sloane

Keywords

Comments

A number k is abundant if sigma(k) > 2k (cf. A005101), perfect if sigma(k) = 2k (this sequence), or deficient if sigma(k) < 2k (cf. A005100), where sigma(k) is the sum of the divisors of k (A000203).
The numbers 2^(p-1)*(2^p - 1) are perfect, where p is a prime such that 2^p - 1 is also prime (for the list of p's see A000043). There are no other even perfect numbers and it is believed that there are no odd perfect numbers.
Numbers k such that Sum_{d|k} 1/d = 2. - Benoit Cloitre, Apr 07 2002
For number of divisors of a(n) see A061645(n). Number of digits in a(n) is A061193(n). - Lekraj Beedassy, Jun 04 2004
All terms other than the first have digital root 1 (since 4^2 == 4 (mod 6), we have, by induction, 4^k == 4 (mod 6), or 2*2^(2*k) = 8 == 2 (mod 6), implying that Mersenne primes M = 2^p - 1, for odd p, are of the form 6*t+1). Thus perfect numbers N, being M-th triangular, have the form (6*t+1)*(3*t+1), whence the property N mod 9 = 1 for all N after the first. - Lekraj Beedassy, Aug 21 2004
The earliest recorded mention of this sequence is in Euclid's Elements, IX 36, about 300 BC. - Artur Jasinski, Jan 25 2006
Theorem (Euclid, Euler). An even number m is a perfect number if and only if m = 2^(k-1)*(2^k-1), where 2^k-1 is prime. Euler's idea came from Euclid's Proposition 36 of Book IX (see Weil). It follows that every even perfect number is also a triangular number. - Mohammad K. Azarian, Apr 16 2008
Triangular numbers (also generalized hexagonal numbers) A000217 whose indices are Mersenne primes A000668, assuming there are no odd perfect numbers. - Omar E. Pol, May 09 2008, Sep 15 2013
If a(n) is even, then 2*a(n) is in A181595. - Vladimir Shevelev, Nov 07 2010
Except for a(1) = 6, all even terms are of the form 30*k - 2 or 45*k + 1. - Arkadiusz Wesolowski, Mar 11 2012
a(4) = A229381(1) = 8128 is the "Simpsons's perfect number". - Jonathan Sondow, Jan 02 2015
Theorem (Farideh Firoozbakht): If m is an integer and both p and p^k-m-1 are prime numbers then x = p^(k-1)*(p^k-m-1) is a solution to the equation sigma(x) = (p*x+m)/(p-1). For example, if we take m=0 and p=2 we get Euclid's result about perfect numbers. - Farideh Firoozbakht, Mar 01 2015
The cototient of the even perfect numbers is a square; in particular, if 2^p - 1 is a Mersenne prime, cototient(2^(p-1) * (2^p - 1)) = (2^(p-1))^2 (see A152921). So, this sequence is a subsequence of A063752. - Bernard Schott, Jan 11 2019
Euler's (1747) proof that all the even perfect number are of the form 2^(p-1)*(2^p-1) implies that their asymptotic density is 0. Kanold (1954) proved that the asymptotic density of odd perfect numbers is 0. - Amiram Eldar, Feb 13 2021
If k is perfect and semiprime, then k = 6. - Alexandra Hercilia Pereira Silva, Aug 30 2021
This sequence lists the fixed points of A001065. - Alois P. Heinz, Mar 10 2024

Examples

			6 is perfect because 6 = 1+2+3, the sum of all divisors of 6 less than 6; 28 is perfect because 28 = 1+2+4+7+14.

References

  • Tom M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976, page 4.
  • Albert H. Beiler, Recreations in the Theory of Numbers, Dover, NY, 2d ed. 1966, pp. 11-23.
  • Stanley J. Bezuszka, Perfect Numbers (Booklet 3, Motivated Math. Project Activities), Boston College Press, Chestnut Hill MA, 1980.
  • John H. Conway and Richard K. Guy, The Book of Numbers, New York: Springer-Verlag, 1996. See pp. 136-137.
  • Euclid, Elements, Book IX, Section 36, about 300 BC.
  • Jan Gullberg, Mathematics from the Birth of Numbers, W. W. Norton & Co., NY & London, 1997, §3.3 Perfect and Amicable Numbers, pp. 82-83.
  • R. K. Guy, Unsolved Problems in Number Theory, Springer, 1st edition, 1981. See section B1.
  • G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers. 3rd ed., Oxford Univ. Press, 1954, p. 239.
  • T. Koshy, "The Ends Of A Mersenne Prime And An Even Perfect Number", Journal of Recreational Mathematics, Baywood, NY, 1998, pp. 196-202.
  • Joseph S. Madachy, Madachy's Mathematical Recreations, New York: Dover Publications, Inc., 1979, p. 149 (First publ. by Charles Scribner's Sons, New York, 1966, under the title: Mathematics on Vacation).
  • Alfred S. Posamentier, Math Charmers, Tantalizing Tidbits for the Mind, Prometheus Books, NY, 2003, pages 46-48, 244-245.
  • Paulo Ribenboim, The Little Book of Bigger Primes, Springer-Verlag NY 2004. See pp. 83-87.
  • József Sándor and Borislav Crstici, Handbook of Number Theory, II, Springer Verlag, 2004.
  • 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).
  • Ian Stewart, L'univers des nombres, "Diviser Pour Régner", Chapter 14, pp. 74-81, Belin-Pour La Science, Paris, 2000.
  • James J. Tattersall, Elementary Number Theory in Nine Chapters, Cambridge University Press, 1999, chapter 4, pages 127-149.
  • Horace S. Uhler, On the 16th and 17th perfect numbers, Scripta Math., Vol. 19 (1953), pp. 128-131.
  • André Weil, Number Theory, An approach through history, From Hammurapi to Legendre, Birkhäuser, 1984, p. 6.
  • David Wells, The Penguin Dictionary of Curious and Interesting Numbers, pp. 107-110, Penguin Books, 1987.

Links

Crossrefs

See A000043 for the current state of knowledge about Mersenne primes.
Cf. A007539, A005820, A027687, A046060, A046061, A000668, A090748, A133033, A000217, A000384, A019279, A061652, A006516, A144912, A153800, A007593, A220290, A028499-A028502, A034916, A065549, A275496, A063752, A156552, A152921, A324201.
Cf. A228058 for Euler's criterion for odd terms.
Positions of 0's in A033879 and in A033880.
Subsequence of following sequences: A005835, A006039, A007691, A023196, A043305, A065997, A083207, A109510, A118372, A216782, A246282, A263837, A294900, A333646, A334410, A335267, A336702, A341622, A342922, A344755, A352739, A357462, and (the even terms), of: A005153, A063752, A174973, A336547, A338520.
Cf. A001065.

Programs

  • Haskell
    a000396 n = a000396_list !! (n-1)
a000396_list = [x | x <- [1..], a000203 x == 2 * x]
-- Reinhard Zumkeller, Jan 20 2012
  • Mathematica
    Select[Range[9000], DivisorSigma[1,#]== 2*# &] (* G. C. Greubel, Oct 03 2017 *)
PerfectNumber[Range[15]] (* Requires Mathematica version 10 or later *) (* Harvey P. Dale, Dec 10 2018 *)
  • PARI
    isA000396(n) = (sigma(n) == 2*n);
  • Python
    from sympy import divisor_sigma
def ok(n): return n > 0 and divisor_sigma(n) == 2*n
print([k for k in range(9999) if ok(k)]) # Michael S. Branicky, Mar 12 2022

Formula

The perfect number N = 2^(p-1)*(2^p - 1) is also multiplicatively p-perfect (i.e., A007955(N) = N^p), since tau(N) = 2*p. - Lekraj Beedassy, Sep 21 2004
a(n) = 2^A133033(n) - 2^A090748(n), assuming there are no odd perfect numbers. - Omar E. Pol, Feb 28 2008
a(n) = A000668(n)*(A000668(n)+1)/2, assuming there are no odd perfect numbers. - Omar E. Pol, Apr 23 2008
a(n) = A000217(A000668(n)), assuming there are no odd perfect numbers. - Omar E. Pol, May 09 2008
a(n) = Sum of the first A000668(n) positive integers, assuming there are no odd perfect numbers. - Omar E. Pol, May 09 2008
a(n) = A000384(A019279(n)), assuming there are no odd perfect numbers and no odd superperfect numbers. a(n) = A000384(A061652(n)), assuming there are no odd perfect numbers. - Omar E. Pol, Aug 17 2008
a(n) = A006516(A000043(n)), assuming there are no odd perfect numbers. - Omar E. Pol, Aug 30 2008
From Reikku Kulon, Oct 14 2008: (Start)
A144912(2, a(n)) = 1;
A144912(4, a(n)) = -1 for n > 1;
A144912(8, a(n)) = 5 or -5 for all n except 2;
A144912(16, a(n)) = -4 or -13 for n > 1. (End)
a(n) = A019279(n)*A000668(n), assuming there are no odd perfect numbers and odd superperfect numbers. a(n) = A061652(n)*A000668(n), assuming there are no odd perfect numbers. - Omar E. Pol, Jan 09 2009
a(n) = A007691(A153800(n)), assuming there are no odd perfect numbers. - Omar E. Pol, Jan 14 2009
Even perfect numbers N = K*A000203(K), where K = A019279(n) = 2^(p-1), A000203(A019279(n)) = A000668(n) = 2^p - 1 = M(p), p = A000043(n). - Lekraj Beedassy, May 02 2009
a(n) = A060286(A016027(n)), assuming there are no odd perfect numbers. - Omar E. Pol, Dec 13 2012
For n >= 2, a(n) = Sum_{k=1..A065549(n)} (2*k-1)^3, assuming there are no odd perfect numbers. - Derek Orr, Sep 28 2013
a(n) = A275496(2^((A000043(n) - 1)/2)) - 2^A000043(n), assuming there are no odd perfect numbers. - Daniel Poveda Parrilla, Aug 16 2016
a(n) = A156552(A324201(n)), assuming there are no odd perfect numbers. - Antti Karttunen, Mar 28 2019
a(n) = ((2^(A000043(n)))^3 - (2^(A000043(n)) - 1)^3 - 1)/6, assuming there are no odd perfect numbers. - Jules Beauchamp, Jun 06 2025

Extensions

I removed a large number of comments that assumed there are no odd perfect numbers. There were so many it was getting hard to tell which comments were true and which were conjectures. - N. J. A. Sloane, Apr 16 2023
Reference to Albert H. Beiler's book updated by Harvey P. Dale, Jan 13 2025

A139250 Toothpick sequence (see Comments lines for definition).

Original entry on oeis.org

0, 1, 3, 7, 11, 15, 23, 35, 43, 47, 55, 67, 79, 95, 123, 155, 171, 175, 183, 195, 207, 223, 251, 283, 303, 319, 347, 383, 423, 483, 571, 651, 683, 687, 695, 707, 719, 735, 763, 795, 815, 831, 859, 895, 935, 995, 1083, 1163, 1199, 1215, 1243, 1279, 1319, 1379
Offset: 0

Views

Author

Omar E. Pol, Apr 24 2008

Keywords

Comments

A toothpick is a copy of the closed interval [-1,1]. (In the paper, we take it to be a copy of the unit interval [-1/2, 1/2].)
We start at stage 0 with no toothpicks.
At stage 1 we place a toothpick in the vertical direction, anywhere in the plane.
In general, given a configuration of toothpicks in the plane, at the next stage we add as many toothpicks as possible, subject to certain conditions:
- Each new toothpick must lie in the horizontal or vertical directions.
- Two toothpicks may never cross.
- Each new toothpick must have its midpoint touching the endpoint of exactly one existing toothpick.
The sequence gives the number of toothpicks after n stages. A139251 (the first differences) gives the number added at the n-th stage.
Call the endpoint of a toothpick "exposed" if it does not touch any other toothpick. The growth rule may be expressed as follows: at each stage, new toothpicks are placed so their midpoints touch every exposed endpoint.
This is equivalent to a two-dimensional cellular automaton. The animations show the fractal-like behavior.
After 2^k - 1 steps, there are 2^k exposed endpoints, all located on two lines perpendicular to the initial toothpick. At the next step, 2^k toothpicks are placed on these lines, leaving only 4 exposed endpoints, located at the corners of a square with side length 2^(k-1) times the length of a toothpick. - M. F. Hasler, Apr 14 2009 and others. For proof, see the Applegate-Pol-Sloane paper.
If the third condition in the definition is changed to "- Each new toothpick must have at exactly one of its endpoints touching the midpoint of an existing toothpick" then the same sequence is obtained. The configurations of toothpicks are of course different from those in the present sequence. But if we start with the configurations of the present sequence, rotate each toothpick a quarter-turn, and then rotate the whole configuration a quarter-turn, we obtain the other configuration.
If the third condition in the definition is changed to "- Each new toothpick must have at least one of its endpoints touching the midpoint of an existing toothpick" then the sequence n^2 - n + 1 is obtained, because there are no holes left in the grid.
A "toothpick" of length 2 can be regarded as a polyedge with 2 components, both on the same line. At stage n, the toothpick structure is a polyedge with 2*a(n) components.
Conjecture: Consider the rectangles in the sieve (including the squares). The area of each rectangle (A = b*c) and the edges (b and c) are powers of 2, but at least one of the edges (b or c) is <= 2.
In the toothpick structure, if n >> 1, we can see some patterns that look like "canals" and "diffraction patterns". For example, see the Applegate link "A139250: the movie version", then enter n=1008 and click "Update". See also "T-square (fractal)" in the Links section. - Omar E. Pol, May 19 2009, Oct 01 2011
From Benoit Jubin, May 20 2009: The web page "Gallery" of Chris Moore (see link) has some nice pictures that are somewhat similar to the pictures of the present sequence. What sequences do they correspond to?
For a connection to Sierpiński triangle and Gould's sequence A001316, see the leftist toothpick triangle A151566.
Eric Rowland comments on Mar 15 2010 that this toothpick structure can be represented as a 5-state CA on the square grid. On Mar 18 2010, David Applegate showed that three states are enough. See links.
Equals row sums of triangle A160570 starting with offset 1; equivalent to convolving A160552: (1, 1, 3, 1, 3, 5, 7, ...) with (1, 2, 2, 2, ...). Equals A160762: (1, 0, 2, -2, 2, 2, 2, -6, ...) convolved with 2*n - 1: (1, 3, 5, 7, ...). Starting with offset 1 equals A151548: [1, 3, 5, 7, 5, 11, 17, 15, ...] convolved with A078008 signed (A151575): [1, 0, 2, -2, 6, -10, 22, -42, 86, -170, 342, ...]. - Gary W. Adamson, May 19 2009, May 25 2009
For a three-dimensional version of the toothpick structure, see A160160. - Omar E. Pol, Dec 06 2009
From Omar E. Pol, May 20 2010: (Start)
Observation about the arrangement of rectangles:
It appears there is a nice pattern formed by distinct modular substructures: a central cross surrounded by asymmetrical crosses (or "hidden crosses") of distinct sizes and also by "nuclei" of crosses.
Conjectures: after 2^k stages, for k >= 2, and for m = 1 to k - 1, there are 4^(m-1) substructures of size s = k - m, where every substructure has 4*s rectangles. The total number of substructures is equal to (4^(k-1)-1)/3 = A002450(k-1). For example: If k = 5 (after 32 stages) we can see that:
a) There is a central cross, of size 4, with 16 rectangles.
b) There are four hidden crosses, of size 3, where every cross has 12 rectangles.
c) There are 16 hidden crosses, of size 2, where every cross has 8 rectangles.
d) There are 64 nuclei of crosses, of size 1, where every nucleus has 4 rectangles.
Hence the total number of substructures after 32 stages is equal to 85. Note that in every arm of every substructure, in the potential growth direction, the length of the rectangles are the powers of 2. (See illustrations in the links. See also A160124.) (End)
It appears that the number of grid points that are covered after n-th stage of the toothpick structure, assuming the toothpicks have length 2*k, is equal to (2*k-2)*a(n) + A147614(n), k > 0. See the formulas of A160420 and A160422. - Omar E. Pol, Nov 13 2010
Version "Gullwing": on the semi-infinite square grid, at stage 1, we place a horizontal "gull" with its vertices at [(-1, 2), (0, 1), (1, 2)]. At stage 2, we place two vertical gulls. At stage 3, we place four horizontal gulls. a(n) is also the number of gulls after n-th stage. For more information about the growth of gulls see A187220. - Omar E. Pol, Mar 10 2011
From Omar E. Pol, Mar 12 2011: (Start)
Version "I-toothpick": we define an "I-toothpick" to consist of two connected toothpicks, as a bar of length 2. An I-toothpick with length 2 is formed by two toothpicks with length 1. The midpoint of an I-toothpick is touched by its two toothpicks. a(n) is also the number of I-toothpicks after n-th stage in the I-toothpick structure. The I-toothpick structure is essentially the original toothpick structure in which every toothpick is replaced by an I-toothpick. Note that in the physical model of the original toothpick structure the midpoint of a wooden toothpick of the new generation is superimposed on the endpoint of a wooden toothpick of the old generation. However, in the physical model of the I-toothpick structure the wooden toothpicks are not overlapping because all wooden toothpicks are connected by their endpoints. For the number of toothpicks in the I-toothpick structure see A160164 which also gives the number of gullwing in a gullwing structure because the gullwing structure of A160164 is equivalent to the I-toothpick structure. It also appears that the gullwing sequence A187220 is a supersequence of the original toothpick sequence A139250 (this sequence).
For the connection with the Ulam-Warburton cellular automaton see the Applegate-Pol-Sloane paper and see also A160164 and A187220.
(End)
A version in which the toothpicks are connected by their endpoints: on the semi-infinite square grid, at stage 1, we place a vertical toothpick of length 1 from (0, 0). At stage 2, we place two horizontal toothpicks from (0,1), and so on. The arrangement looks like half of the I-toothpick structure. a(n) is also the number of toothpicks after the n-th. - Omar E. Pol, Mar 13 2011
Version "Quarter-circle" (or Q-toothpick): a(n) is also the number of Q-toothpicks after the n-th stage in a Q-toothpick structure in the first quadrant. We start from (0,1) with the first Q-toothpick centered at (1, 1). The structure is asymmetric. For a similar structure but starting from (0, 0) see A187212. See A187210 and A187220 for more information. - Omar E. Pol, Mar 22 2011
Version "Tree": It appears that a(n) is also the number of toothpicks after the n-th stage in a toothpick structure constructed following a special rule: the toothpicks of the new generation have length 4 when they are placed on the infinite square grid (note that every toothpick has four components of length 1), but after every stage, one (or two) of the four components of every toothpick of the new generation is removed, if such component contains an endpoint of the toothpick and if such endpoint is touching the midpoint or the endpoint of another toothpick. The truncated endpoints of the toothpicks remain exposed forever. Note that there are three sizes of toothpicks in the structure: toothpicks of lengths 4, 3 and 2. A159795 gives the total number of components in the structure after the n-th stage. A153006 (the corner sequence of the original version) gives 1/4 of the total of components in the structure after the n-th stage. - Omar E. Pol, Oct 24 2011
From Omar E. Pol, Sep 16 2012: (Start)
It appears that a(n)/A147614(n) converges to 3/4.
It appears that a(n)/A160124(n) converges to 3/2.
It appears that a(n)/A139252(n) converges to 3.
Also:
It appears that A147614(n)/A160124(n) converges to 2.
It appears that A160124(n)/A139252(n) converges to 2.
It appears that A147614(n)/A139252(n) converges to 4.
(End)
It appears that a(n) is also the total number of ON cells after n-th stage in a quadrant of the structure of the cellular automaton described in A169707 plus the total number of ON cells after n+1 stages in a quadrant of the mentioned structure, without its central cell. See the illustration of the NW-NE-SE-SW version in A169707. See also the connection between A160164 and A169707. - Omar E. Pol, Jul 26 2015
On the infinite Cairo pentagonal tiling consider the symmetric figure formed by two non-adjacent pentagons connected by a line segment joining two trivalent nodes. At stage 1 we start with one of these figures turned ON. The rule for the next stages is that the concave part of the figures of the new generation must be adjacent to the complementary convex part of the figures of the old generation. a(n) gives the number of figures that are ON in the structure after n-th stage. A160164(n) gives the number of ON cells in the structure after n-th stage. - Omar E. Pol, Mar 29 2018
From Omar E. Pol, Mar 06 2019: (Start)
The "word" of this sequence is "ab". For further information about the word of cellular automata see A296612.
Version "triangular grid": a(n) is also the total number of toothpicks of length 2 after n-th stage in the toothpick structure on the infinite triangular grid, if we use only two of the three axes. Otherwise, if we use the three axes, so we have the sequence A296510 which has word "abc".
The normal toothpick structure can be considered a superstructure of the Ulam-Warburton celular automaton since A147562(n) equals here the total number of "hidden crosses" after 4*n stages, including the central cross (beginning to count the crosses when their "nuclei" are totally formed with 4 quadrilaterals). Note that every quadrilateral in the structure belongs to a "hidden cross".
Also, the number of "hidden crosses" after n stages equals the total number of "flowers with six petals" after n-th stage in the structure of A323650, which appears to be a "missing link" between this sequence and A147562.
Note that the location of the "nuclei of the hidden crosses" is very similar (essentially the same) to the location of the "flowers with six petals" in the structure of A323650 and to the location of the "ON" cells in the version "one-step bishop" of the Ulam-Warburton cellular automaton of A147562. (End)
From Omar E. Pol, Nov 27 2020: (Start)
The simplest substructures are the arms of the hidden crosses. Each closed region (square or rectangle) of the structure belongs to one of these arms. The narrow arms have regions of area 1, 2, 4, 8, ... The broad arms have regions of area 2, 4, 8, 16 , ... Note that after 2^k stages, with k >= 3, the narrow arms of the main hidden crosses in each quadrant frame the size of the toothpick structure after 2^(k-1) stages.
Another kind of substructure could be called "bar chart" or "bar graph". This substructure is formed by the rectangles and squares of width 2 that are adjacent to any of the four sides of the toothpick structure after 2^k stages, with k >= 2. The height of these successive regions gives the first 2^(k-1) - 1 terms from A006519. For example: if k = 5 the respective heights after 32 stages are [1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1]. The area of these successive regions gives the first 2^(k-1) - 1 terms of A171977. For example: if k = 5 the respective areas are [2, 4, 2, 8, 2, 4, 2, 16, 2, 4, 2, 8, 2, 4, 2].
For a connection to Mersenne primes (A000668) and perfect numbers (A000396) see A153006.
For a representation of the Wagstaff primes (A000979) using the toothpick structure see A194810.
For a connection to stained glass windows and a hidden curve see A336532. (End)
It appears that the graph of a(n) bears a striking resemblance to the cumulative distribution function F(x) for X the random variable taking values in [0,1], where the binary expansion of X is given by a sequence of independent coin tosses with probability 3/4 of being 1 at each bit. It appears that F(n/2^k)*(2^(2k+1)+1)/3 approaches a(n) for k large. - James Coe, Jan 10 2022

Examples

			a(10^10) = 52010594272060810683. - _David A. Corneth_, Mar 26 2015

References

  • D. Applegate, Omar E. Pol and N. J. A. Sloane, The Toothpick Sequence and Other Sequences from Cellular Automata, Congressus Numerantium, Vol. 206 (2010), 157-191
  • L. D. Pryor, The Inheritance of Inflorescence Characters in Eucalyptus, Proceedings of the Linnean Society of New South Wales, V. 79, (1954), p. 81, 83.
  • Richard P. Stanley, Enumerative Combinatorics, volume 1, second edition, chapter 1, exercise 95, figure 1.28, Cambridge University Press (2012), p. 120, 166.

Links

Crossrefs

Cf. A000079, A002450, A006519, A139251, A139252, A139253, A147614, A139560, A152968, A152978, A152980, A152998, A153000, A153001, A153003, A153004, A153006, A153007, A000217, A007583, A007683, A000396, A000225, A000668, A006516, A006095, A019988, A160570, A160552, A000969, A001316, A151566, A160406, A160408, A160702, A078008, A151548, A001045, A147562, A160124, A160120, A160160, A160170, A160172, A161206, A161328, A161330, A171977, A194810, A296510, A296612, A299476, A299478, A323650, A336532.

Programs

  • Maple
    G := (x/((1-x)*(1+2*x))) * (1 + 2*x*mul(1+x^(2^k-1)+2*x^(2^k),k=0..20)); # N. J. A. Sloane, May 20 2009, Jun 05 2009
# From N. J. A. Sloane, Dec 25 2009: A139250 is T, A139251 is a.
a:=[0,1,2,4]; T:=[0,1,3,7]; M:=10;
for k from 1 to M do
a:=[op(a),2^(k+1)];
T:=[op(T),T[nops(T)]+a[nops(a)]];
for j from 1 to 2^(k+1)-1 do
a:=[op(a), 2*a[j+1]+a[j+2]];
T:=[op(T),T[nops(T)]+a[nops(a)]];
od: od: a; T;
  • Mathematica
    CoefficientList[ Series[ (x/((1 - x)*(1 + 2x))) (1 + 2x*Product[1 + x^(2^k - 1) + 2*x^(2^k), {k, 0, 20}]), {x, 0, 53}], x] (* Robert G. Wilson v, Dec 06 2010 *)
a[0] = 0; a[n_] := a[n] = Module[{m, k}, m = 2^(Length[IntegerDigits[n, 2]] - 1); k = (2m^2+1)/3; If[n == m, k, k + 2 a[n - m] + a[n - m + 1] - 1]]; Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Oct 06 2018, after David A. Corneth *)
  • PARI
    A139250(n,print_all=0)={my(p=[], /* set of "used" points. Points are written as complex numbers, c=x+iy. Toothpicks are of length 2 */
ee=[[0,1]], /* list of (exposed) endpoints. Exposed endpoints are listed as [c,d] where c=x+iy is the position of the endpoint, and d (unimodular) is the direction */
c,d,ne, cnt=1); print_all && print1("0,1"); n<2 && return(n);
for(i=2,n, p=setunion(p, Set(Mat(ee~)[,1])); /* add endpoints (discard directions) from last move to "used" points */
ne=[]; /* new (exposed) endpoints */
for( k=1, #ee, /* add endpoints of new toothpicks if not among the used points */
setsearch(p, c=ee[k][1]+d=ee[k][2]*I) || ne=setunion(ne,Set([[c,d]]));
setsearch(p, c-2*d) || ne=setunion(ne,Set([[c-2*d,-d]]));
); /* using Set() we have the points sorted, so it's easy to remove those which finally are not exposed because they touch a new toothpick */
forstep( k=#ee=eval(ne), 2, -1, ee[k][1]==ee[k-1][1] && k-- && ee=vecextract(ee,Str("^"k"..",k+1)));
cnt+=#ee; /* each exposed endpoint will give a new toothpick */
print_all && print1(","cnt));cnt} \\ M. F. Hasler, Apr 14 2009
  • PARI
    \\works for n > 0
a(n) = {my(k = (2*msb(n)^2 + 1) / 3); if(n==msb(n),k , k + 2*a(n-msb(n)) + a(n - msb(n) + 1) - 1)}
msb(n)=my(t=0);while(n>>t>0,t++);2^(t-1)\\ David A. Corneth, Mar 26 2015
  • Python
    def msb(n):
    t = 0
    while n>>t > 0:
        t += 1
    return 2**(t - 1)
def a(n):
    k = (2 * msb(n)**2 + 1) / 3
    return 0 if n == 0 else k if n == msb(n) else k + 2*a(n - msb(n)) + a(n - msb(n) + 1) - 1
[a(n) for n in range(101)]  # Indranil Ghosh, Jul 01 2017, after David A. Corneth's PARI script

Formula

a(2^k) = A007583(k), if k >= 0.
a(2^k-1) = A006095(k+1), if k >= 1.
a(A000225(k)) - a((A000225(k)-1)/2) = A006516(k), if k >= 1.
a(A000668(k)) - a((A000668(k)-1)/2) = A000396(k), if k >= 1.
G.f.: (x/((1-x)*(1+2*x))) * (1 + 2*x*Product_{k>=0} (1 + x^(2^k-1) + 2*x^(2^k))). - N. J. A. Sloane, May 20 2009, Jun 05 2009
One can show that lim sup a(n)/n^2 = 2/3, and it appears that lim inf a(n)/n^2 is 0.451... - Benoit Jubin, Apr 15 2009 and Jan 29 2010, N. J. A. Sloane, Jan 29 2010
Observation: a(n) == 3 (mod 4) for n >= 2. - Jaume Oliver Lafont, Feb 05 2009
a(2^k-1) = A000969(2^k-2), if k >= 1. - Omar E. Pol, Feb 13 2010
It appears that a(n) = (A187220(n+1) - 1)/2. - Omar E. Pol, Mar 08 2011
a(n) = 4*A153000(n-2) + 3, if n >= 2. - Omar E. Pol, Oct 01 2011
It appears that a(n) = A160552(n) + (A169707(n) - 1)/2, n >= 1. - Omar E. Pol, Feb 15 2015
It appears that a(n) = A255747(n) + A255747(n-1), n >= 1. - Omar E. Pol, Mar 16 2015
Let n = msb(n) + j where msb(n) = A053644(n) and let a(0) = 0. Then a(n) = (2 * msb(n)^2 + 1)/3 + 2 * a(j) + a(j+1) - 1. - David A. Corneth, Mar 26 2015
It appears that a(n) = (A169707(n) - 1)/4 + (A169707(n+1) - 1)/4, n >= 1. - Omar E. Pol, Jul 24 2015

Extensions

Verified and extended, a(49)-a(53), using the given PARI code by M. F. Hasler, Apr 14 2009
Edited by N. J. A. Sloane, Apr 29 2009, incorporating comments from Omar E. Pol, M. F. Hasler, Rob Pratt, Jaume Oliver Lafont, Franklin T. Adams-Watters, R. J. Mathar, David W. Wilson, David Applegate, Benoit Jubin and others.
Further edited by N. J. A. Sloane, Jan 28 2010

A006519 Highest power of 2 dividing n.

Original entry on oeis.org

1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 16, 1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 32, 1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 16, 1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 64, 1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 16, 1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 32, 1, 2, 1, 4, 1, 2
Offset: 1

Views

Author

N. J. A. Sloane, Simon Plouffe

Keywords

Comments

Least positive k such that m^k + 1 divides m^n + 1 (with fixed base m). - Vladimir Baltic, Mar 25 2002
To construct the sequence: start with 1, concatenate 1, 1 and double last term gives 1, 2. Concatenate those 2 terms, 1, 2, 1, 2 and double last term 1, 2, 1, 2 -> 1, 2, 1, 4. Concatenate those 4 terms: 1, 2, 1, 4, 1, 2, 1, 4 and double last term -> 1, 2, 1, 4, 1, 2, 1, 8, etc. - Benoit Cloitre, Dec 17 2002
a(n) = gcd(seq(binomial(2*n, 2*m+1)/2, m = 0 .. n - 1)) (odd numbered entries of even numbered rows of Pascal's triangle A007318 divided by 2), where gcd() denotes the greatest common divisor of a set of numbers. Due to the symmetry of the rows it suffices to consider m = 0 .. floor((n-1)/2). - Wolfdieter Lang, Jan 23 2004
Equals the continued fraction expansion of a constant x (cf. A100338) such that the continued fraction expansion of 2*x interleaves this sequence with 2's: contfrac(2*x) = [2; 1, 2, 2, 2, 1, 2, 4, 2, 1, 2, 2, 2, 1, 2, 8, 2, ...].
Simon Plouffe observes that this sequence and A003484 (Radon function) are very similar, the difference being all zeros except for every 16th term (see A101119 for nonzero differences). Dec 02 2004
This sequence arises when calculating the next odd number in a Collatz sequence: Next(x) = (3*x + 1) / A006519, or simply (3*x + 1) / BitAnd(3*x + 1, -3*x - 1). - Jim Caprioli, Feb 04 2005
a(n) = n if and only if n = 2^k. This sequence can be obtained by taking a(2^n) = 2^n in place of a(2^n) = n and using the same sequence building approach as in A001511. - Amarnath Murthy, Jul 08 2005
Also smallest m such that m + n - 1 = m XOR (n - 1); A086799(n) = a(n) + n - 1. - Reinhard Zumkeller, Feb 02 2007
Number of 1's between successive 0's in A159689. - Philippe Deléham, Apr 22 2009
Least number k such that all coefficients of k*E(n, x), the n-th Euler polynomial, are integers (cf. A144845). - Peter Luschny, Nov 13 2009
In the binary expansion of n, delete everything left of the rightmost 1 bit. - Ralf Stephan, Aug 22 2013
The equivalent sequence for partitions is A194446. - Omar E. Pol, Aug 22 2013
Also the 2-adic value of 1/n, n >= 1. See the Mahler reference, definition on p. 7. This is a non-archimedean valuation. See Mahler, p. 10. Sometimes called 2-adic absolute value of 1/n. - Wolfdieter Lang, Jun 28 2014
First 2^(k-1) - 1 terms are also the heights of the successive rectangles and squares of width 2 that are adjacent to any of the four sides of the toothpick structure of A139250 after 2^k stages, with k >= 2. For example: if k = 5 the heights after 32 stages are [1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1] respectively, the same as the first 15 terms of this sequence. - Omar E. Pol, Dec 29 2020

Examples

			2^3 divides 24, but 2^4 does not divide 24, so a(24) = 8.
2^0 divides 25, but 2^1 does not divide 25, so a(25) = 1.
2^1 divides 26, but 2^2 does not divide 26, so a(26) = 2.
Per _Marc LeBrun_'s 2000 comment, a(n) can also be determined with bitwise operations in two's complement. For example, given n = 48, we see that n in binary in an 8-bit byte is 00110000 while -n is 11010000. Then 00110000 AND 11010000 = 00010000, which is 16 in decimal, and therefore a(48) = 16.
G.f. = x + 2*x^2 + x^3 + 4*x^4 + x^5 + 2*x^6 + x^7 + 8*x^8 + x^9 + ...

References

  • Kurt Mahler, p-adic numbers and their functions, second ed., Cambridge University Press, 1981.
  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Crossrefs

Partial sums are in A006520, second partial sums in A022560.
Sequences used in definitions of this sequence: A000079, A001511, A004198, A007814.
Cf. A000265, A100338, A003484, A001620, A101119, A002487, A139250.
Sequences with related definitions: A038712, A171977, A135481 (GS(1, 6)).
This is Guy Steele's sequence GS(5, 2) (see A135416).
Related to A007913 via A225546.
A059897 is used to express relationship between sequence terms.
Cf. A091476 (Dgf at s=2).

Programs

  • Haskell
    import Data.Bits ((.&.))
a006519 n = n .&. (-n) :: Integer
-- Reinhard Zumkeller, Mar 11 2012, Dec 29 2011
  • Julia
    using IntegerSequences
[EvenPart(n) for n in 1:102] |> println  # Peter Luschny, Sep 25 2021
  • Magma
    [2^Valuation(n, 2): n in [1..100]]; // Vincenzo Librandi, Mar 27 2015
  • Maple
    with(numtheory): for n from 1 to 200 do if n mod 2 = 1 then printf(`%d,`,1) else printf(`%d,`,2^ifactors(n)[2][1][2]) fi; od:
A006519 := proc(n) if type(n,'odd') then 1 ; else for f in ifactors(n)[2] do if op(1,f) = 2 then return 2^op(2,f) ; end if; end do: end if; end proc: # R. J. Mathar, Oct 25 2010
A006519 := n -> 2^padic[ordp](n,2): # Peter Luschny, Nov 26 2010
  • Mathematica
    lowestOneBit[n_] := Block[{k = 0}, While[Mod[n, 2^k] == 0, k++]; 2^(k - 1)]; Table[lowestOneBit[n], {n, 102}] (* Robert G. Wilson v Nov 17 2004 *)
Table[2^IntegerExponent[n, 2], {n, 128}] (* Jean-François Alcover, Feb 10 2012 *)
Table[BitAnd[BitNot[i - 1], i], {i, 1, 102}] (* Peter Luschny, Oct 10 2019 *)
  • PARI
    {a(n) = 2^valuation(n, 2)};
  • PARI
    a(n)=1<Joerg Arndt, Jun 10 2011
  • PARI
    a(n)=bitand(n,-n); \\ Joerg Arndt, Jun 10 2011
  • PARI
    a(n)=direuler(p=2,n,if(p==2,1/(1-2*X),1/(1-X)))[n] \\ Ralf Stephan, Mar 27 2015
  • Python
    def A006519(n): return n&-n # Chai Wah Wu, Jul 06 2022
  • Scala
    (1 to 128).map(Integer.lowestOneBit()) // _Alonso del Arte, Mar 04 2020

Formula

a(n) = n AND -n (where "AND" is bitwise, and negative numbers are represented in two's complement in a suitable bit width). - Marc LeBrun, Sep 25 2000, clarified by Alonso del Arte, Mar 16 2020
Also: a(n) = gcd(2^n, n). - Labos Elemer, Apr 22 2003
Multiplicative with a(p^e) = p^e if p = 2; 1 if p > 2. - David W. Wilson, Aug 01 2001
G.f.: Sum_{k>=0} 2^k*x^2^k/(1 - x^2^(k+1)). - Ralf Stephan, May 06 2003
Dirichlet g.f.: zeta(s)*(2^s - 1)/(2^s - 2) = zeta(s)*(1 - 2^(-s))/(1 - 2*2^(-s)). - Ralf Stephan, Jun 17 2007
a(n) = 2^floor(A002487(n - 1) / A002487(n)). - Reikku Kulon, Oct 05 2008
a(n) = 2^A007814(n). - R. J. Mathar, Oct 25 2010
a((2*k - 1)*2^e) = 2^e, k >= 1, e >= 0. - Johannes W. Meijer, Jun 07 2011
a(n) = denominator of Euler(n-1, 1). - Arkadiusz Wesolowski, Jul 12 2012
a(n) = A011782(A001511(n)). - Omar E. Pol, Sep 13 2013
a(n) = (n XOR floor(n/2)) XOR (n-1 XOR floor((n-1)/2)) = n - (n AND n-1) (where "AND" is bitwise). - Gary Detlefs, Jun 12 2014
a(n) = ((n XOR n-1)+1)/2. - Gary Detlefs, Jul 02 2014
a(n) = A171977(n)/2. - Peter Kern, Jan 04 2017
a(n) = 2^(A001511(n)-1). - Doug Bell, Jun 02 2017
a(n) = abs(A003188(n-1) - A003188(n)). - Doug Bell, Jun 02 2017
Conjecture: a(n) = (1/(A000203(2*n)/A000203(n)-2)+1)/2. - Velin Yanev, Jun 30 2017
a(n) = (n-1) o n where 'o' is the bitwise converse nonimplication. 'o' is not commutative. n o (n+1) = A135481(n). - Peter Luschny, Oct 10 2019
From Peter Munn, Dec 13 2019: (Start)
a(A225546(n)) = A225546(A007913(n)).
a(A059897(n,k)) = A059897(a(n), a(k)). (End)
Sum_{k=1..n} a(k) ~ (1/(2*log(2)))*n*log(n) + (3/4 + (gamma-1)/(2*log(2)))*n, where gamma is Euler's constant (A001620). - Amiram Eldar, Nov 15 2022
a(n) = n / A000265(n). - Amiram Eldar, May 22 2025

Extensions

More terms from James Sellers, Jun 20 2000

A003462 a(n) = (3^n - 1)/2.

Original entry on oeis.org

0, 1, 4, 13, 40, 121, 364, 1093, 3280, 9841, 29524, 88573, 265720, 797161, 2391484, 7174453, 21523360, 64570081, 193710244, 581130733, 1743392200, 5230176601, 15690529804, 47071589413, 141214768240, 423644304721, 1270932914164
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

Partial sums of A000244. Values of base 3 strings of 1's.
a(n) = (3^n-1)/2 is also the number of different nonparallel lines determined by pair of vertices in the n dimensional hypercube. Example: when n = 2 the square has 4 vertices and then the relevant lines are: x = 0, y = 0, x = 1, y = 1, y = x, y = 1-x and when we identify parallel lines only 4 remain: x = 0, y = 0, y = x, y = 1 - x so a(2) = 4. - Noam Katz (noamkj(AT)hotmail.com), Feb 11 2001
Also number of 3-block bicoverings of an n-set (if offset is 1, cf. A059443). - Vladeta Jovovic, Feb 14 2001
3^a(n) is the highest power of 3 dividing (3^n)!. - Benoit Cloitre, Feb 04 2002
Apart from the a(0) and a(1) terms, maximum number of coins among which a lighter or heavier counterfeit coin can be identified (but not necessarily labeled as heavier or lighter) by n weighings. - Tom Verhoeff, Jun 22 2002, updated Mar 23 2017
n such that A001764(n) is not divisible by 3. - Benoit Cloitre, Jan 14 2003
Consider the mapping f(a/b) = (a + 2b)/(2a + b). Taking a = 1, b = 2 to start with and carrying out this mapping repeatedly on each new (reduced) rational number gives the sequence 1/2, 4/5, 13/14, 40/41, ... converging to 1. Sequence contains the numerators = (3^n-1)/2. The same mapping for N, i.e., f(a/b) = (a + Nb)/(a+b) gives fractions converging to N^(1/2). - Amarnath Murthy, Mar 22 2003
Binomial transform of A000079 (with leading zero). - Paul Barry, Apr 11 2003
With leading zero, inverse binomial transform of A006095. - Paul Barry, Aug 19 2003
Number of walks of length 2*n + 2 in the path graph P_5 from one end to the other one. Example: a(2) = 4 because in the path ABCDE we have ABABCDE, ABCBCDE, ABCDCDE and ABCDEDE. - Emeric Deutsch, Apr 02 2004
The number of triangles of all sizes (not counting holes) in Sierpiński's triangle after n inscriptions. - Lee Reeves (leereeves(AT)fastmail.fm), May 10 2004
Number of (s(0), s(1), ..., s(2n+1)) such that 0 < s(i) < 6 and |s(i) - s(i-1)| = 1 for i = 1, 2, ..., 2*n + 1, s(0) = 1, s(2n+1) = 4. - Herbert Kociemba, Jun 10 2004
Number of non-degenerate right-angled incongruent integer-edged Heron triangles whose circumdiameter is the product of n distinct primes of shape 4k + 1. - Alex Fink and R. K. Guy, Aug 18 2005
Also numerator of the sum of the reciprocals of the first n powers of 3, with A000244 being the sequence of denominators. With the exception of n < 2, the base 10 digital root of a(n) is always 4. In base 3 the digital root of a(n) is the same as the digital root of n. - Alonso del Arte, Jan 24 2006
The sequence 3*a(n), n >= 1, gives the number of edges of the Hanoi graph H_3^{n} with 3 pegs and n >= 1 discs. - Daniele Parisse, Jul 28 2006
Numbers n such that a(n) is prime are listed in A028491 = {3, 7, 13, 71, 103, 541, 1091, ...}. 2^(m+1) divides a(2^m*k) for m > 0. 5 divides a(4k). 5^2 divides a(20k). 7 divides a(6k). 7^2 divides a(42k). 11^2 divides a(5k). 13 divides a(3k). 17 divides a(16k). 19 divides a(18k). 1093 divides a(7k). 41 divides a(8k). p divides a((p-1)/5) for prime p = {41, 431, 491, 661, 761, 1021, 1051, 1091, 1171, ...}. p divides a((p-1)/4) for prime p = {13, 109, 181, 193, 229, 277, 313, 421, 433, 541, ...}. p divides a((p-1)/3) for prime p = {61, 67, 73, 103, 151, 193, 271, 307, 367, ...} = A014753, 3 and -3 are both cubes (one implies other) mod these primes p = 1 mod 6. p divides a((p-1)/2) for prime p = {11, 13, 23, 37, 47, 59, 61, 71, 73, 83, 97, ...} = A097933(n). p divides a(p-1) for prime p > 7. p^2 divides a(p*(p-1)k) for all prime p except p = 3. p^3 divides a(p*(p-1)*(p-2)k) for prime p = 11. - Alexander Adamchuk, Jan 22 2007
Let P(A) be the power set of an n-element set A. Then a(n) = the number of [unordered] pairs of elements {x,y} of P(A) for which x and y are disjoint [and both nonempty]. Wieder calls these "disjoint usual 2-combinations". - Ross La Haye, Jan 10 2008 [This is because each of the elements of {1, 2, ..., n} can be in the first subset, in the second or in neither. Because there are three options for each, the total number of options is 3^n. However, since the sets being empty is not an option we subtract 1 and since the subsets are unordered we then divide by 2! (The number of ways two objects can be arranged.) Thus we obtain (3^n-1)/2 = a(n). - Chayim Lowen, Mar 03 2015]
Also, still with P(A) being the power set of a n-element set A, a(n) is the number of 2-element subsets {x,y} of P(A) such that the union of x and y is equal to A. Cf. A341590. - Fabio Visonà, Feb 20 2021
Starting with offset 1 = binomial transform of A003945: (1, 3, 6, 12, 24, ...) and double bt of (1, 2, 1, 2, 1, 2, ...); equals polcoeff inverse of (1, -4, 3, 0, 0, 0, ...). - Gary W. Adamson, May 28 2009
Also the constant of the polynomials C(x) = 3x + 1 that form a sequence by performing this operation repeatedly and taking the result at each step as the input at the next. - Nishant Shukla (n.shukla722(AT)gmail.com), Jul 11 2009
It appears that this is A120444(3^n-1) = A004125(3^n) - A004125(3^n-1), where A004125 is the sum of remainders of n mod k for k = 1, 2, 3, ..., n. - John W. Layman, Jul 29 2009
Subsequence of A134025; A171960(a(n)) = a(n). - Reinhard Zumkeller, Jan 20 2010
Let A be the Hessenberg matrix of order n, defined by: A[1,j] = 1, A[i, i] := 3, (i > 1), A[i, i-1] = -1, and A[i, j] = 0 otherwise. Then, for n >= 1, a(n) = det(A). - Milan Janjic, Jan 27 2010
This is the sequence A(0, 1; 2, 3; 2) = A(0, 1; 4, -3; 0) of the family of sequences [a, b:c, d:k] considered by Gary Detlefs, and treated as A(a, b; c, d; k) in the Wolfdieter Lang link given below. - Wolfdieter Lang, Oct 18 2010
It appears that if s(n) is a first order rational sequence of the form s(0) = 0, s(n) = (2*s(n-1)+1)/(s(n-1)+2), n > 0, then s(n)= a(n)/(a(n)+1). - Gary Detlefs, Nov 16 2010
This sequence also describes the total number of moves to solve the [RED ; BLUE ; BLUE] or [RED ; RED ; BLUE] pre-colored Magnetic Towers of Hanoi puzzle (cf. A183111 - A183125).
From Adi Dani, Jun 08 2011: (Start)
a(n) is number of compositions of odd numbers into n parts less than 3. For example, a(3) = 13 and there are 13 compositions odd numbers into 3 parts < 3:
1: (0, 0, 1), (0, 1, 0), (1, 0, 0);
3: (0, 1, 2), (0, 2, 1), (1, 0, 2), (1, 2, 0), (2, 0, 1), (2, 1, 0), (1, 1, 1);
5: (1, 2, 2), (2, 1, 2), (2, 2, 1).
(End)
Pisano period lengths: 1, 2, 1, 2, 4, 2, 6, 4, 1, 4, 5, 2, 3, 6, 4, 8, 16, 2, 18, 4, ... . - R. J. Mathar, Aug 10 2012
a(n) is the total number of holes (triangles removed) after the n-th step of a Sierpiński triangle production. - Ivan N. Ianakiev, Oct 29 2013
a(n) solves Sum_{j = a(n) + 1 .. a(n+1)} j = k^2 for some integer k, given a(0) = 0 and requiring smallest a(n+1) > a(n). Corresponding k = 3^n. - Richard R. Forberg, Mar 11 2015
a(n+1) equals the number of words of length n over {0, 1, 2, 3} avoiding 01, 02 and 03. - Milan Janjic, Dec 17 2015
For n >= 1, a(n) is also the total number of words of length n, over an alphabet of three letters, such that one of the letters appears an odd number of times (See A006516 for 4 letter words, and the Balakrishnan reference there). - Wolfdieter Lang, Jul 16 2017
Also, the number of maximal cliques, maximum cliques, and cliques of size 4 in the n-Apollonian network. - Andrew Howroyd, Sep 02 2017
For n > 1, the number of triangles (cliques of size 3) in the (n-1)-Apollonian network. - Andrew Howroyd, Sep 02 2017
a(n) is the largest number that can be represented with n trits in balanced ternary. Correspondingly, -a(n) is the smallest number that can be represented with n trits in balanced ternary. - Thomas König, Apr 26 2020
These form Sierpinski nesting-stars, which alternate pattern on 3^n+1/2 star numbers A003154, based on the square configurations of 9^n. The partial sums of 3^n are delineated according to the geometry of a hexagram, see illustrations in links. (3*a(n-1) + 1) create Sierpinski-anti-triangles, representing the number of holes in a (n+1) Sierpinski triangle (see illustrations). - John Elias, Oct 18 2021
For n > 1, a(n) is the number of iterations necessary to calculate the hyperbolic functions with CORDIC. - Mathias Zechmeister, Jul 26 2022
a(n) is the least number k such that A065363(k) = n. - Amiram Eldar, Sep 03 2022
For all n >= 0, Sum_{k=a(n)+1..a(n+1)} 1/k < Sum_{j=a(n+1)+1..a(n+2)} 1/j. These are the minimal points which partition the infinite harmonic series into a monotonically increasing sequence. Each partition approximates log(3) from below as n tends to infinity. - Joseph Wheat, Apr 15 2023
a(n) is also the number of 3-cycles in the n-Dorogovtsev-Goltsev-Mendes graph (using the convention the 0-Dorogovtsev-Goltsev-Mendes graph is P_2). - Eric W. Weisstein, Dec 06 2023

Examples

			There are 4 3-block bicoverings of a 3-set: {{1, 2, 3}, {1, 2}, {3}}, {{1, 2, 3}, {1, 3}, {2}}, {{1, 2, 3}, {1}, {2, 3}} and {{1, 2}, {1, 3}, {2, 3}}.
Ternary........Decimal
0.................0
1.................1
11................4
111..............13
1111.............40 etc. - _Zerinvary Lajos_, Jan 14 2007
There are altogether a(3) = 13 three letter words over {A,B,C} with say, A, appearing an odd number of times: AAA; ABC, ACB, ABB, ACC; BAC, CAB, BAB, CAC; BCA, CBA, BBA, CCA. - _Wolfdieter Lang_, Jul 16 2017

References

  • J. G. Mauldon, Strong solutions for the counterfeit coin problem, IBM Research Report RC 7476 (#31437) 9/15/78, IBM Thomas J. Watson Research Center, P. O. Box 218, Yorktown Heights, N. Y. 10598.
  • Paulo Ribenboim, The Book of Prime Number Records, Springer-Verlag, NY, 2nd ed., 1989, p. 60.
  • Paulo Ribenboim, The Little Book of Big Primes, Springer-Verlag, NY, 1991, p. 53.
  • Amir Sapir, The Tower of Hanoi with Forbidden Moves, The Computer J. 47 (1) (2004) 20, case three-in-a row, sequence a(n).
  • Robert Sedgewick, Algorithms, 1992, pp. 109.
  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Crossrefs

Sequences used for Shell sort: A033622, A003462, A036562, A036564, A036569, A055875.
Cf. A179526 (repeats), A113047 (characteristic function).
Cf. A000225, A000392, A004125, A014753, A028491 (indices of primes), A059443 (column k = 3), A065363, A097933, A120444, A321872 (sum reciprocals).
Cf. A064099 (minimal number of weightings to detect lighter or heavier coin among n coins).
Cf. A039755 (column k = 1).
Cf. A006516 (binomial transform, and special 4 letter words).
Cf. A341590.
Cf. A003462(n) (3-cycles), A367967(n) (5-cycles), A367968(n) (6-cycles).

Programs

Formula

G.f.: x/((1-x)*(1-3*x)).
a(n) = 4*a(n-1) - 3*a(n-2), n > 1. a(0) = 0, a(1) = 1.
a(n) = 3*a(n-1) + 1, a(0) = 0.
E.g.f.: (exp(3*x) - exp(x))/2. - Paul Barry, Apr 11 2003
a(n+1) = Sum_{k = 0..n} binomial(n+1, k+1)*2^k. - Paul Barry, Aug 20 2004
a(n) = Sum_{i = 0..n-1} 3^i, for n > 0; a(0) = 0.
a(n) = A125118(n, 2) for n > 1. - Reinhard Zumkeller, Nov 21 2006
a(n) = StirlingS2(n+1, 3) + StirlingS2(n+1, 2). - Ross La Haye, Jan 10 2008
a(n) = Sum_{k = 0..n} A106566(n, k)*A106233(k). - Philippe Deléham, Oct 30 2008
a(n) = 2*a(n-1) + 3*a(n-2) + 2, n > 1. - Gary Detlefs, Jun 21 2010
a(n) = 3*a(n-1) + a(n-2) - 3*a(n-3) = 5*a(n-1) - 7*a(n-2) + 3*a(n-3), a(0) = 0, a(1) = 1, a(2) = 4. Observation by G. Detlefs. See the W. Lang comment and link. - Wolfdieter Lang, Oct 18 2010
A008344(a(n)) = 0, for n > 1. - Reinhard Zumkeller, May 09 2012
A085059(a(n)) = 1 for n > 0. - Reinhard Zumkeller, Jan 31 2013
G.f.: Q(0)/2 where Q(k) = 1 - 1/(9^k - 3*x*81^k/(3*x*9^k - 1/(1 - 1/(3*9^k - 27*x*81^k/(9*x*9^k - 1/Q(k+1)))))); (continued fraction ). - Sergei N. Gladkovskii, Apr 12 2013
a(n) = A001065(3^n) where A001065(m) is the sum of the proper divisors of m for positive integer m. - Chayim Lowen, Mar 03 2015
a(n) = A000244(n) - A007051(n) = A007051(n)-1. - Yuchun Ji, Oct 23 2018
Sum_{n>=1} 1/a(n) = A321872. - Amiram Eldar, Nov 18 2020

Extensions

More terms from Michael Somos
Corrected my comment of Jan 10 2008. - Ross La Haye, Oct 29 2008
Removed comment that duplicated a formula. - Joerg Arndt, Mar 11 2010

A139251 First differences of toothpicks numbers A139250.

Original entry on oeis.org

0, 1, 2, 4, 4, 4, 8, 12, 8, 4, 8, 12, 12, 16, 28, 32, 16, 4, 8, 12, 12, 16, 28, 32, 20, 16, 28, 36, 40, 60, 88, 80, 32, 4, 8, 12, 12, 16, 28, 32, 20, 16, 28, 36, 40, 60, 88, 80, 36, 16, 28, 36, 40, 60, 88, 84, 56, 60, 92, 112, 140, 208, 256, 192, 64, 4, 8, 12, 12, 16, 28, 32, 20, 16, 28
Offset: 0

Views

Author

Omar E. Pol, Apr 24 2008

Keywords

Comments

Number of toothpicks added to the toothpick structure at the n-th step (see A139250).
It appears that if n is equal to 1 plus a power of 2 with positive exponent then a(n) = 4. (For proof see the second Applegate link.)
It appears that there is a relation between this sequence, even superperfect numbers, Mersenne primes and even perfect numbers. Conjecture: The sum of the toothpicks added to the toothpick structure between the stage A061652(k) and the stage A000668(k) is equal to the k-th even perfect number, for k >= 1. For example: A000396(1) = 2+4 = 6. A000396(2) = 4+4+8+12 = 28. A000396(3) = 16+4+8+12+12+16+28+32+20+16+28+36+40+60+88+80 = 496. - Omar E. Pol, May 04 2009
Concerning this conjecture, see David Applegate's comments on the conjectures in A153006. - N. J. A. Sloane, May 14 2009
In the triangle (See example lines), the sum of row k is equal to A006516(k), for k >= 1. - Omar E. Pol, May 15 2009
Equals (1, 2, 2, 2, ...) convolved with A160762: (1, 0, 2, -2, 2, 2, 2, -6, ...). - Gary W. Adamson, May 25 2009
Convolved with the Jacobsthal sequence A001045 = A160704: (1, 3, 9, 19, 41, ...). - Gary W. Adamson, May 24 2009
It appears that the sums of two successive terms of A160552 give the positive terms of this sequence. - Omar E. Pol, Feb 19 2015
From Omar E. Pol, Feb 28 2019: (Start)
The study of the toothpick automaton on triangular grid (A296510), and other C.A. of the same family, reveals that some cellular automata that have recurrent periods can be represented in general by irregular triangles (of first differences) whose row lengths are the terms of A011782 multiplied by k, where k >= 1, is the length of an internal cycle. This internal cycle is called "word" of a cellular automaton. For example: A160121 has word "a", so k = 1. This sequence has word "ab", so k = 2. A296511 has word "abc", so k = 3. A299477 has word "abcb" so k = 4. A299479 has word "abcbc", so k = 5.
The structure of this triangle (with word "ab" and k = 2) for the nonzero terms is as follows:
a,b;
a,b;
a,b,a,b;
a,b,a,b,a,b,a,b;
a,b,a,b,a,b,a,b,a,b,a,b,a,b,a,b;
...
The row lengths are the terms of A011782 multiplied by 2, equaling the column 2 of the square array A296612: 2, 2, 4, 8, 16, ...
This arrangement has the property that the odd-indexed columns (a) contain numbers of the toothpicks that are parallel to initial toothpick, and the even-indexed columns (b) contain numbers of the toothpicks that are orthogonal to the initial toothpick (see the third triangle in the Example section).
An associated sound to the animation could be (tick, tock), (tick, tock), ..., the same as the ticking clock sound.
For further information about the "word" of a cellular automaton see A296612. (End)

Examples

			From _Omar E. Pol_, Dec 16 2008: (Start)
Triangle begins:
1;
2;
4,4;
4,8,12,8;
4,8,12,12,16,28,32,16;
4,8,12,12,16,28,32,20,16,28,36,40,60,88,20,32;
(End)
From _David Applegate_, Apr 29 2009: (Start)
The layout of the triangle was adjusted to reveal that the columns become constant as shown below:
. 0;
. 1;
. 2,4;
. 4,4,8,12;
. 8,4,8,12,12,16,28,32;
.16,4,8,12,12,16,28,32,20,16,28,36,40,60,88,80;
.32,4,8,12,12,16,28,32,20,16,28,36,40,60,88,80,36,16,28,36,40,60,88,84,56,...
...
The row sums give A006516.
(End)
From _Omar E. Pol_, Feb 28 2018: (Start)
Also the nonzero terms can write as an irregular triangle in which the row lengths are the terms of A011782 multiplied by 2 as shown below:
1,2;
4,4;
4,8,12,8;
4,8,12,12,16,28,32,16;
4,8,12,12,16,28,32,20,16,28,36,40,60,88,20,32;
...
(End)

Links

Crossrefs

Equals 2*A152968 and 4*A152978 (if we ignore the first couple of terms).
See A147646 for the limiting behavior of the rows. See also A006516.
Row lengths in A011782.
Cf. A139250, A139252, A139253, A152980, A153000, A153001, A000396, A000668, A061652, A153006.
Cf. A006516, A153007, A159790, A001045, A160704, A160762, A147582, A296612.
Cf. A160121 (word "a"), A296511 (word "abc"), A299477 (word "abcb"), A299479 (word "abcbc").

Programs

  • Maple
    G := (x/(1+2*x)) * (1 + 2*x*mul(1+x^(2^k-1)+2*x^(2^k),k=0..20)); # N. J. A. Sloane, May 20 2009, Jun 05 2009
# A139250 is T, A139251 is a.
a:=[0,1,2,4]; T:=[0,1,3,7]; M:=10;
for k from 1 to M do
a:=[op(a),2^(k+1)];
T:=[op(T),T[nops(T)]+a[nops(a)]];
for j from 1 to 2^(k+1)-1 do
a:=[op(a), 2*a[j+1]+a[j+2]];
T:=[op(T),T[nops(T)]+a[nops(a)]];
od: od: a; T;
# N. J. A. Sloane, Dec 25 2009
  • Mathematica
    CoefficientList[Series[((x - x^2)/((1 - x) (1 + 2 x))) (1 + 2 x Product[1 + x^(2^k - 1) + 2 x^(2^k), {k, 0, 20}]), {x, 0, 60}], x] (* Vincenzo Librandi, Aug 22 2014 *)

Formula

Recurrence from N. J. A. Sloane, Jul 20 2009: a(0) = 0; a(2^i)=2^i for all i; otherwise write n=2^i+j, 0 < j < 2^i, then a(n) = 2a(j)+a(j+1). Proof: This is a simplification of the following recurrence of David Applegate. QED
Recurrence from David Applegate, Apr 29 2009: (Start)
Write n=2^(i+1)+j, where 0 <= j < 2^(i+1). Then, for n > 3:
for j=0, a(n) = 2*a(n-2^i) (= n = 2^(i+1))
for 1 <= j <= 2^i - 1, a(n) = a(n-2^i)
for j=2^i, a(n) = a(n-2^i)+4 (= 2^(i+1)+4)
for 2^i+1 <= j <= 2^(i+1)-2, a(n) = 2*a(n-2^i) + a(n-2^i+1)
for j=2^(i+1)-1, a(n) = 2*a(n-2^i) + a(n-2^i+1)-4
and a(n) = 2^(n-1) for n=1,2,3. (End)
G.f.: (x/(1+2*x)) * (1 + 2*x*Product_{k>=0} (1 + x^(2^k-1) + 2*x^(2^k))). - N. J. A. Sloane, May 20 2009, Jun 05 2009
With offset 0 (which would be more natural, but offset 1 is now entrenched): a(0) = 1, a(1) = 2; for i >= 1, a(2^i) = 4; otherwise write n = 2^i +j, 0 < j < 2^i, then a(n) = 2 * Sum_{ k >= 0 } 2^(wt(j+k)-k)*binomial(wt(j+k),k). - N. J. A. Sloane, Jun 03 2009
It appears that a(n) = A187221(n+1)/2. - Omar E. Pol, Mar 08 2011
It appears that a(n) = A160552(n-1) + A160552(n), n >= 1. - Omar E. Pol, Feb 18 2015

Extensions

Partially edited by Omar E. Pol, Feb 28 2019
Showing 1-10 of 132 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.