A006943 -id:A006943 - cp's OEIS frontend

A000215 Fermat numbers: a(n) = 2^(2^n) + 1.

3, 5, 17, 257, 65537, 4294967297, 18446744073709551617, 340282366920938463463374607431768211457, 115792089237316195423570985008687907853269984665640564039457584007913129639937

Offset: 0

N. J. A. Sloane

It is conjectured that just the first 5 numbers in this sequence are primes.
An infinite coprime sequence defined by recursion. - Michael Somos, Mar 14 2004
For n>0, Fermat numbers F(n) have digital roots 5 or 8 depending on whether n is even or odd (Koshy). - Lekraj Beedassy, Mar 17 2005
This is the special case k=2 of sequences with exact mutual k-residues. In general, a(1)=k+1 and a(n)=min{m | m>a(n-1), mod(m,a(i))=k, i=1,...,n-1}. k=1 gives Sylvester's sequence A000058. - Seppo Mustonen, Sep 04 2005
For n>1 final two digits of a(n) are periodically repeated with period 4: {17, 57, 37, 97}. - Alexander Adamchuk, Apr 07 2007
For 1 < k <= 2^n, a(A007814(k-1)) divides a(n) + 2^k. More generally, for any number k, let r = k mod 2^n and suppose r != 1, then a(A007814(r-1)) divides a(n) + 2^k. - T. D. Noe, Jul 12 2007
From Daniel Forgues, Jun 20 2011: (Start)
The Fermat numbers F_n are F_n(a,b) = a^(2^n) + b^(2^n) with a = 2 and b = 1.
For n >= 2, all factors of F_n = 2^(2^n) + 1 are of the form k*(2^(n+2)) + 1 (k >= 1).
The products of distinct Fermat numbers (in their binary representation, see A080176) give rows of Sierpiński's triangle (A006943). (End)
Let F(n) be a Fermat number. For n > 2, F(n) is prime if and only if 5^((F(n)-1)/4) == sqrt(F(n)-1) (mod F(n)). - Arkadiusz Wesolowski, Jul 16 2011
Conjecture: let the smallest prime factor of Fermat number F(n) be P(F(n)). If F(n) is composite, then P(F(n)) < 3*2^(2^n/2 - n - 2). - Arkadiusz Wesolowski, Aug 10 2012
The Fermat primes are not Brazilian numbers, so they belong to A220627, but the Fermat composites are Brazilian numbers so they belong to A220571. For a proof, see Proposition 3 page 36 on "Les nombres brésiliens" in Links. - Bernard Schott, Dec 29 2012
It appears that this sequence is generated by starting with a(0)=3 and following the rule "Write in binary and read in base 4".  For an example of "Write in binary and read in ternary", see A014118. - John W. Layman, Jul 30 2013
Conjecture: the numbers > 5 in this sequence, i.e., 2^2^k + 1 for k>1, are exactly the numbers n such that (n-1)^4-1 divides 2^(n-1)-1. - M. F. Hasler, Jul 24 2015

			a(0) = 1*2^1 + 1 = 3 = 1*(2*1) + 1.
a(1) = 1*2^2 + 1 = 5 = 1*(2*2) + 1.
a(2) = 1*2^4 + 1 = 17 = 2*(2*4) + 1.
a(3) = 1*2^8 + 1 = 257 = 16*(2*8) + 1.
a(4) = 1*2^16 + 1 = 65537 = 2048*(2*16) + 1.
a(5) = 1*2^32 + 1 = 4294967297 = 641*6700417 = (10*(2*32) + 1)*(104694*(2*32) + 1).
a(6) = 1*2^64 + 1 = 18446744073709551617 = 274177*67280421310721 = (2142*(2*64) + 1)*(525628291490*(2*64) + 1).

M. Aigner and G. M. Ziegler, Proofs from The Book, Springer-Verlag, Berlin, 2nd. ed., 2001; see p. 3.
T. M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976, page 7.
P. Bachmann, Niedere Zahlentheorie (1902, 1910), reprinted Chelsea, NY, 1968, vol. 2, p. 87.
James Gleick, Faster, Vintage Books, NY, 2000 (see pp. 259-261).
Jan Gullberg, Mathematics from the Birth of Numbers, W. W. Norton & Co., NY & London, 1997, §3.2 Prime Numbers, pp. 78-79.
R. K. Guy, Unsolved Problems in Number Theory, A3.
G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers. 3rd ed., Oxford Univ. Press, 1954, p. 14.
E. Hille, Analytic Function Theory, Vol. I, Chelsea, N.Y., see p. 64.
T. Koshy, "The Digital Root Of A Fermat Number", Journal of Recreational Mathematics Vol. 32 No. 2 2002-3 Baywood NY.
M. Krizek, F. Luca & L. Somer, 17 Lectures on Fermat Numbers, Springer-Verlag NY 2001.
C. S. Ogilvy and J. T. Anderson, Excursions in Number Theory, Oxford University Press, NY, 1966, p. 36.
Clifford A. Pickover, A Passion for Mathematics, Wiley, 2005; see pp. 18, 59.
C. A. Pickover, The Math Book, Sterling, NY, 2009; see p. 202.
Paulo Ribenboim, The Little Book of Bigger Primes, Springer-Verlag NY 2004. See pp. 6-7, 70-75.
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 136-137.
David Wells, The Penguin Dictionary of Curious and Interesting Numbers, Penguin Books, 1987, pp. 148-149.

