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

 

Logo


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

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: A213629 A278522 A024363 * A129691 A280750 A280748

Adjacent sequences:  A050597 A050598 A050599 * A050601 A050602 A050603

KEYWORD

nonn,tabl

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:33 EST 2018. Contains 299385 sequences. (Running on oeis4.)