A050602 - OEIS

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

%I #46 Oct 11 2024 12:44:00

%S 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,

%T 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,

%U 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

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

%C 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

%C 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.

%C 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.

%H Antti Karttunen, <a href="/A050602/b050602.txt">Table of n, a(n) for n = 0..33152; the first 257 antidiagonals, flattened</a>

%H Beeler, M., Gosper, R. W. and Schroeppel, R., <a href="http://www.inwap.com/pdp10/hbaker/hakmem/boolean.html#item23">HAKMEM, ITEM 23 (Schroeppel)</a> [(A AND B) + (A OR B) = A + B = (A XOR B) + 2 (A AND B).]

%H Nicholas Pippenger, <a href="http://dx.doi.org/10.1006/jagm.2002.1216">Analysis of carry propagation in addition: an elementary approach</a>, J. Algorithms 42 (2002), 317-333.

%H <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>

%F 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.

%e The top left corner of the square array:

%e | 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15

%e -----+--------------------------------------------------------

%e 0 | 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,

%e 1 | 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4,

%e 2 | 0, 0, 1, 1, 0, 0, 2, 2, 0, 0, 1, 1, 0, 0, 3, 3,

%e 3 | 0, 2, 1, 1, 0, 3, 2, 2, 0, 2, 1, 1, 0, 4, 3, 3,

%e 4 | 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 2, 2, 2, 2,

%e 5 | 0, 1, 0, 3, 1, 1, 1, 2, 0, 1, 0, 4, 2, 2, 2, 2,

%e 6 | 0, 0, 2, 2, 1, 1, 1, 1, 0, 0, 3, 3, 2, 2, 2, 2,

%e 7 | 0, 3, 2, 2, 1, 2, 1, 1, 0, 4, 3, 3, 2, 2, 2, 2,

%e 8 | 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1,

%e 9 | 0, 1, 0, 2, 0, 1, 0, 4, 1, 1, 1, 2, 1, 1, 1, 3,

%e 10 | 0, 0, 1, 1, 0, 0, 3, 3, 1, 1, 1, 1, 1, 1, 2, 2,

%e 11 | 0, 2, 1, 1, 0, 4, 3, 3, 1, 2, 1, 1, 1, 3, 2, 2,

%e 12 | 0, 0, 0, 0, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1,

%e 13 | 0, 1, 0, 4, 2, 2, 2, 2, 1, 1, 1, 3, 1, 1, 1, 2,

%e 14 | 0, 0, 3, 3, 2, 2, 2, 2, 1, 1, 2, 2, 1, 1, 1, 1,

%e 15 | 0, 4, 3, 3, 2, 2, 2, 2, 1, 3, 2, 2, 1, 2, 1, 1,

%e etc.

%p 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;

%t 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 *)

%o (PARI)

%o up_to = 120;

%o A050602sq(x,y) = if(!bitand(x,y), 0, 1+A050602sq(bitxor(x,y),2*bitand(x,y)));

%o 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); };

%o v050602 = A050602list(up_to);

%o A050602(n) = v050602[1+n]; \\ _Antti Karttunen_, Sep 04 2023

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

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

%Y Cf. also A192054.

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

%K nonn,tabl,nice

%O 0,12

%A _Antti Karttunen_, Jun 22 1999

%E Name edited by _Antti Karttunen_, Sep 04 2023