A347301 Let S be a set of n distinct integers in the range -n-3 to n+3, and consider the sums s+t of pairs of distinct elements of S; a(n) is the maximum number of such sums that are powers of 2, over all choices for S.

0, 1, 3, 4, 5, 7, 9, 11, 13, 15, 17, 19, 21, 24, 26, 29, 31, 34, 36, 39, 41, 44, 46, 49, 51, 54, 56, 59, 61, 65, 67, 71, 73, 77, 79, 83, 85, 89, 91, 95, 97, 101, 103, 107, 109, 113, 115, 119, 121, 125, 127, 131, 133, 137, 139, 143, 146, 149, 152, 155, 159, 162, 166, 169, 173, 176

Offset: 1

Author

N. J. A. Sloane, Aug 28 2021, based on information supplied by Rob Pratt and Stan Wagon

Keywords

• nonn

Comments

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)

Examples

			a(3) = b(3) = 3 from S = {-1, 3, 5}.
		

Links

• Rob Pratt, Table of n, a(n) for n = 1..100
• Max A. Alekseyev, On computing sets of integers with maximum number of pairs summing to powers of 2, arXiv:2303.02872 [math.CO], 2023.
• Rob Pratt, Output from MILP solver [n, a(n), S]
• N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences: An illustrated guide with many unsolved problems, Guest Lecture given in Doron Zeilberger's Experimental Mathematics Math640 Class, Rutgers University, Spring Semester, Apr 28 2022: Slides; Slides (an alternative source).
• N. J. A. Sloane and Brady Haran, Problems with Powers of Two, Numberphile video, 2022
• Stan Wagon, Problem of the Week 1321: Powers of Two, Apr 16 2021.
• Stan Wagon, Problem of the Week 1321 (Solution)
• Eric Snyder, Table of n, allowable M for n = 1..500

Crossrefs

See A352178 for the unrestricted problem.