Sierpiński's triangle

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.

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

n		[row (n)]2  =  [     n ∑   i  = 0    (( n i ) mod 2) 2 i  ]2  =  [     ⌊  log2 n ⌋ ∏   i  = 0    Fi  (  ⌊  n  / 2 i⌋ mod 2)]2  =  [     ⌊  log2 n ⌋ ∏   i  = 0    (2 2 i + 1) (  ⌊  n  / 2 i⌋ 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)

     

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

[     ⌊  log2 n ⌋ ∏   i  = 0    (2 2 i + 1) (  ⌊  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

  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  / 2 i⌋ mod 2)]2  =  [     ⌊  log2 n ⌋ ∏   i  = 0    (2 2 i + 1) (  ⌊  n  / 2 i⌋ mod 2)]2 ,

then for any row

2 k + n, 0   ≤   n   ≤   2 k  −  1,

we have

     

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

[     k ∏   i  = 0    Fi   (  ⌊  n  / 2 i⌋ mod 2)]2  =  [     ⌊  log2 ( 2 k + n) ⌋ ∏   i  = 0    Fi   (  ⌊  n  / 2 i⌋ 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, ...}

See also

• Pascal's triangle

External links

• Antti Karttunen, On Pascal’s Triangle Modulo 2 in Fibonacci Representation, The Fibonacci Quarterly, Volume 42, Number 1, February 2004.