A050602 Square array A(x,y), read by antidiagonals, where A(x,y) = 0 if (x AND y) = 0, otherwise A(x,y) = 1+A(x XOR y, 2*(x AND y)).

0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 2, 1, 2, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 2, 3, 1, 3, 2, 3, 0, 0, 0, 2, 2, 1, 1, 2, 2, 0, 0, 0, 1, 0, 2, 1, 1, 1, 2, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 2, 1, 2, 0, 2, 1, 2, 0, 2, 1, 2, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0

Offset

0,12

Comments

Array is symmetric and is read by antidiagonals: (0,0), (0,1), (1,0), (0,2), (1,1), (2,0), etc. - Antti Karttunen, Sep 04 2023

Comment from N. J. A. Sloane, Jun 21 2011: Apparently the same as the following sequence. Infinite square array read by antidiagonals, where T(m,n) = length of longest carry propagation when u and v are added in binary, for u >= 0, v >= 0.

See A192054 for definition of carry propagation. For example, T(3,5) = 3, since adding 011 + 101 in binary, the initial 1 propagates three places.

Links

Antti Karttunen, Table of n, a(n) for n = 0..33152; the first 257 antidiagonals, flattened

Beeler, M., Gosper, R. W. and Schroeppel, R., HAKMEM, ITEM 23 (Schroeppel) [(A AND B) + (A OR B) = A + B = (A XOR B) + 2 (A AND B).]

Nicholas Pippenger, Analysis of carry propagation in addition: an elementary approach, J. Algorithms 42 (2002), 317-333.

Index entries for sequences related to binary expansion of n

Formula

If A004198(x,y) = 0, then A(x,y) = 0, otherwise A(x,y) = 1 + A(A003987(x,y), 2*A004198(x,y)), where A004198 and A003987 are bitwise-AND and bitwise-XOR respectively.

Example

The top left corner of the square array:
     |  0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15
-----+--------------------------------------------------------
   0 |  0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  0,  0,  0,  0,  0,  0,
   1 |  0, 1, 0, 2, 0, 1, 0, 3, 0, 1,  0,  2,  0,  1,  0,  4,
   2 |  0, 0, 1, 1, 0, 0, 2, 2, 0, 0,  1,  1,  0,  0,  3,  3,
   3 |  0, 2, 1, 1, 0, 3, 2, 2, 0, 2,  1,  1,  0,  4,  3,  3,
   4 |  0, 0, 0, 0, 1, 1, 1, 1, 0, 0,  0,  0,  2,  2,  2,  2,
   5 |  0, 1, 0, 3, 1, 1, 1, 2, 0, 1,  0,  4,  2,  2,  2,  2,
   6 |  0, 0, 2, 2, 1, 1, 1, 1, 0, 0,  3,  3,  2,  2,  2,  2,
   7 |  0, 3, 2, 2, 1, 2, 1, 1, 0, 4,  3,  3,  2,  2,  2,  2,
   8 |  0, 0, 0, 0, 0, 0, 0, 0, 1, 1,  1,  1,  1,  1,  1,  1,
   9 |  0, 1, 0, 2, 0, 1, 0, 4, 1, 1,  1,  2,  1,  1,  1,  3,
  10 |  0, 0, 1, 1, 0, 0, 3, 3, 1, 1,  1,  1,  1,  1,  2,  2,
  11 |  0, 2, 1, 1, 0, 4, 3, 3, 1, 2,  1,  1,  1,  3,  2,  2,
  12 |  0, 0, 0, 0, 2, 2, 2, 2, 1, 1,  1,  1,  1,  1,  1,  1,
  13 |  0, 1, 0, 4, 2, 2, 2, 2, 1, 1,  1,  3,  1,  1,  1,  2,
  14 |  0, 0, 3, 3, 2, 2, 2, 2, 1, 1,  2,  2,  1,  1,  1,  1,
  15 |  0, 4, 3, 3, 2, 2, 2, 2, 1, 3,  2,  2,  1,  2,  1,  1,
etc.

Maple

add3c := proc(a, b) option remember; if(0 = ANDnos(a, b)) then RETURN(0); else RETURN(1+add3c(XORnos(a, b), 2*ANDnos(a, b))); fi; end;

Mathematica

a[n_, k_] := a[n, k] = If[0 == BitAnd[n, k], 0, 1 + a[BitXor[n, k], 2*BitAnd[n, k]]]; Table[a[n - k, k], {n, 0, 14}, {k, 0, n}] // Flatten (* Jean-François Alcover, Jan 16 2014, updated Mar 06 2016 after Maple *)

Prog

(PARI)
up_to = 120;
A050602sq(x, y) = if(!bitand(x, y), 0, 1+A050602sq(bitxor(x, y), 2*bitand(x, y)));
A050602list(up_to) = { my(v = vector(up_to), i=0); for(a=0, oo, for(col=0, a, i++; if(i > up_to, return(v)); v[i] = A050602sq(col, a-col))); (v); };
v050602 = A050602list(up_to);
A050602(n) = v050602[1+n]; \\ Antti Karttunen, Sep 04 2023

Crossrefs

Row/Column 1: A007814, Row/Column 2: A050605, Row/Column 3: A050606. See also A372554 [A(n, 2n+1)].

Cf. A003056, A003987, A004198, A050600, A050601, A048720.

Cf. also A192054.

Cf. also A072030 (A285721) for similar arrays computed for an elementary Euclidean algorithm.

Sequence in context: A319812 A079071 A322795 * A065040 A284688 A057595

Adjacent sequences: A050599 A050600 A050601 * A050603 A050604 A050605

Keyword

nonn,tabl,nice

Author

Antti Karttunen, Jun 22 1999

Extensions

Name edited by Antti Karttunen, Sep 04 2023

Status

approved