N. J. A. Sloane, Table of n, a(n) for n = 0..11
Richard Bellman, A note on relatively prime sequences, Bull. Amer. Math. Soc. 53 (1947), 778-779.
Chris Bispels, Matthew Cohen, Joshua Harrington, Joshua Lowrance, Kaelyn Pontes, Leif Schaumann, and Tony W. H. Wong, A further investigation on covering systems with odd moduli, arXiv:2507.16135 [math.NT], 2025. See p. 3.
Chris K. Caldwell, The Prime Glossary, Fermat number.
Chris K. Caldwell, The prime pages All prime-square Mersenne divisors are Wieferich (2021).
Shane Chern, Fermat Numbers in Multinomial Coefficients, J. Int. Seq. 17 (2014) # 14.3.2.
Leonhard Euler, Observations on a theorem of Fermat and others on looking at prime numbers, arXiv:math/0501118 [math.HO], 2005-2008.
Leonhard Euler, Observationes de theoremate quodam Fermatiano aliisque ad numeros primos spectantibus.
Emmanuel Ferrand, Deformations of the Taylor Formula, Journal of Integer Sequences, Vol. 10 (2007), Article 07.1.7.
Richard K. Guy, The strong law of small numbers. Amer. Math. Monthly 95 (1988), no. 8, 697-712. [Annotated scanned copy]
Christian Kassel and Christophe Reutenauer, Pairs of intertwined integer sequences, arXiv:2507.15780 [math.NT], 2025. See p. 12.
Wilfrid Keller, Prime factors k.2^n + 1 of Fermat numbers F_m
Jiří Klaška, Jakóbczyk's Hypothesis on Mersenne Numbers and Generalizations of Skula's Theorem, J. Int. Seq., Vol. 26 (2023), Article 23.3.8.
T.-W. Leung, A Brief Introduction to Fermat Numbers
Romeo Meštrović, Euclid's theorem on the infinitude of primes: a historical survey of its proofs (300 BC--2012) and another new proof, arXiv preprint arXiv:1202.3670 [math.HO], 2012. - From _N. J. A. Sloane_, Jun 13 2012
Romeo Meštrović, Goldbach-type conjectures arising from some arithmetic progressions, University of Montenegro, 2018.
Romeo Meštrović, Goldbach's like conjectures arising from arithmetic progressions whose first two terms are primes, arXiv:1901.07882 [math.NT], 2019.
Michael A. Morrison and John Brillhart, The factorization of F_7, Bull. Amer. Math. Soc. 77 (1971), 264.
Robert Munafo, Fermat Numbers
Robert Munafo, Notes on Fermat numbers
Seppo Mustonen, On integer sequences with mutual k-residues.
Seppo Mustonen, On integer sequences with mutual k-residues. [Local copy]
OEIS Wiki, Fermat numbers.
OEIS Wiki, Sierpinski's triangle.
G. A. Paxson, The compositeness of the thirteenth Fermat number, Math. Comp. 15 (76) (1961) 420-420.
Carl Pomerance, A tale of two sieves, Notices Amer. Math. Soc., 43 (1996), 1473-1485.
P. Sanchez, PlanetMath.org, Fermat Numbers
Bernard Schott, Les nombres brésiliens, Quadrature, no. 76, avril-juin 2010, pages 30-38. Local copy, included here with permission from the editors of Quadrature.
G. Villemin's Almanach of Numbers, Nombres de Fermat.
Le Roy J. Warren, Henry G. Bray, On the square-freeness of Fermat and Mersenne Numbers, Pac. J. Math. 22 (3) (1967) 563.
Eric Weisstein's World of Mathematics, Fermat Number.
Eric Weisstein's World of Mathematics, Generalized Fermat Number.
Wikipedia, Fermat number.
Wolfram Research, Fermat numbers are pairwise coprime.

a(n) = A001146(n) + 1 = A051179(n) + 2.
Cf. A019434, A050922, A051158, A051179, A063486, A073617, A085866.
See A004249 for a similar sequence.
Cf. A080176 for binary representation of Fermat numbers.
Cf. A220627, A220570, A220571, A125134, A249119.
Cf. A000058, A000120, A000225, A006943, A007814, A014118, A077585, A242619, A242620, A257916, A257917.
Cf. A000058, A000120, A000225, A006943, A007814, A014118, A077585, A242619, A242620, A257916, A257917.

a000215 = (+ 1) . (2 ^) . (2 ^)  -- Reinhard Zumkeller, Feb 13 2015

Maple
```
A000215 := n->2^(2^n)+1;
```

Table[2^(2^n) + 1, {n, 0, 8}] (* Alonso del Arte, Jun 07 2011 *)

A000215(n):=2^(2^n)+1$ makelist(A000215(n),n,0,10); /* Martin Ettl, Dec 10 2012 */

PARI
```
a(n)=if(n<1,3*(n==0),(a(n-1)-1)^2+1)
```

def a(n): return 2**(2**n) + 1
print([a(n) for n in range(9)]) # Michael S. Branicky, Apr 19 2021

a(0) = 3; a(n) = (a(n-1)-1)^2 + 1, n >= 1.
a(n) = a(n-1)*a(n-2)*...*a(1)*a(0) + 2, n >= 0, where for n = 0, we get the empty product, i.e., 1, plus 2, giving 3 = a(0). - Benoit Cloitre, Sep 15 2002 [edited by Daniel Forgues, Jun 20 2011]
The above formula implies that the Fermat numbers (being all odd) are coprime.
Conjecture: F is a Fermat prime if and only if phi(F-2) = (F-1)/2. - Benoit Cloitre, Sep 15 2002
A000120(a(n)) = 2. - Reinhard Zumkeller, Aug 07 2010
If a(n) is composite, then a(n) = A242619(n)^2 + A242620(n)^2 = A257916(n)^2 - A257917(n)^2. - Arkadiusz Wesolowski, May 13 2015
Sum_{n>=0} 1/a(n) = A051158. - Amiram Eldar, Oct 27 2020
From Amiram Eldar, Jan 28 2021: (Start)
Product_{n>=0} (1 + 1/a(n)) = A249119.
Product_{n>=0} (1 - 1/a(n)) = 1/2. (End)
a(n) = 2*A077585(n) + 3. - César Aguilera, Jul 26 2023
a(n) = 2*2^A000225(n) + 1. - César Aguilera, Jul 11 2024

