cp's OEIS Frontend

A087808 a(0) = 0; a(2n) = 2a(n), a(2n+1) = a(n) + 1.

%I A087808 #32 Mar 08 2022 15:20:16
%S A087808 0,1,2,2,4,3,4,3,8,5,6,4,8,5,6,4,16,9,10,6,12,7,8,5,16,9,10,6,12,7,8,
%T A087808 5,32,17,18,10,20,11,12,7,24,13,14,8,16,9,10,6,32,17,18,10,20,11,12,7,
%U A087808 24,13,14,8,16,9,10,6,64,33,34,18,36,19,20,11,40,21,22,12
%N A087808 a(0) = 0; a(2n) = 2a(n), a(2n+1) = a(n) + 1.
%H A087808 Reinhard Zumkeller, <a href="/A087808/b087808.txt">Table of n, a(n) for n = 0..10000</a>
%H A087808 N. J. A. Sloane and J. A. Sellers, <a href="http://dx.doi.org/10.1016/j.disc.2004.11.014">On non-squashing partitions</a>, Discrete Math., 294 (2005), 259-274.
%F A087808 a(n) = A135533(n)+1-2^(A000523(n)+1-A000120(n)). - _Don Knuth_, Mar 01 2008
%F A087808 From _Antti Karttunen_, Oct 07 2016: (Start)
%F A087808 a(n) = A048675(A005940(n+1)).
%F A087808 For all n >= 0, a(A003714(n)) = A048679(n).
%F A087808 For all n >= 0, a(A277020(n)) = n.
%F A087808 (End)
%p A087808 S := 2; f := proc(n) global S; option remember; if n=0 then RETURN(0); fi; if n mod 2 = 0 then RETURN(S*f(n/2)); else f((n-1)/2)+1; fi; end;
%t A087808 a[0]=0; a[n_] := a[n] = If[EvenQ[n], 2*a[n/2], a[(n-1)/2]+1]; Array[a,76,0] (* _Jean-François Alcover_, Aug 12 2017 *)
%o A087808 (PARI) a(n)=if(n<1,0,if(n%2==0,2*a(n/2),a((n-1)/2)+1))
%o A087808 (Haskell)
%o A087808 import Data.List (transpose)
%o A087808 a087808 n = a087808_list !! n
%o A087808 a087808_list = 0 : concat
%o A087808    (transpose [map (+ 1) a087808_list, map (* 2) $ tail a087808_list])
%o A087808 -- _Reinhard Zumkeller_, Mar 18 2015
%o A087808 (Scheme) (define (A087808 n) (cond ((zero? n) n) ((even? n) (* 2 (A087808 (/ n 2)))) (else (+ 1 (A087808 (/ (- n 1) 2)))))) ;; _Antti Karttunen_, Oct 07 2016
%o A087808 (Python)
%o A087808 from functools import lru_cache
%o A087808 @lru_cache(maxsize=None)
%o A087808 def A087808(n): return 0 if n == 0 else A087808(n//2) + (1 if n % 2 else A087808(n//2)) # _Chai Wah Wu_, Mar 08 2022
%Y A087808 This is Guy Steele's sequence GS(5, 4) (see A135416); compare GS(4, 5): A135529.
%Y A087808 A048678(k) is where k appears first in the sequence.
%Y A087808 Cf. A000120, A003714, A004718, A005940, A048675, A048679, A080100, A090639.
%Y A087808 A left inverse of A277020.
%Y A087808 Cf. also A277006.
%K A087808 nonn,easy
%O A087808 0,3
%A A087808 _Ralf Stephan_, Oct 14 2003