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

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, 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, 24, 13, 14, 8, 16, 9, 10, 6, 64, 33, 34, 18, 36, 19, 20, 11, 40, 21, 22, 12

Offset: 0

Author

Ralf Stephan, Oct 14 2003

Keywords

• nonn
• easy

Links

• Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
• N. J. A. Sloane and J. A. Sellers, On non-squashing partitions, Discrete Math., 294 (2005), 259-274.

Crossrefs

This is Guy Steele's sequence GS(5, 4) (see A135416); compare GS(4, 5): A135529.

A048678(k) is where k appears first in the sequence.

Cf. A000120, A003714, A004718, A005940, A048675, A048679, A080100, A090639.

A left inverse of A277020.

Cf. also A277006.

Programs

Haskell

import Data.List (transpose)
a087808 n = a087808_list !! n
a087808_list = 0 : concat
   (transpose [map (+ 1) a087808_list, map (* 2) $ tail a087808_list])
-- Reinhard Zumkeller, Mar 18 2015

Maple

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;

Mathematica

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

PARI

a(n)=if(n<1,0,if(n%2==0,2*a(n/2),a((n-1)/2)+1))

Python

from functools import lru_cache
@lru_cache(maxsize=None)
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

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

Formula

a(n) = A135533(n)+1-2^(A000523(n)+1-A000120(n)). - Don Knuth, Mar 01 2008

From Antti Karttunen, Oct 07 2016: (Start)

a(n) = A048675(A005940(n+1)).

For all n >= 0, a(A003714(n)) = A048679(n).

For all n >= 0, a(A277020(n)) = n.

(End)