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

%I A050600 #12 Sep 21 2021 06:18:05
%S A050600 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,
%T A050600 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,
%U A050600 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
%N A050600 Recursion counts for summation table A003056 with formula a(y,0) = y, a(y,x) = a((y XOR x),2*(y AND x)).
%C A050600 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.
%C A050600 For k=1..n-1: T(n,k) = T(n,n-k) = A080080(n-k,k) + 1. - _Reinhard Zumkeller_, Aug 03 2014
%H A050600 Reinhard Zumkeller, <a href="/A050600/b050600.txt">Rows n = 0..127 of triangle, flattened</a>
%H A050600 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>
%H A050600 <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>
%F A050600 a(n) -> add1c( (n-((trinv(n)*(trinv(n)-1))/2)), (((trinv(n)-1)*(((1/2)*trinv(n))+1))-n) )
%p A050600 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;
%t A050600 trinv[n_] := Floor[(1 + Sqrt[1 + 8*n])/2];
%t A050600 add1c[a_, b_] := add1c[a, b] = If[b == 0, 0, 1 + add1c[BitXor[a, b], 2*BitAnd[a, b]]];
%t A050600 a[n_] := add1c[n - (trinv[n]*(trinv[n] - 1))/2, (trinv[n] - 1)* ((1/2)*trinv[n] + 1) - n];
%t A050600 Table[a[n], {n, 0, 100}] (* _Jean-François Alcover_, Sep 21 2021, after Maple code *)
%o A050600 (Haskell)
%o A050600 import Data.Bits (xor, (.&.), shiftL)
%o A050600 a050600 n k = adder 0 (n - k) k where
%o A050600    adder :: Int -> Int -> Int -> Int
%o A050600    adder c u 0 = c
%o A050600    adder c u v = adder (c + 1) (u `xor` v) (shiftL (u .&. v) 1)
%o A050600 a050600_row n = map (a050600 n) $ reverse [0..n]
%o A050600 a050600_tabl = map a050600_row [0..]
%o A050600 -- _Reinhard Zumkeller_, Aug 02 2014
%Y A050600 Column 1: A001511, column 2: A050603, column 3: A050604.
%Y A050600 Cf. A050601, A050602, A003056, A048720 (for the Maple implementation of trinv and XORnos, ANDnos)
%Y A050600 Cf. A080080.
%K A050600 nonn,tabl
%O A050600 0,5
%A A050600 _Antti Karttunen_, Jun 22 1999