A354158 - OEIS

%I #11 Jul 26 2022 02:26:53

%S -1,-1,0,-1,2,0,2,-1,6,2,5,0,8,2,6,-1,14,6,11,2,15,5,11,0,20,8,15,2,

%T 20,6,14,-1,30,14,23,6,29,11,21,2,35,15,26,5,33,11,23,0,44,20,33,8,41,

%U 15,29,2,48,20,35,6,44,14,30,-1,62,30,47,14,57,23,41,6,65,29,48,11,59,21,41,2,75,35,56,15,68,26,48,5,77,33

%N The Bodlaender function: a(1) = -1; a(2*n) = a(n), a(2*n+1) = a(n+1) + n.

%H N. J. A. Sloane, <a href="/A354158/b354158.txt">Table of n, a(n) for n = 1..10000</a>

%H Hans L. Bodlaender, Jitender S. Deogun, Klaus Jansen, Ton Kloks, Dieter Kratsch, Haiko Müller, and Zsolt Tuza, <a href="https://doi.org/10.1137/S0895480195282550">Rankings of Graphs</a>, SIAM J. Discrete Math., 11 (1998), 168-181. See p. 179.

%H Andreas M. Hinz, Sandi Klavžar, and Sara Sabrina Zemljič, <a href="https://doi.org/10.1016/j.dam.2016.09.024">A survey and classification of Sierpiński-type graphs</a>, Discrete Applied Math., 217 (2017), 565-600. See Cor. 4.9.

%p g:=proc(n) option remember; if n = 1 then -1 elif (n mod 2) = 0 then g(n/2) else (n-1)/2 + g((n+1)/2); fi; end;

%o (Python)

%o from functools import lru_cache

%o @lru_cache(maxsize=None)

%o def a(n):

%o     if n == 1: return -1

%o     return a(n//2+1) + n//2 if n&1 else a(n//2)

%o print([a(n) for n in range(1, 91)]) # _Michael S. Branicky_, Jul 25 2022

%K sign

%O 1,5

%A _N. J. A. Sloane_, May 30 2022, following a suggestion from _Don Knuth_