A050601 -id:A050601 - cp's OEIS frontend

A050600 Recursion counts for summation table A003056 with formula a(y,0) = y, a(y,x) = a((y XOR x),2*(y AND x)).

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

Offset: 0

Antti Karttunen, Jun 22 1999

Count the summation table A003056 with recursive formula based on identity A+B = (A XOR B)+ 2*(A AND B) given by Schroeppel and then this table gives the number of recursion steps to get the final result.

For k=1..n-1: T(n,k) = T(n,n-k) = A080080(n-k,k) + 1. - Reinhard Zumkeller, Aug 03 2014

Reinhard Zumkeller, Rows n = 0..127 of triangle, flattened
Beeler, M., Gosper, R. W. and Schroeppel, R., HAKMEM, ITEM 23 (Schroeppel)
Index entries for sequences related to binary expansion of n

Column 1: A001511, column 2: A050603, column 3: A050604.
Cf. A050601, A050602, A003056, A048720 (for the Maple implementation of trinv and XORnos, ANDnos)
Cf. A080080.

import Data.Bits (xor, (.&.), shiftL)
a050600 n k = adder 0 (n - k) k where
   adder :: Int -> Int -> Int -> Int
   adder c u 0 = c
   adder c u v = adder (c + 1) (u `xor` v) (shiftL (u .&. v) 1)
a050600_row n = map (a050600 n) $ reverse [0..n]
a050600_tabl = map a050600_row [0..]
-- Reinhard Zumkeller, Aug 02 2014

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

trinv[n_] := Floor[(1 + Sqrt[1 + 8*n])/2];
add1c[a_, b_] := add1c[a, b] = If[b == 0, 0, 1 + add1c[BitXor[a, b], 2*BitAnd[a, b]]];
a[n_] := add1c[n - (trinv[n]*(trinv[n] - 1))/2, (trinv[n] - 1)* ((1/2)*trinv[n] + 1) - n];
Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Sep 21 2021, after Maple code *)

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

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

Original entry on oeis.org

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

Antti Karttunen, Jun 22 1999

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.

			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.

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

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.

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;

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

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

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.

Name edited by Antti Karttunen, Sep 04 2023

cp's OEIS Frontend

A050600 Recursion counts for summation table A003056 with formula a(y,0) = y, a(y,x) = a((y XOR x),2*(y AND x)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

Formula