This site is supported by donations to The OEIS Foundation.

Sierpiński's triangle

(Redirected from Sierpinski's triangle)

Sierpiński’s triangle, named after Wacław Sierpiński, is Pascal’s triangle modulo 2.

Sierpiński’s triangle (Pascal’s triangle mod 2)
 n
[row (n)]2  =  [
 n ∑ i  = 0

((
 n i
) mod 2) 2i  ]2  =  [
 ⌊  log2 n ⌋ ∏ i  = 0

Fi  (
⌊  n  / 2i
mod 2)
]2  =
[
 ⌊  log2 n ⌋ ∏ i  = 0

(2 2i + 1) (
⌊  n  / 2i
mod 2)
]2

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).
 [row (n)]10

(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
 i  = 0
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

Sierpiński’s triangle rows
 n
 [row(n)]2
 [row(n)]10
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
* F5 = 4294967297 = 641 ⋅ 6700417 is the first composite Fermat number. From here on no other Fermat number is known to be prime.

Sierpiński’s triangle rows and constructible (with straightedge and compass) odd-sided polygons

For
 n = 1
to 31, we get all the non-empty products of the 5 known Fermat primes, giving the number of sides of constructible odd-sided polygons. If there are no other Fermat primes, there are then no more constructible (with straightedge and compass) odd-sided polygons.

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 ∑ i  = 0

((
 n i
) mod 2) 2i  ]2  =  [
 ⌊  log2 n ⌋ ∏ i  = 0

Fi   (
⌊  n  / 2i
mod 2)
]2  =
[
 ⌊  log2 n ⌋ ∏ i  = 0

(2 2i + 1) (
⌊  n  / 2i
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  n, 0   ≤   n   ≤   2 k  −  1,
is the product of distinct Fermat numbers in  {F0 , ..., Fk   − 1}

[row (n)]2  =  [
 ⌊  log2 n ⌋ ∏ i  = 0

Fi   (
⌊  n  / 2i
mod 2)
]2  =  [
 ⌊  log2 n ⌋ ∏ i  = 0

(2 2i + 1) (
⌊  n  / 2i
mod 2)
]2 ,

then for any row
 2 k + n, 0   ≤   n   ≤   2 k  −  1,
we have

[row (2k + n)]2  =  [row (n)]2 [ Fk  ]2  =  [
 ⌊  log2 n ⌋ ∏ i  = 0

Fi   (
⌊  n  / 2i
mod 2)
]2 [ Fk  ]2  =
[
 k ∏ i  = 0

Fi   (
⌊  n  / 2i
mod 2)
]2  =  [
 ⌊  log2 ( 2 k + n) ⌋ ∏ i  = 0

Fi   (
⌊  n  / 2i
mod 2)
]2 .

As a particular case, rows
 2 n, n   ≥   0,
give
 Fn
, the
 n
th Fermat number.

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, ...}
A001317 Sierpiński’s triangle (Pascal’s triangle mod 2) rows converted to decimal. (
 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, ...}