A047999 Sierpiński's [Sierpinski's] triangle (or gasket): triangle, read by rows, formed by reading Pascal's triangle (A007318) mod 2.

Original entry on oeis.org

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

Offset: 0

N. J. A. Sloane

Restored the alternative spelling of Sierpinski to facilitate searching for this triangle using regular-expression matching commands in ASCII. - N. J. A. Sloane, Jan 18 2016
Also triangle giving successive states of cellular automaton generated by "Rule 60" and "Rule 102". - Hans Havermann, May 26 2002
Also triangle formed by reading triangle of Eulerian numbers (A008292) mod 2. - Philippe Deléham, Oct 02 2003
Self-inverse when regarded as an infinite lower triangular matrix over GF(2).
Start with [1], repeatedly apply the map 0 -> [00/00], 1 -> [10/11] [Allouche and Berthe]
Also triangle formed by reading triangles A011117, A028338, A039757, A059438, A085881, A086646, A086872, A087903, A104219 mod 2. - Philippe Deléham, Jun 18 2005
J. H. Conway writes (in Math Forum): at least the first 31 rows give odd-sided constructible polygons (sides 1, 3, 5, 15, 17, ... see A001317). The 1's form a Sierpiński sieve. - M. Dauchez (mdzzdm(AT)yahoo.fr), Sep 19 2005
When regarded as an infinite lower triangular matrix, its inverse is a (-1,0,1)-matrix with zeros undisturbed and the nonzero entries in every column form the Prouhet-Thue-Morse sequence (1,-1,-1,1,-1,1,1,-1,...) A010060 (up to relabeling). - David Callan, Oct 27 2006
Triangle read by rows: antidiagonals of an array formed by successive iterates of running sums mod 2, beginning with (1, 1, 1, ...). - Gary W. Adamson, Jul 10 2008
T(n,k) = A057427(A143333(n,k)). - Reinhard Zumkeller, Oct 24 2010
The triangle sums, see A180662 for their definitions, link Sierpiński’s triangle A047999 with seven sequences, see the crossrefs. The Kn1y(n) and Kn2y(n), y >= 1, triangle sums lead to the Sierpiński-Stern triangle A191372. - Johannes W. Meijer, Jun 05 2011
Used to compute the total Steifel-Whitney cohomology class of the Real Projective space. This was an essential component of the proof that there are no product operations without zero divisors on R^n for n not equal to 1, 2, 4 or 8 (real numbers, complex numbers, quaternions, Cayley numbers), proved by Bott and Milnor. - Marcus Jaiclin, Feb 07 2012
T(n,k) = A134636(n,k) mod 2. - Reinhard Zumkeller, Nov 23 2012
T(n,k) = 1 - A219463(n,k), 0 <= k <= n. - Reinhard Zumkeller, Nov 30 2012
From Vladimir Shevelev, Dec 31 2013: (Start)
Also table of coefficients of polynomials s_n(x) of degree n which are defined by formula s_n(x) = Sum_{i=0..n} (binomial(n,i) mod 2)*x^k. These polynomials we naturally call Sierpiński's polynomials. They also are defined by the recursion: s_0(x)=1, s_(2*n+1)(x) = (x+1)*s_n(x^2), n>=0, and s_(2*n)(x) = s_n(x^2), n>=1.
Note that: s_n(1)  = A001316(n),
           s_n(2)  = A001317(n),
           s_n(3)  = A100307(n),
           s_n(4)  = A001317(2*n),
           s_n(5)  = A100308(n),
           s_n(6)  = A100309(n),
           s_n(7)  = A100310(n),
           s_n(8)  = A100311(n),
           s_n(9)  = A100307(2*n),
           s_n(10) = A006943(n),
           s_n(16) = A001317(4*n),
           s_n(25) = A100308(2*n), etc.
The equality s_n(10) = A006943(n) means that sequence A047999 is obtained from A006943 by the separation by commas of the digits of its terms. (End)
Comment from N. J. A. Sloane, Jan 18 2016: (Start)
Take a diamond-shaped region with edge length n from the top of the triangle, and rotate it by 45 degrees to get a square S_n. Here is S_6:
  [1, 1, 1, 1, 1, 1]
  [1, 0, 1, 0, 1, 0]
  [1, 1, 0, 0, 1, 1]
  [1, 0, 0, 0, 1, 0]
  [1, 1, 1, 1, 0, 0]
  [1, 0, 1, 0, 0, 0].
