Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.
%I #216 Dec 25 2024 04:27:33
%S 0,1,3,4,6,7,9,11,13,15,17,19,21,24,26,29,31,34,36,39,41
%N Let S = {t_1, t_2, ..., t_n} be a set of n distinct integers and consider the sums t_i + t_j (i<j); a(n) is the maximum number of such sums that are powers of 2, over all choices for S.
%C Given distinct integers t_1, ..., t_n, form a graph G with n vertices labeled by the t_i, and with an edge from t_i to t_j, labeled t_i + t_j, whenever t_i + t_j is a power of 2.
%C See the Pratt link for the best lower bounds known, and examples of sets achieving these bounds, for 1 <= n <= 100. - _N. J. A. Sloane_, Sep 26 2022
%C The following remarkable theorem is due to M. S. Smith (email of Mar 06 2022).
%C Theorem: G contains no 4-cycles.
%C Proof. Suppose the contrary, and assume the vertices t_1, t_2, t_3, t_4 form a 4-cycle, with edges labeled b_1 = t_1+t_2, b_2 = t_2+t_3, b_3 = t_3+t_4, b_4 = t_4+t_1. The b_i are powers of 2.
%C Since the t_i are distinct, b_1 != b_4, b_2 != b_1, b_3 != b_2, and b_4 != b_3.
%C We also have
%C (*) b_1+b_3 = b_2+b_4 = t_1+t_2+t_3+t_4.
%C However, the powers of 2 form a Sidon set (all pairwise sums are distinct), so (*) implies that either b_1=b_2 and b_3=b_4 or b_1=b_4 and b_3=b_2, both of which are impossible. QED
%C Let c(n) = A006855(n) denote the maximum number of edges in a graph on n nodes containing no 4-cycle.
%C Corollary: a(n) <= c(n).
%C The values of c(n) agree with the lower bounds on a(n) for n <= 9 (see A347301), which establishes the first 9 values of a(n).
%C Another corollary is that a(n) is bounded asymptotically by (n/4)*(sqrt(4n-3)+1) (see A006855).
%C The theorem is remarkable, since before the only known values of a(n) were the trivial values for n <= 3.
%C In summary, we have a(n) >= A347301(n) for n >= 6, and
%C a(n) <= A006855(n) for all n.
%C From _Thomas Scheuerle_, Sep 23 2022: (Start)
%C Subgraphs of G consisting only of edges between positive numbers are free from any cycles. Proof: If b + c = 2^t then either (b-1)XOR(c) or (b)XOR(c-1) will be 2^t-1. The properties of XOR allow in this case only a chain for Sidon sets. (XOR means bitwise exclusive or).
%C From this we can conclude that all cycles in the graph G must contain at least one negative number.
%C Conjecture A: The count of negative numbers in an optimal solution is either equal to the count of positive numbers or one less.
%C This leads to Conjecture B: a(n) <= floor((n+1)*3/2). (End)
%C _Max Alekseyev_ points out that both conjectures are wrong.
%C (A) Counterexamples are given by examples from A347301:
%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 (B) For n=14, this bound is 22, but it is smaller than a(14) = 24. _N. J. A. Sloane_, Sep 25 2022
%D M. S. Smith, Email to N. J. A. Sloane, Mar 06 2022.
%H Max 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 Matthew Bolan, <a href="/A352178/a352178.pdf">Stan Wagon 1321 Solution</a>, Sep 22, 2022 [Shows that a(10) = 15]
%H Alex Bradley, <a href="/A352178/a352178_1.pdf">Pairwise Powers of 2 Problem</a>, Sep 22 2022 [Short proof that there do not exist four distinct numbers all of whose pairwise sums are powers of 2]
%H C. R. J. Clapham, A. Flockhart, and J. Sheehan, <a href="https://doi.org/10.1002/jgt.3190130107">Graphs without four-cycles</a>, J. Graph Theory 13 (1) (1989) 29-47
%H Charlotte Darroch, <a href="/A352178/a352178_7.txt">Comments on Stan Wagon's Powers of 2 Problem</a>, Sep 22 2022
%H Christof Haase, <a href="/A352178/a352178_2.txt">Decidability of the Powers of Two Problem</a>, Sep 22 2022
%H Péter Hajnal, <a href="https://doi.org/10.3390/a17020055">Binary Numeration System with Alternating Signed Digits and Its Graph Theoretical Relationship</a>, Algorithms (2024) Vol. 17, Art. No. 55. See p. 9.
%H Brady Haran and N. J. A. Sloane, <a href="https://youtu.be/IPoh5C9CcI8">Problems with Powers of Two</a>, Youtube Numberphile Video, Sep 21 2022
%H Brady Haran and N. J. A. Sloane, <a href="https://www.numberphile.com/stop-press">STOP PRESS: Postscript to Problems with Powers of Two</a>, Sep 21 2022
%H Noam Kimmel, <a href="/A352178/a352178_4.pdf">Asymptotics (upper and lower bounds) for a(n)</a>
%H Firas Melaih, <a href="/A352178/a352178_3.pdf">On The OEIS Sequence A352178</a> [Shows a(10) = 15, a(12) < 21, and some impossibility results on the graphs]
%H Firas Melaih, <a href="/A352178/a352178_3.txt">a(11) = 17</a> [Proves a(11) = 17 from an uploaded paper]
%H Rob Pratt, <a href="/A352178/a352178_5.txt">The best lower bounds known for 1 <= n <= 100 as of Sep 25 2022</a> [Gives n, best lower bound known, and an example of an n-set achieving that bound]
%H Thomas Scheuerle, <a href="/A352178/a352178_6.txt">The best lower bounds known for 1 <= n <= 351 as of Sep 28 2022</a> [Gives n, best lower bound known, and an example of an n-set achieving that bound]
%H István Selek, <a href="/A352178/a352178_2.pdf">A possible proof of the Powers of Two problem</a>, Sep 22 2022 [A solution for the case n = 4 using linear algebra]
%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 Stan Wagon, <a href="/A347301/a347301_1.pdf">Problem of the Week 1321: Powers of Two</a>, Apr 16 2021.
%F a(n) <= (p-1) + (n-p)*k. k is the count of loose ends of the subgraphs of positive numbers. Subgraphs means here the biggest sets of positive numbers connected by sums which are equal to a power of two. There may be multiple such sets which are not interconnected directly. From observation it appears that a(n) <= (p-1) + (n-p)*(k-1) does hold in most cases. - _Thomas Scheuerle_, Sep 26 2022
%F For n > 2, a(n) <= floor(a(n-1) * n / (n-2)). - _Max Alekseyev_, Jan 23 2023
%e a(3) = 3 from S = {-1, 3, 5}.
%e a(4) >= 4 from S = {-3, -1, 3, 5}, a(4) <= A006855(4) = 4, so a(4) = 4.
%e a(5) >= 6 from S = {-3, -1, 3, 5, 11}, a(5) <= A006855(5) = 6, so a(5) = 6.
%e From _Thomas Scheuerle_, Sep 26 2022: (Start)
%e a(13): { -11, -7, -5, -3, -1, 1, 3, 5, 7, 9, 11, 13, 15 }
%e 13
%e |
%e 9-7-1-3-5-11
%e |
%e 15 -> Four loose ends k = 4. Eight positive numbers p = 8.
%e a(13) = 21 < (p-1) + (n-p)*k
%e a(10): {-9, -5, -3, -1, 3, 5, 7, 9, 11, 13}
%e 13-3-5-11 7-9 -> Two times two loose ends k = 4. Six positive numbers p = 6.
%e a(10) = 15 < (p-1) + (n-p)*k
%e (End)
%Y Cf. A006855, A347301, A357409.
%K nonn,more
%O 1,3
%A _N. J. A. Sloane_, Mar 07 2022
%E a(10) from _Matthew Bolan_, Sep 22 2022 - see link. - _N. J. A. Sloane_, Sep 22 2022
%E Edited by _N. J. A. Sloane_, Sep 22 2022
%E a(12)-a(18) from _Max Alekseyev_, Sep 25 2022, Sep 29 2022
%E a(19)-a(20) from _Max Alekseyev_, Dec 02 2023
%E a(21) from _Max Alekseyev_, May 01 2024