%I #93 Mar 14 2023 19:34:31
%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,
%T 54,56,59,61,65,67,71,73,77,79,83,85,89,91,95,97,101,103,107,109,113,
%U 115,119,121,125,127,131,133,137,139,143,146,149,152,155,159,162,166,169,173,176
%N 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.
%C 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.)
%C 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.
%C The values of a(n) for n <= 100 were found by _Rob Pratt_ using a MILP solver. See links.
%C Of course b(n) >= a(n). For b(n) see A352178. - _N. J. A. Sloane_, Mar 07 2022
%C b(5) >= 6 from {-3, -1, 3, 5, 11} whereas a(5) = 5 from {-4, -3, -1, 3, 5}.
%C Comments from _Rob Pratt_: (Start)
%C With [-100,100] bounds, the optimal values for n=11 to 15 are 17, 19, 21, 24, 26.
%C With [-70,70] bounds, the optimal values for n=16 to 20 are 29, 31, 34, 36, 39.
%C The following two infinite families of odd consecutive integers appear to yield an n*log n lower bound.
%C (C1) For n odd, take S = {4-n, 6-n, ..., -3, -1, 1, 3, ..., n, n+2}.
%C (C2) For n even, take S = {5-n, 7-n, ..., -3, -1, 1, 3, ..., n+1, n+3}.
%C This is not always optimal. For example, you can do at least 1 better for n = 27 and 28.
%C 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;
%C 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;
%C 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;
%C 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.
%C (End)
%C Comments from _N. J. A. Sloane_, Feb 21 2022: (Start)
%C 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, .... (*)
%C 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)
%C From _Chai Wah Wu_, Sep 21 2022: (Start)
%C 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.
%C It appears that a(n) can be achieved using S with only odd integers (this may be true for A352178 as well):
%C a(2) = 1: { -3, 5 }
%C a(3) = 3: { -1, 3, 5 }
%C a(4) = 4: { -3, -1, 3, 5 }
%C a(5) = 5: { -3, -1, 1, 3, 5 }
%C a(6) = 7: { -5, -3, -1, 5, 7, 9 }
%C a(7) = 9: { -5, -3, -1, 3, 5, 7, 9 }
%C a(8) = 11: { -7, -5, -3, -1, 5, 7, 9, 11 }
%C a(9) = 13: { -7, -5, -3, -1, 3, 5, 7, 9, 11 }
%C a(10) = 15: { -9, -5, -3, -1, 3, 5, 7, 9, 11, 13 }
%C a(11) = 17: { -9, -7, -5, -3, -1, 3, 5, 7, 9, 11, 13 }
%C a(12) = 19: { -9, -7, -5, -3, -1, 1, 3, 5, 7, 9, 11, 13 }
%C a(13) = 21: { -11, -7, -5, -3, -1, 1, 3, 5, 7, 9, 11, 13, 15 }
%C (End)
%C Comments from _Eric Snyder_, Oct 22 2022: (Start)
%C 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.)
%C 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.
%C 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).
%C 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)
%H Rob Pratt, <a href="/A347301/b347301.txt">Table of n, a(n) for n = 1..100</a>
%H Max A. Alekseyev, <a href="https://arxiv.org/abs/2303.02872">On computing sets of integers with maximum number of pairs summing to powers of 2</a>, arXiv:2303.02872 [math.CO], 2023.
%H Rob Pratt, <a href="/A347301/a347301.txt">Output from MILP solver</a> [n, a(n), S]
%H N. J. A. Sloane, <a href="https://vimeo.com/704569041/4ffa06b95e">The On-Line Encyclopedia of Integer Sequences: An illustrated guide with many unsolved problems</a>, Guest Lecture given in Doron Zeilberger's Experimental Mathematics Math640 Class, Rutgers University, Spring Semester, Apr 28 2022: <a href="https://sites.math.rutgers.edu/~zeilberg/EM22/C27.pdf">Slides</a>; <a href="http://NeilSloane.com/doc/Math640.04.2022.pdf">Slides (an alternative source)</a>.
%H N. J. A. Sloane and Brady Haran, <a href="https://youtube.com/watch?v=IPoh5C9CcI8">Problems with Powers of Two</a>, Numberphile video, 2022
%H Stan Wagon, <a href="/A347301/a347301_1.pdf">Problem of the Week 1321: Powers of Two</a>, Apr 16 2021.
%H Stan Wagon, <a href="/A347301/a347301_3.pdf">Problem of the Week 1321 (Solution)</a>
%H Eric Snyder, <a href="/A347301/a347301_1.txt">Table of n, allowable M for n = 1..500</a>
%e a(3) = b(3) = 3 from S = {-1, 3, 5}.
%Y See A352178 for the unrestricted problem.
%K nonn
%O 1,3
%A _N. J. A. Sloane_, Aug 28 2021, based on information supplied by _Rob Pratt_ and _Stan Wagon_