login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 as A(0,0), A(0,1), A(1,0), A(0,2), A(1,1), A(2,0), ... 32
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

Paul D. Hanna, First 45 Rows of Triangle, in flattened form.

Discussion of SeqFan-mailing list about related array A255483

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.

From Antti Karttunen, Sep 19 2016: (Start)

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).

A(row,col) = A248663(A066117(row+1,col+1)) = A048675(A255483(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; ...

From Antti Karttunen, Sep 19 2016: (Start)

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)

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)

(define (A099884 n) (A099884bi (A002262 n) (A025581 n)))

;; 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)))))

;; Antti Karttunen, Sep 19 2016

(Python)

from sympy import binomial

def a(n): return sum([(binomial(n, i)%2)*2**i for i in xrange(n + 1)])

def T(n, k): return 2**(n - k)*a(k)

for n in xrange(21): print [T(n, k) for k in xrange(n + 1)] # Indranil Ghosh, Apr 11 2017

CROSSREFS

Cf. A047999, A158875 (row sums).

Cf. A000215, A003401, A048675, A048724, A066117, A248663, A255483, A276586.

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).

Cf. A276618 (transpose).

Sequence in context: A054582 A257797 A220347 * A191446 A230764 A276685

Adjacent sequences:  A099881 A099882 A099883 * A099885 A099886 A099887

KEYWORD

nonn,tabl

AUTHOR

Paul D. Hanna, Oct 28 2004

EXTENSIONS

Square array interpretation added as a second, alternative description by Antti Karttunen, Sep 19 2016

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 17 06:06 EDT 2019. Contains 324183 sequences. (Running on oeis4.)