OFFSET
1,2
COMMENTS
Optimal binary search with equality.
LINKS
Robert Israel, Table of n, a(n) for n = 1..10000
Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications, Preprint 2016.
Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications, ACM Transactions on Algorithms, 13:4 (2017), #47; DOI: 10.1145/3127585.
FORMULA
a(n) = min_{1<=k<=n-1} n + a(k) + a(n-1-k).
a(n) = A123753(n) - floor(3*(n+1)/2). - Peter Luschny, Nov 30 2017
From Robert Israel, Nov 30 2017: (Start)
Empirical: a(n+3)-a(n+2)-a(n+1)+a(n) = 1 if n = 2^k-3 or 2^k-2 for some k, 0 otherwise.
Empirical g.f.: (2*x^2+x^3)/(1-x-x^2+x^3) + Sum_{k>=2} x^{2^k}/(1-x)^2. (End)
EXAMPLE
a_5 = 8 = 5 + a_1 + a_3; this is the smallest example where choosing the middle value is not optimal.
MAPLE
f:= proc(n) option remember;
n+min(seq(procname(k)+procname(n-1-k), k=1..n-1))
end proc:
f(1):= 0: f(0):= 0:
map(f, [$1..100]); # Robert Israel, Nov 30 2017
MATHEMATICA
a[n_] := (n+1)(1+IntegerLength[n+1, 2])-2^IntegerLength[n+1, 2]-Quotient[3n+1, 2];
Table[a[n], {n, 1, 60}] (* Peter Luschny, Dec 02 2017 *)
PROG
(Python)
def A097383(n):
s, i, z = -n//2, n, 1
while 0 <= i: s += i; i -= z; z += z
return s
print([A097383(n) for n in range(1, 61)]) # Peter Luschny, Nov 30 2017
(Python)
def A097383(n): return (n+1)*(m:=n.bit_length())-(1<<m)-(n-1>>1) # Chai Wah Wu, Mar 29 2023
CROSSREFS
KEYWORD
easy,nonn
AUTHOR
Franklin T. Adams-Watters, Aug 11 2004
STATUS
approved