This site is supported by donations to The OEIS Foundation.

Sierpiński's triangle

From OeisWiki

(Redirected from Sierpinski's triangle)
Jump to: navigation, search


This article needs more work.

Please help by expanding it!


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

Contents

Sierpiński's triangle (Pascal's triangle mod
2
)

n
 
\begin{array}{l} {\displaystyle  [{\rm row}(n)]_2 = \left[ \sum_{i=0}^{n} \bigg( \binom{n}{i} ~\bmod~ 2 \bigg) ~ 2^i \right]_2 = \left[ \prod_{i=0}^{ \lfloor \log_2(n) \rfloor} {\rm F}_i^{( \lfloor \frac{n}{2^i} \rfloor ~\bmod~ 2)} \right]_2 = \left[ \prod_{i=0}^{ \lfloor \log_2(n) \rfloor } (2^{2^i}+1)^{( \lfloor \frac{n}{2^i} \rfloor ~\bmod~ 2)}\right]_2  } \end{array}
[row(n)]10
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 F_4
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.

Sierpinski'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 Sierpinski's triangle interpreted as a binary number are products of distinct Fermat numbers (Denton Hewgill's identity[1])

[{\rm row}(n)]_2 = \left[\sum_{i=0}^{n} \bigg(\binom{n}{i} ~\bmod~ 2\bigg) ~ 2^i\right]_2 = \left[\prod_{i=0}^{\lfloor \log_2(n) \rfloor} {\rm F}_i^{(\lfloor \frac{n}{2^i} \rfloor ~\bmod~ 2)}\right]_2 = \left[\prod_{i=0}^{\lfloor \log_2(n) \rfloor} (2^{2^i}+1)^{(\lfloor \frac{n}{2^i} \rfloor ~\bmod~ 2)}\right]_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 ≤ 2k − 1,
    is the product of distinct Fermat numbers in
    {F0, ..., Fk −1}
[{\rm row}(n)]_2 = \left[\prod_{i=0}^{\lfloor \log_2(n) \rfloor} {\rm F}_i^{(\lfloor \frac{n}{2^i} \rfloor ~\bmod~ 2)}\right]_2 = \left[\prod_{i=0}^{\lfloor \log_2(n) \rfloor} (2^{2^i}+1)^{(\lfloor \frac{n}{2^i} \rfloor ~\bmod~ 2)}\right]_2 \,
then for any row
2k + n, 0 ≤ n ≤ 2k − 1,
we have
[{\rm row}(2^k + n)]_2 = [{\rm row}(n)]_2 ~ [{\rm F}_k]_2 = \left[\prod_{i=0}^{\lfloor \log_2(n) \rfloor} {\rm F}_i^{(\lfloor \frac{n}{2^i} \rfloor ~\bmod~ 2)}\right]_2 ~ [{\rm F}_k]_2 = \left[\prod_{i=0}^{k} {\rm F}_i^{(\lfloor \frac{n}{2^i} \rfloor ~\bmod~ 2)}\right]_2 = \left[\prod_{i=0}^{\lfloor \log_2(2^k + n) \rfloor} {\rm F}_i^{(\lfloor \frac{n}{2^i} \rfloor ~\bmod~ 2)}\right]_2. \,
As a particular case, rows
2n, n ≥ 0,
give
Fn
, the
n
th Fermat number.

Sequences

A006943 Sierpinski'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 Sierpinski's triangle (or 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 Sierpinski'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, ...}

See also

Notes

  1. Antti Karttunen, On Pascal's Triangle Modulo 2 in Fibonacci Representation (Abstract).

External links

Personal tools