cp's OEIS Frontend

Equals n-1 times the expected number of probes for a successful binary search in a size n-1 list.

Piecewise linear: breakpoints at powers of 2 with values given by A000337.

a(n) is the number of digits in the binary representation of all the numbers 1 to n-1. - Hieronymus Fischer, Dec 05 2006

It is also coincidentally the maximum number of comparisons for merge sort. - Li-yao Xia, Nov 18 2015

Sequence consists of A011782(n) n+1's. - Jon Perry, Apr 04 2004

For n > 0: a(n) = A003314(n+1) - A003314(n) = A123753(n) - A123753(n-1). - Reinhard Zumkeller, Oct 12 2006

For k >= 2, k appears 2^(k-2) times consecutively. - Bernard Schott, Jun 08 2019

Also length of binary representation of 2n. - Michel Marcus, Oct 28 2020

Optimal binary search with equality.

For a given set S, we count pairs (s,t) with s in S, t in S, s < t, and s+t equal to a power of 2. (The powers need not be distinct.)

Arises in studying Stan Wagon's Problem of the Week 1321, which asks for the maximum number b(n) if S can be any set of n distinct integers.

The values of a(n) for n <= 100 were found by Rob Pratt using a MILP solver. See links.

Of course b(n) >= a(n). For b(n) see A352178. - N. J. A. Sloane, Mar 07 2022

b(5) >= 6 from {-3, -1, 3, 5, 11} whereas a(5) = 5 from {-4, -3, -1, 3, 5}.

Comments from Rob Pratt: (Start)

With [-100,100] bounds, the optimal values for n=11 to 15 are 17, 19, 21, 24, 26.

With [-70,70] bounds, the optimal values for n=16 to 20 are 29, 31, 34, 36, 39.

The following two infinite families of odd consecutive integers appear to yield an n*log n lower bound.

(C1) For n odd, take S = {4-n, 6-n, ..., -3, -1, 1, 3, ..., n, n+2}.

(C2) For n even, take S = {5-n, 7-n, ..., -3, -1, 1, 3, ..., n+1, n+3}.

This is not always optimal. For example, you can do at least 1 better for n = 27 and 28.

n = 27: S = {-23, -21, -19, -17, -15, -13, -11, -9, -7, -5, -3, -1, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29} yields 56;

n = 28: S = {-23, -21, -19, -17, -15, -13, -11, -9, -7, -5, -3, -1, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31} yields 59;

n = 27: S = {-21, -19, -17, -15, -13, -11, -9, -7, -5, -3, -1, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 37} yields 57;

n = 28: S = {-21, -19, -17, -15, -13, -11, -9, -7, -5, -3, -1, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 35, 37} yields 60.

(End)

Comments from N. J. A. Sloane, Feb 21 2022: (Start)

Construction (C1) can be analyzed as follows. For n = 1, 3, 5, 7, ... the number of powers of 2 are 0, 2, 5, 9, 13, 17, 21, 26, 31, 36, 41, 46, 51, 56, 61, 67, 73, 79, 85, .... (*)

I computed 200 terms of (*), took first differences, and then the RUNS transform, getting essentially A070941, which implies that (*) appears to be A003314((n+1)/2)-3, which is (1/2)*n*log_2(n) - O(n). This is a plausible lower bound on a(n) for all n, and could even be the true order of growth. (End)

From Chai Wah Wu, Sep 21 2022: (Start)

If for S = {t_i}_i, all the integers t_i are even, then the set S generates the same number of powers of 2 as {t_i/2}_i. This is because 2a+2b is a power of 2 if and only if a+b is a power of 2.

It appears that a(n) can be achieved using S with only odd integers (this may be true for A352178 as well):

a(2) = 1: { -3, 5 }

a(3) = 3: { -1, 3, 5 }

a(4) = 4: { -3, -1, 3, 5 }

a(5) = 5: { -3, -1, 1, 3, 5 }

a(6) = 7: { -5, -3, -1, 5, 7, 9 }

a(7) = 9: { -5, -3, -1, 3, 5, 7, 9 }

a(8) = 11: { -7, -5, -3, -1, 5, 7, 9, 11 }

a(9) = 13: { -7, -5, -3, -1, 3, 5, 7, 9, 11 }

a(10) = 15: { -9, -5, -3, -1, 3, 5, 7, 9, 11, 13 }

a(11) = 17: { -9, -7, -5, -3, -1, 3, 5, 7, 9, 11, 13 }

a(12) = 19: { -9, -7, -5, -3, -1, 1, 3, 5, 7, 9, 11, 13 }

a(13) = 21: { -11, -7, -5, -3, -1, 1, 3, 5, 7, 9, 11, 13, 15 }

(End)

Comments from Eric Snyder, Oct 22 2022: (Start)

Construction (C1), along with the variable M from S. Wagon's solution linked below, is not unique to each n. For instance, for n = 128, all of M = {9, 11, 13, 15, 17} result in the same value, a(n) = 399. (However, for n = 4^p, M = 1 + 2^p does seem to be unique.)

If we consider only the central value of M for each n, M appears to be a stepwise function that "prefers" values near powers of 2, or halfway between powers of 2.

Conjecture: Construction (C1), with proper values of M, will compute the majority of maximal values for a(n). The exceptions, like 27, 28 above, seem to cluster near (7/8)*2^k, with a run from n = 54 to n = 59, and another from n = 111 to n = 124 (comparing values from (C1) to those provided by T. Scheuerle in A352178).

These exceptions seem to arise because including 2^k+1 and/or 2^k+3 in the set allows for connections to -1 and -3 (as well as lower negative numbers), where having 2^k-1 or 2^k-3 in the set of values would only connect to lower negative numbers. (End)

The external path length of a tree is the sum of the levels of its external nodes (i.e. leaves).

The external path length of a tree is the sum of the levels of its external nodes (i.e. leaves).

The external path length of a tree is the sum of the levels of its external nodes (i.e. leaves).