Note: this stuff is a bit haphazardous (or just a pile of amateur's
notes),
and the question is after all about the multiplication table of the powers of
GF(2)[X] polynomials x^2+1 (binary encoding 101 = 5.) at the topmost row and
x^2+x+1 (binary encoding 111 = 7.) at the leftmost column.
This relates to the array A048710
and related sequences in Neil J.A. Sloane's Encyclopedia of Integer Sequences.
Note: This document uses HTML numerical entity-encodings for various
mathematical symbols found in Unicode at range U+2000 - U+23FF,
so you should have an appropriate font file available in your browser
to see all the symbols (such as large "Pi" for product) correctly.
- 90x150 family of single non-zero site.
| 1 | 5 | 17 | 85 | 257 | 1285 | 4369 | 21845 | 65537 | 327685 |
|---|
| 7 | 27 | 119 | 427 | 1799 | 6939 | 30583 | 109227 | 458759 | 1769499 |
|---|
| 21 | 65 | 325 | 1105 | 5397 | 16705 | 83013 | 283985 | 1376277 | 4259905 |
|---|
| 107 | 455 | 1755 | 7607 | 27499 | 116423 | 450011 | 1944247 | 7012459 | 29819335 |
|---|
| 273 | 1365 | 4097 | 20485 | 69649 | 348245 | 1052929 | 5264645 | 17891601 | 89458005 |
|---|
| 1911 | 6827 | 28679 | 110619 | 487543 | 1749419 | 7370503 | 28420891 | 125241207 | 447421099 |
|---|
| 5189 | 17745 | 86037 | 266305 | 1331525 | 4527185 | 22103317 | 68440385 | 340071493 | 1162954065 |
|---|
| 28123 | 121527 | 438379 | 1864135 | 7190235 | 31157687 | 112647019 | 476952263 | 1843097051 | 7964383927 |
|---|
| 65793 | 328965 | 1118481 | 5592405 | 16777217 | 83886085 | 285212689 | 1426063445 | 4311744769 | 21558723845 |
|---|
| 460551 | 1776411 | 7829367 | 27962027 | 117440519 | 452984859 | 1996488823 | 7163871659 | 30182213383 | 116417108763 |
|---|
Specific formulas and identities:
- The nth term of the first row can be generated
with
| ∞ | |
| ∏ |
(biti (n) 22i+1) + 1 |
| i=o | |
where biti (n) stands for ith bit of
the integer n (the least significant bit is bit0),
and n is the nth generation after the the initial single
non-zero site 1 (which is the generation 0).
The 22i+1 in the formula is the i+1th
Fermat number.
- 1-family factored:
-
| 1 | ``(5) | ``(17) | ``(5)*``(17) | ``(257) | ``(5)*``(257) | ``(17)*``(257) | ``(5)*``(17)*``(257) | ``(65537) | ``(5)*``(65537) |
|---|
| ``(7) | ``(3)^3 | ``(7)*``(17) | ``(7)*``(61) | ``(7)*``(257) | ``(3)^3*``(257) | ``(7)*``(17)*``(257) | ``(3)*``(23)*``(1583) | ``(7)*``(65537) | ``(3)^3*``(65537) |
|---|
| ``(3)*``(7) | ``(5)*``(13) | ``(5)^2*``(13) | ``(5)*``(13)*``(17) | ``(3)*``(7)*``(257) | ``(5)*``(13)*``(257) | ``(3)*``(7)*``(59)*``(67) | ``(5)*``(13)*``(17)*``(257) | ``(3)*``(7)*``(65537) | ``(5)*``(13)*``(65537) |
|---|
| ``(107) | ``(5)*``(7)*``(13) | ``(3)^3*``(5)*``(13) | ``(7607) | ``(107)*``(257) | ``(116423) | ``(450011) | ``(29)*``(67043) | ``(107)*``(65537) | ``(5)*``(7)*``(13)*``(65537) |
|---|
| ``(3)*``(7)*``(13) | ``(3)*``(5)*``(7)*``(13) | ``(17)*``(241) | ``(5)*``(17)*``(241) | ``(17)^2*``(241) | ``(5)*``(17)^2*``(241) | ``(17)*``(241)*``(257) | ``(5)*``(17)*``(241)*``(257) | ``(3)*``(7)*``(13)*``(65537) | ``(3)*``(5)*``(7)*``(13)*``(65537) |
|---|
| ``(3)*``(7)^2*``(13) | ``(6827) | ``(7)*``(17)*``(241) | ``(3)^3*``(17)*``(241) | ``(7)*``(17)^2*``(241) | ``(7)*``(17)*``(61)*``(241) | ``(7)*``(17)*``(241)*``(257) | ``(773)*``(36767) | ``(3)*``(7)^2*``(13)*``(65537) | ``(65537)*``(6827) |
|---|
| ``(5189) | ``(3)*``(5)*``(7)*``(13)^2 | ``(3)*``(7)*``(17)*``(241) | ``(5)*``(13)*``(17)*``(241) | ``(5)^2*``(13)*``(17)*``(241) | ``(5)*``(13)*``(17)^2*``(241) | ``(22103317) | ``(5)*``(13)*``(17)*``(241)*``(257) | ``(65537)*``(5189) | ``(3)*``(5)*``(7)*``(13)^2*``(65537) |
|---|
| ``(28123) | ``(3)^3*``(7)*``(643) | ``(17)*``(107)*``(241) | ``(5)*``(7)*``(13)*``(17)*``(241) | ``(3)^3*``(5)*``(13)*``(17)*``(241) | ``(11)*``(29)*``(97673) | ``(83)*``(1357193) | ``(12347)*``(38629) | ``(65537)*``(28123) | ``(619)*``(3593)*``(3581) |
|---|
| ``(3)*``(7)*``(13)*``(241) | ``(3)*``(5)*``(7)*``(13)*``(241) | ``(3)*``(7)*``(13)*``(17)*``(241) | ``(3)*``(5)*``(7)*``(13)*``(17)*``(241) | ``(97)*``(257)*``(673) | ``(5)*``(97)*``(257)*``(673) | ``(17)*``(97)*``(257)*``(673) | ``(5)*``(17)*``(97)*``(257)*``(673) | ``(97)*``(257)^2*``(673) | ``(5)*``(97)*``(257)^2*``(673) |
|---|
| ``(3)*``(7)^2*``(13)*``(241) | ``(3)^4*``(7)*``(13)*``(241) | ``(3)*``(7)^2*``(13)*``(17)*``(241) | ``(27962027) | ``(7)*``(97)*``(257)*``(673) | ``(3)^3*``(97)*``(257)*``(673) | ``(7)*``(17)*``(97)*``(257)*``(673) | ``(7)*``(61)*``(97)*``(257)*``(673) | ``(7)*``(97)*``(257)^2*``(673) | ``(3)^3*``(97)*``(257)^2*``(673) |
|---|
Detseq is [1, -8, 256, -32768, 16777216, -1430224109568, 11716395905581056, -60920408332222813175808, 7984959760921108568579506176, -4832821973017079976234876288368640]
First 6 factored: [1, -``(2)^3, ``(2)^8, -``(2)^15, ``(2)^24, -``(2)^32*``(3)^2*``(37)]
- 90x150 family of 3 (two adjacent non-zero sites)
-
| 3 | 15 | 51 | 255 | 771 | 3855 | 13107 | 65535 | 196611 | 983055 |
|---|
| 9 | 45 | 153 | 765 | 2313 | 11565 | 39321 | 196605 | 589833 | 2949165 |
|---|
| 63 | 195 | 975 | 3315 | 16191 | 50115 | 249039 | 851955 | 4128831 | 12779715 |
|---|
| 189 | 585 | 2925 | 9945 | 48573 | 150345 | 747117 | 2555865 | 12386493 | 38339145 |
|---|
| 819 | 4095 | 12291 | 61455 | 208947 | 1044735 | 3158787 | 15793935 | 53674803 | 268374015 |
|---|
| 2457 | 12285 | 36873 | 184365 | 626841 | 3134205 | 9476361 | 47381805 | 161024409 | 805122045 |
|---|
| 15567 | 53235 | 258111 | 798915 | 3994575 | 13581555 | 66309951 | 205321155 | 1020214479 | 3488862195 |
|---|
| 46701 | 159705 | 774333 | 2396745 | 11983725 | 40744665 | 198929853 | 615963465 | 3060643437 | 10466586585 |
|---|
| 197379 | 986895 | 3355443 | 16777215 | 50331651 | 251658255 | 855638067 | 4278190335 | 12935234307 | 64676171535 |
|---|
| 592137 | 2960685 | 10066329 | 50331645 | 150994953 | 754974765 | 2566914201 | 12834571005 | 38805702921 | 194028514605 |
|---|
Specific formulas and identities:
- Because all even-length binary palindromes are divisible by 3
(follows from the divisibility shorthand rule) and rules 90 and 150
preserve even-length binary palindromes as such (and 3, in binary 11 is also one),
then it follows that all the terms in this array are divisible by 3.
- The nth term of the first row can be generated
with
| ∞ | |
| 3 | ∏ |
(biti (n) 22i+1) + 1 |
| i=o | |
i.e., it's just the sequence rule90(1) multiplied by three.
These two sequences (rule90(1) and rule90(3)) can be combined
to form the sequence
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,84215045,
252645135,286331153,858993459,1431655765,4294967295,4294967297
which is produced from Pascal's triangle computed modulo 2,
by interpreting each row as a binary number and converting it to decimal
(Sloane's A001317).
The formula for the nth term (1 is the zeroth term) of this sequence is:
| ∞ | |
| ∏ |
(biti (n) 22i) + 1 |
| i=o | |
| ``(3) | ``(3)*``(5) | ``(3)*``(17) | ``(3)*``(5)*``(17) | ``(3)*``(257) | ``(3)*``(5)*``(257) | ``(3)*``(17)*``(257) | ``(3)*``(5)*``(17)*``(257) | ``(3)*``(65537) | ``(3)*``(5)*``(65537) |
|---|
| ``(3)^2 | ``(3)^2*``(5) | ``(3)^2*``(17) | ``(3)^2*``(5)*``(17) | ``(3)^2*``(257) | ``(3)^2*``(5)*``(257) | ``(3)^2*``(17)*``(257) | ``(3)^2*``(5)*``(17)*``(257) | ``(3)^2*``(65537) | ``(3)^2*``(5)*``(65537) |
|---|
| ``(3)^2*``(7) | ``(3)*``(5)*``(13) | ``(3)*``(5)^2*``(13) | ``(3)*``(5)*``(13)*``(17) | ``(3)^2*``(7)*``(257) | ``(3)*``(5)*``(13)*``(257) | ``(3)^2*``(7)*``(59)*``(67) | ``(3)*``(5)*``(13)*``(17)*``(257) | ``(3)^2*``(7)*``(65537) | ``(3)*``(5)*``(13)*``(65537) |
|---|
| ``(3)^3*``(7) | ``(3)^2*``(5)*``(13) | ``(3)^2*``(5)^2*``(13) | ``(3)^2*``(5)*``(13)*``(17) | ``(3)^3*``(7)*``(257) | ``(3)^2*``(5)*``(13)*``(257) | ``(3)^3*``(7)*``(59)*``(67) | ``(3)^2*``(5)*``(13)*``(17)*``(257) | ``(3)^3*``(7)*``(65537) | ``(3)^2*``(5)*``(13)*``(65537) |
|---|
| ``(3)^2*``(7)*``(13) | ``(3)^2*``(5)*``(7)*``(13) | ``(3)*``(17)*``(241) | ``(3)*``(5)*``(17)*``(241) | ``(3)*``(17)^2*``(241) | ``(3)*``(5)*``(17)^2*``(241) | ``(3)*``(17)*``(241)*``(257) | ``(3)*``(5)*``(17)*``(241)*``(257) | ``(3)^2*``(7)*``(13)*``(65537) | ``(3)^2*``(5)*``(7)*``(13)*``(65537) |
|---|
| ``(3)^3*``(7)*``(13) | ``(3)^3*``(5)*``(7)*``(13) | ``(3)^2*``(17)*``(241) | ``(3)^2*``(5)*``(17)*``(241) | ``(3)^2*``(17)^2*``(241) | ``(3)^2*``(5)*``(17)^2*``(241) | ``(3)^2*``(17)*``(241)*``(257) | ``(3)^2*``(5)*``(17)*``(241)*``(257) | ``(3)^3*``(7)*``(13)*``(65537) | ``(3)^3*``(5)*``(7)*``(13)*``(65537) |
|---|
| ``(3)*``(5189) | ``(3)^2*``(5)*``(7)*``(13)^2 | ``(3)^2*``(7)*``(17)*``(241) | ``(3)*``(5)*``(13)*``(17)*``(241) | ``(3)*``(5)^2*``(13)*``(17)*``(241) | ``(3)*``(5)*``(13)*``(17)^2*``(241) | ``(3)*``(22103317) | ``(3)*``(5)*``(13)*``(17)*``(241)*``(257) | ``(3)*``(65537)*``(5189) | ``(3)^2*``(5)*``(7)*``(13)^2*``(65537) |
|---|
| ``(3)^2*``(5189) | ``(3)^3*``(5)*``(7)*``(13)^2 | ``(3)^3*``(7)*``(17)*``(241) | ``(3)^2*``(5)*``(13)*``(17)*``(241) | ``(3)^2*``(5)^2*``(13)*``(17)*``(241) | ``(3)^2*``(5)*``(13)*``(17)^2*``(241) | ``(3)^2*``(22103317) | ``(3)^2*``(5)*``(13)*``(17)*``(241)*``(257) | ``(3)^2*``(65537)*``(5189) | ``(3)^3*``(5)*``(7)*``(13)^2*``(65537) |
|---|
| ``(3)^2*``(7)*``(13)*``(241) | ``(3)^2*``(5)*``(7)*``(13)*``(241) | ``(3)^2*``(7)*``(13)*``(17)*``(241) | ``(3)^2*``(5)*``(7)*``(13)*``(17)*``(241) | ``(3)*``(97)*``(257)*``(673) | ``(3)*``(5)*``(97)*``(257)*``(673) | ``(3)*``(17)*``(97)*``(257)*``(673) | ``(3)*``(5)*``(17)*``(97)*``(257)*``(673) | ``(3)*``(97)*``(257)^2*``(673) | ``(3)*``(5)*``(97)*``(257)^2*``(673) |
|---|
| ``(3)^3*``(7)*``(13)*``(241) | ``(3)^3*``(5)*``(7)*``(13)*``(241) | ``(3)^3*``(7)*``(13)*``(17)*``(241) | ``(3)^3*``(5)*``(7)*``(13)*``(17)*``(241) | ``(3)^2*``(97)*``(257)*``(673) | ``(3)^2*``(5)*``(97)*``(257)*``(673) | ``(3)^2*``(17)*``(97)*``(257)*``(673) | ``(3)^2*``(5)*``(17)*``(97)*``(257)*``(673) | ``(3)^2*``(97)*``(257)^2*``(673) | ``(3)^2*``(5)*``(97)*``(257)^2*``(673) |
|---|
Detseq is [3, 0, 0, 0, 0, 0, 0, 0, 0, 0]
First 6 factored: [``(3), 0, 0, 0, 0, 0]
- 90x150 family of 11 (first asymmetric family, a reflection of family 13)
| 11 | 39 | 187 | 599 | 2827 | 10023 | 48059 | 152919 | 720907 | 2555943 |
|---|
| 49 | 245 | 801 | 4005 | 12593 | 62965 | 205345 | 1026725 | 3211313 | 16056565 |
|---|
| 151 | 715 | 2535 | 11899 | 38807 | 182731 | 650983 | 3036539 | 9896087 | 46858955 |
|---|
| 997 | 3185 | 15797 | 52065 | 255717 | 818545 | 4032693 | 13347425 | 65340389 | 208735345 |
|---|
| 3003 | 9559 | 45067 | 159783 | 766139 | 2454103 | 11582219 | 41047847 | 196807611 | 626468183 |
|---|
| 12833 | 64165 | 200753 | 1003765 | 3281697 | 16408485 | 51585329 | 257926645 | 841036321 | 4205181605 |
|---|
| 40679 | 189819 | 618647 | 2929355 | 10385895 | 48733819 | 158984087 | 748583371 | 2665979623 | 12439905659 |
|---|
| 252085 | 834145 | 4084709 | 13048945 | 64712117 | 213310305 | 1047377637 | 3353046385 | 16520763573 | 54667360865 |
|---|
| 723723 | 2565927 | 12303291 | 39146839 | 184549387 | 654311463 | 3137339579 | 10049552983 | 47429192459 | 168158045991 |
|---|
| 3223857 | 16119285 | 52568609 | 262843045 | 822083633 | 4110418165 | 13438550817 | 67192754085 | 211275493681 | 1056377468405 |
|---|
Open Questions
If one constructs nxn matrices from the first n rows and n columns
of family 1 array, starting from one-element matrix (1),
and then takes determinants of said matrices, one gets the following
sequence:
1, -8, 256, -32768, 16777216, -1430224109568, 11716395905581056, -60920408332222813175808,
7984959760921108568579506176, -4832821973017079976234876288368640,
5525009511402910343196523934081000952299520, 18820801145508339494005058842109037023969738596810752,
-631521292222481682984507154573546419406274963804461794852864,
-140565071983931462129512671771145008085327489473528585465379755185405952,
656825717285994265915881005475721771490442235095485220947160470276117728579591077888,
-124903659782448333748176984520146423136383977700258437072289954390562087842565967146958299594752,
1072914267832652136516226496267854281004293863842006555947118683873591556682600051237592645270459786461184,
-51486397534763262695839535220948937922412519124586169165401057529006730135169346976172734834031636092959687064575541248,
etc.
Here one almost sees the formula
det(n) = (-2)(n2+2n)
(where det(0) corresponds to 1x1 matrix)
but the sixth term is suddenly -1430224109568 instead of
"expected" -34359738368 (1430224109568/34359738368 is 333/8)
and after that the rule does not hold any longer.
The determinant sequence of family 1 matrices factored is:
1,
-(2)3,
(2)8,
-(2)15,
24
(2) ,
32 2
-(2) (3) (37),
45 2
(2) (3) (37),
55
-(2) (3) (41) (59) (233),
72
(2) (3) (41) (59) (233),
89
-(2) (3) (5) (17) (67) (457),
103 3
(2) (3) (5) (17) (67) (457) (7753),
121 2 2
(2) (3) (11) (164447) (5099) (7753),
146 2 2
-(2) (3) (11) (164447) (5099) (7753),
164 4
-(2) (3) (2702937917) (3541337) (7753),
182 3
(2) (3) (11) (193) (2702937917) (3541337) (32971) (5923),
207 2
-(2) (3) (11) (193) (12026591582911) (13531849) (32971) (5923),
240 2
(2) (3) (11) (193) (12026591582911) (13531849) (32971) (5923),
266 2
-(2) (3) (11) (193) (2609074344427) (44602669170061) (32971) (5923),
299 2
(2) (3) (97) (44602669170061) (2609074344427) (97187) (9185513),
332 2
(2) (3) (5) (97) (359) (4118489) (9381911382433) (11065213) (97187) (9185513)
etc.