login
The OEIS is supported by the many generous donors 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
Beeler, M., Gosper, R. W. and Schroeppel, R., HAKMEM, ITEM 23 (Schroeppel)
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
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 | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 19 01:57 EDT 2024. Contains 370952 sequences. (Running on oeis4.)