This site is supported by donations to The OEIS Foundation.
Sierpiński's triangle
From OeisWiki
(Redirected from Sierpinski's triangle)
Sierpiński’s triangle, named after Wacław Sierpiński, is Pascal’s triangle modulo 2.
Contents

A006943 Rows of Sierpiński’s triangle (Pascal’s triangle mod 2). A047999 Concatenated rows of Sierpiński’s triangle (Pascal’s triangle mod 2). 
(A001317)  
0  1  1  
1  1  1  3  
2  1  0  1  5  
3  1  1  1  1  15  
4  1  0  0  0  1  17  
5  1  1  0  0  1  1  51  
6  1  0  1  0  1  0  1  85  
7  1  1  1  1  1  1  1  1  255  
8  1  0  0  0  0  0  0  0  1  257  
9  1  1  0  0  0  0  0  0  1  1  771  
10  1  0  1  0  0  0  0  0  1  0  1  1285  
11  1  1  1  1  0  0  0  0  1  1  1  1  3855  
12  1  0  0  0  1  0  0  0  1  0  0  0  1  4369  
13  1  1  0  0  1  1  0  0  1  1  0  0  1  1  13107  
14  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  21845  
15  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  65535  
16  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  65537  
17  1  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  1  196611  
18  1  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  1  327685  
19  1  1  1  1  0  0  0  0  0  0  0  0  0  0  0  0  1  1  1  1  983055  
20  1  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  1  1114129  
21  1  1  0  0  1  1  0  0  0  0  0  0  0  0  0  0  1  1  0  0  1  1  3342387  
22  1  0  1  0  1  0  1  0  0  0  0  0  0  0  0  0  1  0  1  0  1  0  1  5570645  
23  1  1  1  1  1  1  1  1  0  0  0  0  0  0  0  0  1  1  1  1  1  1  1  1  16711935  
24  1  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  1  16843009  
25  1  1  0  0  0  0  0  0  1  1  0  0  0  0  0  0  1  1  0  0  0  0  0  0  1  1  50529027  
26  1  0  1  0  0  0  0  0  1  0  1  0  0  0  0  0  1  0  1  0  0  0  0  0  1  0  1  84215045  
27  1  1  1  1  0  0  0  0  1  1  1  1  0  0  0  0  1  1  1  1  0  0  0  0  1  1  1  1  252645135  
28  1  0  0  0  1  0  0  0  1  0  0  0  1  0  0  0  1  0  0  0  1  0  0  0  1  0  0  0  1  286331153  
29  1  1  0  0  1  1  0  0  1  1  0  0  1  1  0  0  1  1  0  0  1  1  0  0  1  1  0  0  1  1  858993459  
30  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  1431655765  
31  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  4294967295  
32  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  4294967297  

1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32 
Sierpiński’s triangle rows



Factorization into Fermat numbers  

0  1  1  
1  11  3  (11)2 = 3 = F0  
2  101  5  (101)2 = 5 = F1  
3  1111  15  (11)2 ⋅ (101)2 = 3 ⋅ 5 = F0 F1  
4  10001  17  (10001)2 = 17 = F2  
5  110011  51  (11)2 ⋅ (10001)2 = 3 ⋅ 17 = F0 F2  
6  1010101  85  (101)2 ⋅ (10001)2 = 5 ⋅ 17 = F1 F2  
7  11111111  255  (11)2 ⋅ (101)2 ⋅ (10001)2 = 3 ⋅ 5 ⋅ 17 = F0 F1 F2  
8  100000001  257  (100000001)2 = 257 = F3  
9  1100000011  771  (11)2 ⋅ (100000001)2 = 3 ⋅ 257 = F0 F3  
10  10100000101  1285  (101)2 ⋅ (100000001)2 = 5 ⋅ 257 = F1 F3  
11  111100001111  3855  (11)2 ⋅ (101)2 ⋅ (100000001)2 = 3 ⋅ 5 ⋅ 257 = F0 F1 F3  
12  1000100010001  4369  (10001)2 ⋅ (100000001)2 = 17 ⋅ 257 = F2 F3  
13  11001100110011  13107  (11)2 ⋅ (10001)2 ⋅ (100000001)2 = 3 ⋅ 17 ⋅ 257 = F0 F2 F3  
14  101010101010101  21845  (101)2 ⋅ (10001)2 ⋅ (100000001)2 = 5 ⋅ 17 ⋅ 257 = F1 F2 F3  
15  1111111111111111  65535  (11)2 ⋅ (101)2 ⋅ (10001)2 ⋅ (100000001)2 = 3 ⋅ 5 ⋅ 17 ⋅ 257 = F0 F1 F2 F3  
16  10000000000000001  65537  (10000000000000001)2 = 65537 = F4  
17  110000000000000011  196611  (11)2 ⋅ (10000000000000001)2 = 3 ⋅ 65537 = F0 F4  
18  1010000000000000101  327685  (101)2 ⋅ (10000000000000001)2 = 5 ⋅ 65537 = F1 F4  
19  11110000000000001111  983055  (11)2 ⋅ (101)2 ⋅ (10000000000000001)2 = 3 ⋅ 5 ⋅ 65537 = F0 F1 F4  
20  100010000000000010001  1114129  (10001)2 ⋅ (10000000000000001)2 = 17 ⋅ 65537 = F2 F4  
21  1100110000000000110011  3342387  (11)2 ⋅ (10001)2 ⋅ (10000000000000001)2 = 3 ⋅ 17 ⋅ 65537 = F0 F2 F4  
22  10101010000000001010101  5570645  (101)2 ⋅ (10001)2 ⋅ (10000000000000001)2 = 5 ⋅ 17 ⋅ 65537 = F1 F2 F4  
23  111111110000000011111111  16711935  (11)2 ⋅ (101)2 ⋅ (10001)2 ⋅ (10000000000000001)2 = 3 ⋅ 5 ⋅ 17 ⋅ 65537 = F0 F1 F2 F4  
24  1000000010000000100000001  16843009  (100000001)2 = (10000000000000001)2 = 257 ⋅ 65537 = F3 F4  
25  11000000110000001100000011  50529027  (11)2 ⋅ (100000001)2 = (10000000000000001)2 = 3 ⋅ 257 ⋅ 65537 = F0 F3 F4  
26  101000001010000010100000101  84215045  (101)2 ⋅ (100000001)2 = (10000000000000001)2 = 5 ⋅ 257 ⋅ 65537 = F1 F3 F4  
27  1111000011110000111100001111  252645135  (11)2 ⋅ (101)2 ⋅ (100000001)2 = (10000000000000001)2 = 3 ⋅ 5 ⋅ 257 ⋅ 65537 = F0 F1 F3 F4  
28  10001000100010001000100010001  286331153  (10001)2 ⋅ (100000001)2 = (10000000000000001)2 = 17 ⋅ 257 ⋅ 65537 = F2 F3 F4  
29  110011001100110011001100110011  858993459  (11)2 ⋅ (10001)2 ⋅ (100000001)2 = (10000000000000001)2 = 3 ⋅ 17 ⋅ 257 ⋅ 65537 = F0 F2 F3 F4  
30  1010101010101010101010101010101  1431655765  (101)2 ⋅ (10001)2 ⋅ (100000001)2 = (10000000000000001)2 = 5 ⋅ 17 ⋅ 257 ⋅ 65537 = F1 F2 F3 F4  
31  11111111111111111111111111111111  4294967295  (11)2 ⋅ (101)2 ⋅ (10001)2 ⋅ (100000001)2 = (10000000000000001)2 = 3 ⋅ 5 ⋅ 17 ⋅ 257 ⋅ 65537 = F0 F1 F2 F3 F4  
32  100000000000000000000000000000001  4294967297*  (100000000000000000000000000000001)2 = 4294967297* = F5 
Sierpiński’s triangle rows and constructible (with straightedge and compass) oddsided polygons
Forn = 1 
Rows formulae
It can be proved by induction that the rows of Sierpiński’s triangle interpreted as a binary number are products of distinct Fermat numbers (Denton Hewgill’s identity^{[1]})
[row (n)]2 = [
⌊ n / 2 i⌋ mod 2)]2 = 
[
⌊ n / 2 i⌋ mod 2)]2 . 
Inductive proof:
 Base case: For row 0, we get 1 (empty product), the product of distinct Fermat numbers in { };
 Inductive hypothesis: Assume that any row