Then (i) S_n contains no square (parallel to the axes) with all four corners equal to 1 (cf. A227133); (ii) S_n can be constructed by using the greedy algorithm with the constraint that there is no square with that property; and (iii) S_n contains A064194(n) 1's. Thus A064194(n) is a lower bound on A227133(n). (End)
See A123098 for a multiplicative encoding of the rows, i.e., product of the primes selected by nonzero terms; e.g., 1 0 1 => 2^1 * 3^0 * 5^1. - M. F. Hasler, Sep 18 2016
From Valentin Bakoev, Jul 11 2020: (Start)
The Sierpinski's triangle with 2^n rows is a part of a lower triangular matrix M_n of dimension 2^n X 2^n. M_n is a block matrix defined recursively: M_1= [1, 0], [1, 1], and for n>1, M_n = [M_(n-1), O_(n-1)], [M_(n-1), M_(n-1)], where M_(n-1) is a block matrix of the same type, but of dimension 2^(n-1) X 2^(n-1), and O_(n-1) is the zero matrix of dimension 2^(n-1) X 2^(n-1). Here is how M_1, M_2 and M_3 look like:
1 0     1 0 0 0      1 0 0 0 0 0 0 0
1 1     1 1 0 0      1 1 0 0 0 0 0 0   - It is seen the self-similarity of the
        1 0 1 0      1 0 1 0 0 0 0 0     matrices M_1, M_2, ..., M_n, ...,
        1 1 1 1      1 1 1 1 0 0 0 0     analogously to the Sierpinski's fractal.
                     1 0 0 0 1 0 0 0
                     1 1 0 0 1 1 0 0
                     1 0 1 0 1 0 1 0
                     1 1 1 1 1 1 1 1
M_n can also be defined as M_n = M_1 X M_(n-1) where X denotes the Kronecker product. M_n is an important matrix in coding theory, cryptography, Boolean algebra, monotone Boolean functions, etc. It is a transformation matrix used in computing the algebraic normal form of Boolean functions. Some properties and links concerning M_n can be seen in LINKS. (End)
Sierpinski's gasket has fractal (Hausdorff) dimension log(A000217(2))/log(2) = log(3)/log(2) = 1.58496... (and cf. A020857). This gasket is the first of a family of gaskets formed by taking the Pascal triangle (A007318) mod j, j >= 2 (see CROSSREFS). For prime j, the dimension of the gasket is log(A000217(j))/log(j) = log(j(j + 1)/2)/log(j) (see Reiter and Bondarenko references). - Richard L. Ollerton, Dec 14 2021

			Triangle begins:
              1,
             1,1,
            1,0,1,
           1,1,1,1,
          1,0,0,0,1,
         1,1,0,0,1,1,
        1,0,1,0,1,0,1,
       1,1,1,1,1,1,1,1,
      1,0,0,0,0,0,0,0,1,
     1,1,0,0,0,0,0,0,1,1,
    1,0,1,0,0,0,0,0,1,0,1,
   1,1,1,1,0,0,0,0,1,1,1,1,
  1,0,0,0,1,0,0,0,1,0,0,0,1,
  ...

Boris A. Bondarenko, Generalized Pascal Triangles and Pyramids (in Russian), FAN, Tashkent, 1990, ISBN 5-648-00738-8.
Brand, Neal; Das, Sajal; Jacob, Tom. The number of nonzero entries in recursively defined tables modulo primes. Proceedings of the Twenty-first Southeastern Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL, 1990). Congr. Numer. 78 (1990), 47--59. MR1140469 (92h:05004).
John W. Milnor and James D. Stasheff, Characteristic Classes, Princeton University Press, 1974, pp. 43-49 (sequence appears on p. 46).
H.-O. Peitgen, H. Juergens and D. Saupe: Chaos and Fractals (Springer-Verlag 1992), p. 408.
Michel Rigo, Formal Languages, Automata and Numeration Systems, 2 vols., Wiley, 2014. Mentions this sequence - see "List of Sequences" in Vol. 2.
S. Wolfram, A New Kind of Science, Wolfram Media, 2002; Chapter 3.

