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