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

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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)). 8
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
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.
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.
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
KEYWORD
nonn,tabl,nice
AUTHOR
Antti Karttunen, Jun 22 1999
EXTENSIONS
Name edited by Antti Karttunen, Sep 04 2023
STATUS
approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 18 22:56 EDT 2024. Contains 370952 sequences. (Running on oeis4.)