A050602 - OEIS

The OEIS mourns the passing of Jim Simons and is grateful to the Simons Foundation for its support of research in many branches of science, including the OEIS.

The OEIS is supported by the many generous donors to the OEIS Foundation.

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 (list; table; graph; refs; listen; history; text; internal format)

	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], 2BitAnd[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.` `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`

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 18 23:43 EDT 2024. Contains 372666 sequences. (Running on oeis4.)