cp's OEIS Frontend

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.

%I A099884 #73 Dec 23 2024 14:53:42
%S A099884 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,
%T A099884 68,102,85,128,192,160,240,136,204,170,255,256,384,320,480,272,408,
%U A099884 340,510,257,512,768,640,960,544,816,680,1020,514,771,1024,1536,1280,1920
%N 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.
%C A099884 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).
%C A099884 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
%H A099884 Paul D. Hanna, <a href="/A099884/b099884.txt">First 45 Rows of Triangle, in flattened form.</a>
%H A099884 SeqFan-mailing list, <a href="https://web.archive.org/web/*/http://list.seqfan.eu/oldermail/seqfan/2016-September/016788.html">Discussion of about related array A255483</a>
%H A099884 <a href="/index/Ge#GF2X">Index entries for sequences related to polynomials in ring GF(2)[X]</a>
%F A099884 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.
%F A099884 From _Antti Karttunen_, Sep 19 2016: (Start)
%F A099884 When viewed as a square array A(row,col), with row >= 0, col >= 0, the following recurrences and formulas are valid:
%F A099884 A(0,col) = A000079(col), for row > 0, A(row,col) = A048724(A(row-1, col)).
%F A099884 A(row,0) = A001317(row), for col > 0, A(row,col) = 2*A(row,col-1).
%F A099884 A(row,col) = A248663(A066117(row+1,col+1)) = A048675(A255483(row,col+1)).
%F A099884 (End)
%F A099884 With the definitions from _Antti Karttunen_ above, A(row+1, col) = A048720(3, A(row, col)). - _Peter Munn_, Jan 13 2020
%F A099884 A(n,k) = A193231(A(k,n)) = A091202(A036561(n,k)). - _Antti Karttunen_, Jan 18 2020
%e A099884 The main diagonal equals A001317 (Pascal's triangle mod 2 in decimal):
%e A099884 {1,3,5,15,17,51,85,255,257,771,1285,3855,...}, and defines the XOR BINOMIAL transform of the powers of 2.
%e A099884 Rows begin:
%e A099884   1;
%e A099884   2, 3;
%e A099884   4, 6, 5;
%e A099884   8, 12, 10, 15;
%e A099884   16, 24, 20, 30, 17;
%e A099884   32, 48, 40, 60, 34, 51;
%e A099884   64, 96, 80, 120, 68, 102, 85;
%e A099884   128, 192, 160, 240, 136, 204, 170, 255;
%e A099884   256, 384, 320, 480, 272, 408, 340, 510, 257;
%e A099884   512, 768, 640, 960, 544, 816, 680, 1020, 514, 771;
%e A099884   1024, 1536, 1280, 1920, 1088, 1632, 1360, 2040, 1028, 1542, 1285;
%e A099884   2048, 3072, 2560, 3840, 2176, 3264, 2720, 4080, 2056, 3084, 2570, 3855;
%e A099884   ...
%e A099884 From _Antti Karttunen_, Sep 19 2016: (Start)
%e A099884 Viewed as a square array, the top left corner looks like this:
%e A099884      1,    2,     4,     8,    16,     32,     64,    128
%e A099884      3,    6,    12,    24,    48,     96,    192,    384
%e A099884      5,   10,    20,    40,    80,    160,    320,    640
%e A099884     15,   30,    60,   120,   240,    480,    960,   1920
%e A099884     17,   34,    68,   136,   272,    544,   1088,   2176
%e A099884     51,  102,   204,   408,   816,   1632,   3264,   6528
%e A099884     85,  170,   340,   680,  1360,   2720,   5440,  10880
%e A099884    255,  510,  1020,  2040,  4080,   8160,  16320,  32640
%e A099884    257,  514,  1028,  2056,  4112,   8224,  16448,  32896
%e A099884    771, 1542,  3084,  6168, 12336,  24672,  49344,  98688
%e A099884   1285, 2570,  5140, 10280, 20560,  41120,  82240, 164480
%e A099884   3855, 7710, 15420, 30840, 61680, 123360, 246720, 493440
%e A099884   4369, 8738, 17476, 34952, 69904, 139808, 279616, 559232
%e A099884   ...
%e A099884 (End)
%e A099884 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
%t A099884 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 *)
%o A099884 (PARI) {T(n,k)=local(B);B=0;for(i=0,k,B=bitxor(B,binomial(k,i)%2*2^(n-i)));B}
%o A099884 for(n=0,10,for(k=0,n,print1(T(n,k),", "));print(""))
%o A099884 (Scheme)
%o A099884 (define (A099884 n) (A099884bi (A002262 n) (A025581 n)))
%o A099884 ;; Then use either this recurrence:
%o A099884 (define (A099884bi row col) (if (zero? row) (A000079 col) (A048724 (A099884bi (- row 1) col))))
%o A099884 ;; or this one:
%o A099884 (define (A099884bi row col) (if (zero? col) (A001317 row) (* 2 (A099884bi row (- col 1)))))
%o A099884 ;; _Antti Karttunen_, Sep 19 2016
%o A099884 (Python)
%o A099884 from sympy import binomial
%o A099884 def a(n):
%o A099884     return sum((binomial(n, i)%2)*2**i for i in range(n + 1))
%o A099884 def T(n, k): return 2**(n - k)*a(k)
%o A099884 for n in range(21): print([T(n, k) for k in range(n + 1)]) # _Indranil Ghosh_, Apr 11 2017
%Y A099884 Essentially GF(2)[X] analog of table A036561. - _Antti Karttunen_, Jan 18 2020
%Y A099884 Cf. A047999, A158875 (row sums).
%Y A099884 Cf. A000215, A003401, A048675, A048720, A048724, A066117, A248663, A255483, A276586.
%Y A099884 Cf. A000079 (first column of triangular table, the topmost row of square array).
%Y A099884 Cf. A001317 (the rightmost diagonal of triangular table, the leftmost column of square array).
%Y A099884 Cf. A099885, A117998 (central diagonals).
%Y A099884 Cf. A276618 (transpose), A091202, A193231.
%K A099884 nonn,tabl
%O A099884 0,2
%A A099884 _Paul D. Hanna_, Oct 28 2004
%E A099884 Square array interpretation added as a second, alternative description by _Antti Karttunen_, Sep 19 2016