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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A050602 Recursion counts for summation table A003056 with formula a(y,x): if (y AND x) = 0 then (y XOR x), otherwise = a((y XOR x),2*(y AND x)) 7
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

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.

The array begins:

0 0 0 0 0 0 0 0 ...

0 1 0 2 0 1 0 3 ...

0 0 1 1 0 0 2 2 ...

0 2 1 1 0 3 2 2 ...

0 0 0 0 1 1 1 1 ...

0 1 0 3 1 1 1 2 ...

0 0 2 2 1 1 1 1 ...

0 3 2 2 1 2 1 1 ...

...

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

Table of n, a(n) for n=0..119.

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

FORMULA

a(n) -> add3c( (n-((trinv(n)*(trinv(n)-1))/2)), (((trinv(n)-1)*(((1/2)*trinv(n))+1))-n) )

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

CROSSREFS

Row/Column 1: A007814, Row/Column 2: A050605, Row/Column 3: A050606.

Cf. A050600, A050601, A003056, A048720 (for the Maple implementation of trinv and XORnos, ANDnos).

Cf. also A192054.

Sequence in context: A079548 A175620 A079071 * A065040 A284688 A057595

Adjacent sequences:  A050599 A050600 A050601 * A050603 A050604 A050605

KEYWORD

nonn,tabl,nice

AUTHOR

Antti Karttunen, Jun 22 1999

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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified February 20 10:45 EST 2018. Contains 299385 sequences. (Running on oeis4.)