cp's OEIS Frontend

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)

For this sequence we check the sums for all possible pairs between two distinct members of a set of consecutive odd numbers, we count as valid results of the form 2^m, valid sums are obviously >= 1.

The related sequence A357574 counts the pairs that add to a power of 2.

For sequences of consecutive odd numbers the maximum number of pairs that add to a power of 2 will never be obtained if the sequence starts with numbers greater than 1. Obviously for sequences of all negative numbers, we will not obtain any valid pair.

It appears likely that an optimal solution for A352178 will contain only odd numbers as a mix of odd and even numbers would lead to two unconnected graphs. Let us now assume A352178(k) has an optimal solution in odd numbers only, then there exists a least m such that a(k+m) uses a superset of the same solution pairs used in A352178(k). It would be interesting to know if m has a bound in relation to k.

An optimal set delivering a(n) pairs summing to powers of 2 can be formed by n-A357409(n) first negative odd numbers and A357409(n) first positive odd numbers, that is, by the odd numbers in the interval [-2*(n-A357409(n))+1, 2*A357409(n)-1].

a(n) is in many cases equal to A347301(n) but there are some deviations: a(3) = 2 but A347301(3) = 3, a(29) = 62 but A347301(29) = 61, a(31) = 68 but A347301(32) = 67, a(33) = 74 but A347301(33) = 73, ... . Hence it appears that a(n) may be used as an improved lower bound for A352178(n) in many cases.

Conjecture: a(n+1) - a(n) = k, if n is even then A129868(k-1) < n < A129868(k), if n is odd then A020515(k) <= n < A020515(k+1).