is the product of distinct Fermat numbers inn, 0 ≤ n ≤ 2 k − 1, {F0 , ..., Fk − 1}
[row (n)]2 = [
⌊ n / 2 i⌋ mod 2)]2 = [
⌊ n / 2 i⌋ mod 2)]2 , 
then for any row
2 k + n, 0 ≤ n ≤ 2 k − 1, 
[row (2 k + n)]2 = [row (n)]2 [ Fk ]2 = [
⌊ n / 2 i⌋ mod 2)]2 [ Fk ]2 = 
[
⌊ n / 2 i⌋ mod 2)]2 = [
⌊ n / 2 i⌋ mod 2)]2 . 
As a particular case, rows
2 n, n ≥ 0, 
Fn 
n 
Sequences
A006943 Sierpiński’s triangle (Pascal’s triangle mod 2) rows.
 {1, 11, 101, 1111, 10001, 110011, 1010101, 11111111, 100000001, 1100000011, 10100000101, 111100001111, 1000100010001, 11001100110011, 101010101010101, 1111111111111111, 10000000000000001, 110000000000000011, 1010000000000000101, ...}
A047999 Sierpiński’s triangle (or Sierpiński’s gasket): triangle, read by rows, formed by reading Pascal’s triangle mod 2.
 {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, ...}
n ≥ 0. 
 {1, 3, 5, 15, 17, 51, 85, 255, 257, 771, 1285, 3855, 4369, 13107, 21845, 65535, 65537, 196611, 327685, 983055, 1114129, 3342387, 5570645, 16711935, 16843009, 50529027, ...}
See also
Notes
 ↑ Antti Karttunen, On Pascal’s Triangle Modulo 2 in Fibonacci Representation (Abstract).
External links
 Antti Karttunen, On Pascal’s Triangle Modulo 2 in Fibonacci Representation, The Fibonacci Quarterly, Volume 42, Number 1, February 2004.