N. J. A. Sloane, Table of n, a(n) for n = 0..10584 [First 144 rows, flattened; first 50 rows from T. D. Noe].
J.-P. Allouche and V. Berthe, Triangle de Pascal, complexité et automates, Bulletin of the Belgian Mathematical Society Simon Stevin 4.1 (1997): 1-24.
J.-P. Allouche, F. v. Haeseler, H.-O. Peitgen and G. Skordev, Linear cellular automata, finite automata and Pascal's triangle, Discrete Appl. Math. 66 (1996), 1-22.
David 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. [There is a typo in Theorem 6: (13) should read u(n) = 4.3^(wt(n-1)-1) for n >= 2.],
J. Baer, Explore patterns in Pascal's Triangle
Valentin Bakoev, Fast Bitwise Implementation of the Algebraic Normal Form Transform, Serdica J. of Computing 11 (2017), No 1, 45-57.
Valentin Bakoev, Properties and links concerning M_n
Thomas Baruchel, Flattening Karatsuba's Recursion Tree into a Single Summation, SN Computer Science (2020) Vol. 1, Article No. 48.
Thomas Baruchel, A non-symmetric divide-and-conquer recursive formula for the convolution of polynomials and power series, arXiv:1912.00452 [math.NT], 2019.
A. Bogomolny, Dot Patterns and Sierpinski Gasket
Boris A. Bondarenko, Generalized Pascal Triangles and Pyramids, English translation published by Fibonacci Association, Santa Clara Univ., Santa Clara, CA, 1993; see pp. 130-132.
Paul Bradley and Peter Rowley, Orbits on k-subsets of 2-transitive Simple Lie-type Groups, 2014.
E. Burlachenko, Fractal generalized Pascal matrices, arXiv:1612.00970 [math.NT], 2016. See p. 9.
S. Butkevich, Pascal Triangle Applet
David Callan, Sierpinski's triangle and the Prouhet-Thue-Morse word, arXiv:math/0610932 [math.CO], 2006.
B. Cherowitzo, Pascal's Triangle using Clock Arithmetic, Part I
B. Cherowitzo, Pascal's Triangle using Clock Arithmetic, Part II
C. Cobeli, A. Zaharescu, A game with divisors and absolute differences of exponents, arXiv:1411.1334 [math.NT], 2014; Journal of Difference Equations and Applications, Vol. 20, #11, 2014.
Ilya Gutkovskiy, Illustrations (triangle formed by reading Pascal's triangle mod m)
R. K. Guy, The strong law of small numbers. Amer. Math. Monthly 95 (1988), no. 8, 697-712.
Brady Haran, Chaos Game, Numberphile video, YouTube (April 27, 2017).
I. Kobayashi et al., Pascal's Triangle
Dr. Math, Regular polygon formulas [Broken link?]
Y. Moshe, The distribution of elements in automatic double sequences, Discr. Math., 297 (2005), 91-103.
National Curve Bank, Sierpinski Triangles
Hieu D. Nguyen, A Digital Binomial Theorem, arXiv:1412.3181 [math.NT], 2014.
S. Northshield, Sums across Pascal's triangle modulo 2, Congressus Numerantium, 200, pp. 35-52, 2010.
A. M. Reiter, Determining the dimension of fractals generated by Pascal's triangle, Fibonacci Quarterly, 31(2), 1993, pp. 112-120.
F. Richman, Javascript for computing Pascal's triangle modulo n. Go to this page, then under "Modern Algebra and Other Things", click "Pascal's triangle modulo n".
Vladimir Shevelev, On Stephan's conjectures concerning Pascal triangle modulo 2 and their polynomial generalization, J. of Algebra Number Theory: Advances and Appl., 7 (2012), no.1, 11-29. Also arXiv:1011.6083, 2010.
N. J. A. Sloane, Illustration of rows 0 to 32 (encoignure style)
N. J. A. Sloane, Illustration of rows 0 to 64 (encoignure style)
N. J. A. Sloane, Illustration of rows 0 to 128 (encoignure style)
N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS
Eric Weisstein's World of Mathematics, Sierpiński Sieve, Rule 60, Rule 102
Index entries for sequences related to cellular automata
Index entries for triangles and arrays related to Pascal's triangle
Index entries for sequences generated by sieves

Sequences based on the triangles formed by reading Pascal's triangle mod m: (this sequence) (m = 2), A083093 (m = 3), A034931 (m = 4), A095140 (m = 5), A095141 (m = 6), A095142 (m = 7), A034930(m = 8), A095143 (m = 9), A008975 (m = 10), A095144 (m = 11), A095145 (m = 12), A275198 (m = 14), A034932 (m = 16).
Other versions: A090971, A038183.
Cf. A007318, A054431, A001317, A008292, A083093, A034931, A034930, A008975, A034932, A166360, A249133, A064194, A227133.
From Johannes W. Meijer, Jun 05 2011: (Start)
A106344 is a skew version of this triangle.
Triangle sums (see the comments): A001316 (Row1; Related to Row2), A002487 (Related to Kn11, Kn12, Kn13, Kn21, Kn22, Kn23), A007306 (Kn3, Kn4), A060632 (Fi1, Fi2), A120562 (Ca1, Ca2), A112970 (Gi1, Gi2), A127830 (Ze3, Ze4). (End)

import Data.Bits (xor)
a047999 :: Int -> Int -> Int
a047999 n k = a047999_tabl !! n !! k
a047999_row n = a047999_tabl !! n
a047999_tabl = iterate (\row -> zipWith xor ([0] ++ row) (row ++ [0])) [1]
-- Reinhard Zumkeller, Dec 11 2011, Oct 24 2010

A047999:= func< n,k | BitwiseAnd(n-k, k) eq 0 select 1 else 0 >;
[A047999(n,k): k in [0..n], n in [0..15]]; // G. C. Greubel, Dec 03 2024

# Maple code for first M rows (here M=10) - N. J. A. Sloane, Feb 03 2016
ST:=[1,1,1]; a:=1; b:=2; M:=10;
for n from 2 to M do ST:=[op(ST),1];
for i from a to b-1 do ST:=[op(ST), (ST[i+1]+ST[i+2]) mod 2 ]; od:
ST:=[op(ST),1];
a:=a+n; b:=a+n; od:
ST; # N. J. A. Sloane
# alternative
A047999 := proc(n,k)
    modp(binomial(n,k),2) ;
end proc:
seq(seq(A047999(n,k),k=0..n),n=0..12) ; # R. J. Mathar, May 06 2016

Mod[ Flatten[ NestList[ Prepend[ #, 0] + Append[ #, 0] &, {1}, 13]], 2] (* Robert G. Wilson v, May 26 2004 *)
rows = 14; ca = CellularAutomaton[60, {{1}, 0}, rows-1]; Flatten[ Table[ca[[k, 1 ;; k]], {k, 1, rows}]] (* Jean-François Alcover, May 24 2012 *)
Mod[#,2]&/@Flatten[Table[Binomial[n,k],{n,0,20},{k,0,n}]] (* Harvey P. Dale, Jun 26 2019 *)

\\ Recurrence for Pascal's triangle mod p, here p = 2.
p = 2; s=13; T=matrix(s,s); T[1,1]=1;
for(n=2,s, T[n,1]=1; for(k=2,n, T[n,k] = (T[n-1,k-1] + T[n-1,k])%p ));
for(n=1,s,for(k=1,n,print1(T[n,k],", "))) \\ Gerald McGarvey, Oct 10 2009

A011371(n)=my(s);while(n>>=1,s+=n);s
T(n,k)=A011371(n)==A011371(k)+A011371(n-k) \\ Charles R Greathouse IV, Aug 09 2013

T(n,k)=bitand(n-k,k)==0 \\ Charles R Greathouse IV, Aug 11 2016

def A047999_T(n,k):
    return int(not ~n & k) # Chai Wah Wu, Feb 09 2016

Lucas's Theorem is that T(n,k) = 1 if and only if the 1's in the binary expansion of k are a subset of the 1's in the binary expansion of n; or equivalently, k AND NOT n is zero, where AND and NOT are bitwise operators. - Chai Wah Wu, Feb 09 2016 and N. J. A. Sloane, Feb 10 2016
Sum_{k>=0} T(n, k) = A001316(n) = 2^A000120(n).
T(n,k) = T(n-1,k-1) XOR T(n-1,k), 0 < k < n; T(n,0) = T(n,n) = 1. - Reinhard Zumkeller, Dec 13 2009
T(n,k) = (T(n-1,k-1) + T(n-1,k)) mod 2 = |T(n-1,k-1) - T(n-1,k)|, 0 < k < n; T(n,0) = T(n,n) = 1. - Rick L. Shepherd, Feb 23 2018
From Vladimir Shevelev, Dec 31 2013: (Start)
For polynomial {s_n(x)} we have
s_0(x)=1; for n>=1, s_n(x) = Product_{i=1..A000120(n)} (x^(2^k_i) + 1),
if the binary expansion of n is n = Sum_{i=1..A000120(n)} 2^k_i;
G.f. Sum_{n>=0} s_n(x)*z^n = Product_{k>=0} (1 + (x^(2^k)+1)*z^(2^k)) (0Let x>1, t>0 be real numbers. Then
Sum_{n>=0} 1/s_n(x)^t = Product_{k>=0} (1 + 1/(x^(2^k)+1)^t);
Sum_{n>=0} (-1)^A000120(n)/s_n(x)^t = Product_{k>=0} (1 - 1/(x^(2^k)+1)^t).
In particular, for t=1, x>1, we have
Sum_{n>=0} (-1)^A000120(n)/s_n(x) = 1 - 1/x. (End)
From Valentin Bakoev, Jul 11 2020: (Start)
(See my comment about the matrix M_n.) Denote by T(i,j) the number in the i-th row and j-th column of M_n (0 <= i, j < 2^n). When i>=j, T(i,j) is the j-th number in the i-th row of the Sierpinski's triangle. For given i and j, we denote by k the largest integer of the type k=2^m and kT(i,0) = T(i,i) = 1, or
T(i,j) = 0 if i < j, or
T(i,j) = T(i-k,j), if j < k, or
T(i,j) = T(i-k,j-k), if j >= k.
Thus, for given i and j, T(i,j) can be computed in O(log_2(i)) steps. (End)

Additional links from Lekraj Beedassy, Jan 22 2004

A249183 a(n) = row n of triangle A249133, concatenated.

Original entry on oeis.org

1, 111, 11011, 1110111, 110101011, 11100000111, 1101100011011, 111011101110111, 11010101010101011, 1110000000000000111, 110110000000000011011, 11101110000000001110111, 1101010110000000110101011, 111000001110000011100000111, 11011000110110001101100011011

Offset: 0

Reinhard Zumkeller, Nov 14 2014

nonn

			.   0:                                  1
.   1:                                 111
.   2:                                11011
.   3:                               1110111
.   4:                              110101011
.   5:                             11100000111
.   6:                            1101100011011
.   7:                           111011101110111
.   8:                          11010101010101011
.   9:                         1110000000000000111
.  10:                        110110000000000011011
.  11:                       11101110000000001110111
.  12:                      1101010110000000110101011
.  13:                     111000001110000011100000111
.  14:                    11011000110110001101100011011
.  15:                   1110111011101110111011101110111
.  16:                  110101010101010101010101010101011
.  17:                 11100000000000000000000000000000111
.  18:                1101100000000000000000000000000011011
.  19:               111011100000000000000000000000001110111
.  20:              11010101100000000000000000000000110101011
.  21:             1110000011100000000000000000000011100000111
.  22:            110110001101100000000000000000001101100011011
.  23:           11101110111011100000000000000000111011101110111
.  24:          1101010101010101100000000000000011010101010101011
.  25:         111000000000000011100000000000001110000000000000111
.  26:        11011000000000001101100000000000110110000000000011011
.  27:       1110111000000000111011100000000011101110000000001110111
.  28:      110101011000000011010101100000001101010110000000110101011
.  29:     11100000111000001110000011100000111000001110000011100000111
.  30:    1101100011011000110110001101100011011000110110001101100011011
.  31:   111011101110111011101110111011101110111011101110111011101110111
.  32:  11010101010101010101010101010101010101010101010101010101010101011 .

Reinhard Zumkeller, Table of n, a(n) for n = 0..500

Cf. A249133, A249184 (decimal), A007088, A006943.

a249183 = foldr (\b v -> 10 * v + b) 0 . a249133_row

a[n_] := FromDigits[Mod[Riffle[Binomial[n, Range[0, n]], Binomial[n - 1, Range[0, n - 1]]], 2]]; Array[a, 15, 0] (* Amiram Eldar, Jul 28 2023 *)

a(n) = Sum_{k=0..2*n} A249133(n,k)*10^k.
a(n) = A007088(A249184(n));
A055641(a(n)) = A249304(n).

A173019 a(n) is the value of row n in triangle A083093 seen as ternary number.

Original entry on oeis.org

1, 4, 16, 28, 112, 448, 784, 3136, 12301, 19684, 78736, 314944, 551152, 2204608, 8818432, 15432256, 61729024, 242132884, 387459856, 1549839424, 6199180549, 10848875968, 43395503872, 173577055372, 303766932781, 1215067731124

Offset: 0

Michael Thaler (michael_thaler(AT)brown.edu), Nov 07 2010

Previous name was "Pascal's Triangle mod 3 converted to decimal."
If 2|a(n), then 4|a(n).
If 8|a(n), then 16|a(n).
If a(n)=4*a(n-1), then 3 does not divide n.
The first few odd values for a(n) are a(0)=1, a(8)=12301, a(20)=6199180549, a(24)=303766932781.
It appears that, as the terms of A001317 (analogous to this sequence, using binary instead of ternary) can be uniquely represented as products of Fermat numbers, the terms of this sequence can be represented as products from a nontrivial set of numbers. - Thomas Anton, Oct 27 2018
Subsequence of A014190. - Chai Wah Wu, Jul 30 2025

			a(9) = 3^(3^2) + 1 = 19684;
a(8) = (5*19684 - 12)/8 = 12301;
a(10) = 4*19684 = 78736.

Reinhard Zumkeller, Table of n, a(n) for n = 0..1000
P. Mathonet, M. Rigo, M. Stipulanti and N. Zénaïdi, On digital sequences associated with Pascal's triangle, arXiv:2201.06636 [math.NT], 2022.

Cf. A006940 (takes these values and converts them to decimal notation).

Cf. A001317, A007089, A006943, A083093, A014190.

a173019 = foldr (\t v -> 3 * v + t) 0 . map toInteger . a083093_row
-- Reinhard Zumkeller, Jul 11 2013

FromDigits[#, 3] & /@ Table[Mod[Binomial[n, k], 3], {n, 0, 25}, {k, 0, n}] (* Michael De Vlieger, Oct 31 2018 *)

a(n) = my(v = vector(n+1, k, binomial(n, k-1))); fromdigits(apply(x->x % 3, v), 3); \\ Michel Marcus, Nov 21 2018

from math import prod, comb
from gmpy2 import digits
def A173019(n):
    if n==0: return 1
    c, l = '', len(s:=digits(n,3))
    for k in range(m:=n+2>>1):
        t = digits(k,3).zfill(l)
        c += str(prod(comb(int(s[i]),int(t[i]))%3 for i in range(l))%3)
    return int(c+c[m-2+(n&1)::-1],3) # Chai Wah Wu, Jul 30 2025

a(3^n) = 3^(3^n) + 1.
a(3^n) = (8*a((3^n)-1) + 12)/5. [5*a(3^n) = 1200...0012 (base 3), 8*a((3^n)-1) = (22)(1212...2121) = 11222...2202 (base 3).]
For n > 0, a((3^n)+1) = 4*a(3^n) and a((3^n)+2) = 4*a((3^n)+1).
a(n) = Sum_{k=0..n} A083093(n,k) * 3^k. - Reinhard Zumkeller, Jul 11 2013

a(13) and a(19) corrected and name clarified by Tom Edgar, Oct 11 2015

A245550 a(0)=0; for n >= 1, a(n) = f(n) - 2*f(floor((n-1)/2)), where f(n) = A006046(n).

Original entry on oeis.org

0, 1, 3, 3, 7, 5, 9, 9, 17, 11, 15, 15, 23, 19, 27, 27, 43, 29, 33, 33, 41, 37, 45, 45, 61, 49, 57, 57, 73, 65, 81, 81, 113, 83, 87, 87, 95, 91, 99, 99, 115, 103, 111, 111, 127, 119, 135, 135, 167, 139, 147, 147, 163, 155, 171, 171, 203, 179, 195, 195, 227, 211, 243, 243, 307, 245, 249, 249, 257

Offset: 0

N. J. A. Sloane, Jul 29 2014

nonn

For n >= 1, a(n) is the number of ON cells in the n-th generation of the 2-D Mitra-Kumar cellular automaton defined as follows. The state of a cell depends on the states of its NW and NE neighbors at the previous generation.

An ON cell remains ON iff 0 or 2 of its neighbors were ON, and an OFF cell turns ON iff exactly one of its neighbors was ON.

			The first few generations of the automaton are:
X  0X0  00X00  000X000  0000X0000
   X0X  00000  0000000  000000000
        X000X  0X000X0  00X000X00
               X0X0X0X  000000000
                        X0000000X
The rows are a subset of the rows of Pascal's triangle A007318 read mod 2 (see A006943). The binary weights of these rows are given by A001316, whose partial sums are A006046, and the formula in the definition follows easily from this.

Sugata Mitra and Sujai Kumar. "Fractal replication in time-manipulated one-dimensional cellular automata." Complex Systems, 16.3 (2006): 191-207. See Fig. 16.

Reinhard Zumkeller, Table of n, a(n) for n = 0..1000
Index entries for sequences related to cellular automata

Cf. A006046, A001316, A006943, A007318.

a245550 n = a245550_list !! n
a245550_list = 0 : zipWith (-) (tail a006046_list) (h a006046_list)
               where h (x:xs) = (2 * x) : (2 * x) : h xs
-- Reinhard Zumkeller, Jul 29 2014

f:=proc(n) option remember; # A006046
if n <= 1 then n elif n mod 2 = 0 then 3*f(n/2)
else 2*f((n-1)/2)+f((n+1)/2); fi; end;
g:=n->f(n)-2*f(floor((n-1)/2));
[0,seq(g(n),n=1..130)];

A262260 Number of triangles formed by the positions of odd numbers in the first n rows of Pascal's triangle, also known as Tartaglia's triangle.

Original entry on oeis.org

0, 1, 1, 4, 4, 6, 6, 13, 13, 15, 15, 21, 21, 25, 25, 40, 40, 42, 42, 48, 48, 52, 52, 66, 66, 70, 70, 82, 82, 90, 90, 121, 121, 123, 123, 129, 129, 133, 133, 147, 147, 151, 151, 163, 163, 171, 171, 201, 201, 205, 205, 217, 217, 225, 225, 253, 253, 261, 261, 285, 285, 301, 301, 364, 364

Offset: 0

Emmanuele Villa, Nov 09 2016

Named Tartaglia's triangle after the Italian mathematician Niccolò Fontana Tartaglia (1500-1577). - Amiram Eldar, Jun 11 2021

			Taking Pascal's triangle, removing the even terms and replacing each odd term with a dot, will give you this illustration (the circles are connected with lines to show the sub-triangles):
                                        triangle counts
                                        ---------------
   row                                     new total
   ===                                     === =====
    0                  o                    0    0
                      / \
    1                o---o                  1    1
                    /     \
    2              o       o                0    1
                  / \     / \
    3            o---o---o---o              3    4
                /             \
    4          o               o            0    4
              / \             / \
    5        o---o           o---o          2    6
            /     \         /     \
    6      o       o       o       o        0    6
          / \     / \     / \     / \
    7    o---o---o---o---o---o---o---o      7   13
        /                             \
    8  o                               o    0   13
.
.
Formula example:
given a(46) = 171, a(47) is computed as follows:
A = A001316(46) = 16
B = A001316(44) = 8
C = A001316(44) - 1 = 7
D = A001316((47+1-32)/8) - 1 = 1
a(47) = 171 + 16 + 8 + 7 - 1 = 201
.
.
You can find results for a(n), A, B, C and D in the links section for the first 500 rows.

Riccardo Perego and Emmanuele Villa, Tartaglia's Triangle Odd Distribution (in Italian), 2012.
Jon E. Schoenfield, Plot of terms through n=2^14.
Emmanuele Villa, A,B,C,D coefficients for the first 500 rows.
Emmanuele Villa, C# Program that calculates the first 50 rows.
Wikipedia, Pascal's Triangle.

Cf. A000120, A001316, A001317, A006943, A088512.

Empirical formula:
a(0)=0; a(1)=1; for n>1, a(n) = a(n-1) + A + B + C - D
where
A = A001316(n-1) if n = 2x+1, 0 otherwise
B = A001316(n-3) if n = 4x+1, 0 otherwise
C = B-1 if n = 8x+1, 0 otherwise
D = A088512(n+1) = A001316((n+1-m)/8)-1 if n = 8x+1, 0 otherwise, where m is the highest power of 2 less than n.

A332087 Diagonals of cellular automata with 4 conditions and 6 possible values.

Original entry on oeis.org

3, 33, 333, 3333, 33433, 334433, 3344433, 33433433, 334444433, 3344444433, 33434443433, 334445544433, 3344455544433, 33434000043433, 334444444444433, 3344444334444433, 33434400000443433, 334445433334544433, 3344454322234544433, 33434050022005043433, 3344444433333344444433

Offset: 1

Mario Cortés, Aug 22 2020

nonn

The automata starts with 2 entries on each axis of value 3.
Defined value(u,v) for any u,v natural the value of each cell of the automata.
The axis(u,0),(u,-1) and (0,v),(-1,v) are value 3.
Matrix (with entries):
33333333333333
33333333333333
33444444444444 ...
33443443443443
33434444444444
33444455044444
33444550440440
33434504303303
33444043032032
33443440322322
...          ...
Diagonals:
4
44
444
4334
44444
444444
4344434
44455444
444555444
4340000434
44444444444
444443344444
4344000004434
44454333345444
444543222345444
4340500220050434
44444433333444444
...
The stable parts around the axis are built with the matrix:
33434
30444
44134
34314
44440
until approximately at a(300), when it disappears, and form a more chaotic structure that covers all the area of (u+175,v+175).

			value(1,1) = floor(((3)+(3)+(3)+(3)+(3)+(3)+(3))/7 +1) = 4,
value(1,2) = floor(((4)+(3)+(3)+(3)+(3)+(3)+(3))/7 +1) = 4,
value(2,1) = floor(((3)+(4)+(3)+(3)+(3)+(3)+(3))/7 +1) = 4,
...

Mario Cortés, VISUAL REPRESENTATION WITH COLORS

Cf. A006943.

value(v,u)= (In order of priority)
if( (v,u-1)+(v-1,u)+(v-1,u-1)+(v,u-2)+(v-2,u)-(v-1,u-2)-(v-2,u-1) )>10;0
if( (v,u-1)+(v-1,u)+(v-1,u-1)-(v,u-2)-(v-2,u) )=5;3
if( (v,u-1)+(v-1,u)+(v-1,u-1)+(v-1,u-2)+(v-2,u-1)-(v-2,u-2) )=3;2
if( (v-1,u-2)+(v-2,u-1)+(v-2,u-2)+(v-1,u-1)-(v,u-1)-(v-1,u) )=1;1
if nothing= floor(((v,u-1)+(v-1,u)+(v-1,u-1)+(v,u-2)+(v-2,u)-(v-1,u-2)-(v-2,u-1))/7 +1)

Showing 1-7 of 7 results.

cp's OEIS Frontend

A000215 Fermat numbers: a(n) = 2^(2^n) + 1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

Maxima

PARI

Python

Formula

A047999 Sierpiński's [Sierpinski's] triangle (or gasket): triangle, read by rows, formed by reading Pascal's triangle (A007318) mod 2.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

PARI

Python

Formula

Extensions

A249183 a(n) = row n of triangle A249133, concatenated.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

Formula

A173019 a(n) is the value of row n in triangle A083093 seen as ternary number.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Python

Formula

Extensions

A245550 a(0)=0; for n >= 1, a(n) = f(n) - 2*f(floor((n-1)/2)), where f(n) = A006046(n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

A262260 Number of triangles formed by the positions of odd numbers in the first n rows of Pascal's triangle, also known as Tartaglia's triangle.

Views

Author

Keywords