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) odd-sided 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.