A050600 - OEIS

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

(list; table; graph; refs; listen; history; text; internal format)

OFFSET

0,5

COMMENTS

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

LINKS

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

FORMULA

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

MAPLE

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;

MATHEMATICA

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

PROG

(Haskell)

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

CROSSREFS

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.

Sequence in context: A357380 A278522 A024363 * A129691 A280750 A280748

Adjacent sequences: A050597 A050598 A050599 * A050601 A050602 A050603

KEYWORD

nonn,tabl

AUTHOR

Antti Karttunen, Jun 22 1999

STATUS

approved