|
| |
|
|
A099884
|
|
XOR difference triangle of the powers of 2, read by rows; Square array A(row,col): A(0,col) = 2^col, A(row,col) = A048724(A(row-1, col)) for row > 0, read by descending antidiagonals.
|
|
33
|
|
|
|
1, 2, 3, 4, 6, 5, 8, 12, 10, 15, 16, 24, 20, 30, 17, 32, 48, 40, 60, 34, 51, 64, 96, 80, 120, 68, 102, 85, 128, 192, 160, 240, 136, 204, 170, 255, 256, 384, 320, 480, 272, 408, 340, 510, 257, 512, 768, 640, 960, 544, 816, 680, 1020, 514, 771, 1024, 1536, 1280, 1920
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,2
|
|
|
COMMENTS
|
Define an "XOR difference triangle" for a sequence A by the following process. Start with A in the leftmost column. Generate the next column by performing the XOR operation between adjacent terms of the prior column. Repeat this process to generate the XOR difference triangle for A. Further, we define the "XOR BINOMIAL transform" of A as the main diagonal in the XOR difference triangle for A. The XOR BINOMIAL transform is its self-inverse. Let a sequence B be the XOR BINOMIAL transform of A, then we may express B by: B(n) = SumXOR_{k=0..n} A047999(n,k)*A(k), which is equivalent to: B(n) = (C(n,0)mod 2)*A(0) XOR (C(n,1)mod 2)*A(1) XOR (C(n,2)mod 2)*A(2) XOR ... XOR (X(n,n)mod 2)*A(n), where the coefficients are C(n,k)(mod 2) = A047999(n,k).
This sequence is a rearrangement of the numbers which are 2^k times distinct Fermat numbers (numbers of the form 2^(2^m) + 1). This matches the sizes of polygons constructible with compass and straightedge (A003401) up to 2^32+1, which is the first nonprime Fermat number. - Franklin T. Adams-Watters, Jun 16 2006
|
|
|
LINKS
|
|
|
|
FORMULA
|
T(n, k) = 2^(n-k)*A001317(k). T(n, n) = A001317(n) = SumXOR_{k=0..n} A047999(n, k)*2^k, where SumXOR is the analog of summation under the binary XOR operation.
When viewed as a square array A(row,col), with row >= 0, col >= 0, the following recurrences and formulas are valid:
A(0,col) = A000079(col), for row > 0, A(row,col) = A048724(A(row-1, col)).
A(row,0) = A001317(row), for col > 0, A(row,col) = 2*A(row,col-1).
(End)
|
|
|
EXAMPLE
|
The main diagonal equals A001317 (Pascal's triangle mod 2 in decimal):
{1,3,5,15,17,51,85,255,257,771,1285,3855,...}, and defines the XOR BINOMIAL transform of the powers of 2.
Rows begin:
1;
2, 3;
4, 6, 5;
8, 12, 10, 15;
16, 24, 20, 30, 17;
32, 48, 40, 60, 34, 51;
64, 96, 80, 120, 68, 102, 85;
128, 192, 160, 240, 136, 204, 170, 255;
256, 384, 320, 480, 272, 408, 340, 510, 257;
512, 768, 640, 960, 544, 816, 680, 1020, 514, 771;
1024, 1536, 1280, 1920, 1088, 1632, 1360, 2040, 1028, 1542, 1285;
2048, 3072, 2560, 3840, 2176, 3264, 2720, 4080, 2056, 3084, 2570, 3855;
...
Viewed as a square array, the top left corner looks like this:
1, 2, 4, 8, 16, 32, 64, 128
3, 6, 12, 24, 48, 96, 192, 384
5, 10, 20, 40, 80, 160, 320, 640
15, 30, 60, 120, 240, 480, 960, 1920
17, 34, 68, 136, 272, 544, 1088, 2176
51, 102, 204, 408, 816, 1632, 3264, 6528
85, 170, 340, 680, 1360, 2720, 5440, 10880
255, 510, 1020, 2040, 4080, 8160, 16320, 32640
257, 514, 1028, 2056, 4112, 8224, 16448, 32896
771, 1542, 3084, 6168, 12336, 24672, 49344, 98688
1285, 2570, 5140, 10280, 20560, 41120, 82240, 164480
3855, 7710, 15420, 30840, 61680, 123360, 246720, 493440
4369, 8738, 17476, 34952, 69904, 139808, 279616, 559232
...
(End)
The square array shown above can be viewed as a subtable of a multiplication table with particular relevance to the carryless multiplication defined by A048720, as the first column gives the A048720 powers of 3 (and the first row gives powers of 2, which are the same as in standard arithmetic). - Peter Munn, Jan 13 2020
|
|
|
MATHEMATICA
|
a[n_]:= Sum[Mod[Binomial[n, i], 2]*2^i, {i, 0, n}]; T[n_, k_]:=2^(n - k)a[k]; Table[T[n, k], {n, 0, 20}, {k, 0, n}] // Flatten (* Indranil Ghosh, Apr 11 2017 *)
|
|
|
PROG
|
(PARI) {T(n, k)=local(B); B=0; for(i=0, k, B=bitxor(B, binomial(k, i)%2*2^(n-i))); B}
for(n=0, 10, for(k=0, n, print1(T(n, k), ", ")); print(""))
(Scheme)
;; Then use either this recurrence:
(define (A099884bi row col) (if (zero? row) (A000079 col) (A048724 (A099884bi (- row 1) col))))
;; or this one:
(define (A099884bi row col) (if (zero? col) (A001317 row) (* 2 (A099884bi row (- col 1)))))
(Python)
from sympy import binomial
def a(n):
return sum((binomial(n, i)%2)*2**i for i in range(n + 1))
def T(n, k): return 2**(n - k)*a(k)
for n in range(21): print([T(n, k) for k in range(n + 1)]) # Indranil Ghosh, Apr 11 2017
|
|
|
CROSSREFS
|
Cf. A000079 (first column of triangular table, the topmost row of square array).
Cf. A001317 (the rightmost diagonal of triangular table, the leftmost column of square array).
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
Square array interpretation added as a second, alternative description by Antti Karttunen, Sep 19 2016
|
|
|
STATUS
|
approved
|
| |
|
|
