cp's OEIS Frontend

A352178 Let S = {t_1, t_2, ..., t_n} be a set of n distinct integers and consider the sums t_i + t_j (i a(n) is the maximum number of such sums that are powers of 2, over all choices for S.

%I A352178 #216 Dec 25 2024 04:27:33
%S A352178 0,1,3,4,6,7,9,11,13,15,17,19,21,24,26,29,31,34,36,39,41
%N A352178 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 A352178 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 A352178 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 A352178 The following remarkable theorem is due to M. S. Smith (email of Mar 06 2022).
%C A352178 Theorem: G contains no 4-cycles.
%C A352178 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 A352178 Since the t_i are distinct, b_1 != b_4, b_2 != b_1, b_3 != b_2, and b_4 != b_3.
%C A352178 We also have
%C A352178    (*) b_1+b_3 = b_2+b_4 = t_1+t_2+t_3+t_4.
%C A352178 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 A352178 Let c(n) = A006855(n) denote the maximum number of edges in a graph on n nodes containing no 4-cycle.
%C A352178 Corollary: a(n) <= c(n).
%C A352178 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 A352178 Another corollary is that a(n) is bounded asymptotically by (n/4)*(sqrt(4n-3)+1) (see A006855).
%C A352178 The theorem is remarkable, since before the only known values of a(n) were the trivial values for n <= 3.
%C A352178 In summary, we have a(n) >= A347301(n) for n >= 6, and
%C A352178 a(n) <= A006855(n) for all n.
%C A352178 From _Thomas Scheuerle_, Sep 23 2022: (Start)
%C A352178 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 A352178 From this we can conclude that all cycles in the graph G must contain at least one negative number.
%C A352178 Conjecture A: The count of negative numbers in an optimal solution is either equal to the count of positive numbers or one less.
%C A352178 This leads to Conjecture B: a(n) <= floor((n+1)*3/2). (End)
%C A352178 _Max Alekseyev_ points out that both conjectures are wrong.
%C A352178 (A)  Counterexamples are given by examples from A347301:
%C A352178   a(12) = 19: {  -9, -7, -5, -3, -1, 1, 3,  5,  7,  9, 11, 13 }
%C A352178   a(13) = 21: { -11, -7, -5, -3, -1, 1, 3,  5,  7,  9, 11, 13, 15 }
%C A352178 (B)  For n=14, this bound is 22, but it is smaller than a(14) = 24. _N. J. A. Sloane_, Sep 25 2022
%D A352178 M. S. Smith, Email to N. J. A. Sloane, Mar 06 2022.
%H A352178 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 A352178 Matthew Bolan, <a href="/A352178/a352178.pdf">Stan Wagon 1321 Solution</a>, Sep 22, 2022 [Shows that a(10) = 15]
%H A352178 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 A352178 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 A352178 Charlotte Darroch, <a href="/A352178/a352178_7.txt">Comments on Stan Wagon's Powers of 2 Problem</a>, Sep 22 2022
%H A352178 Christof Haase, <a href="/A352178/a352178_2.txt">Decidability of the Powers of Two Problem</a>, Sep 22 2022
%H A352178 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 A352178 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 A352178 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 A352178 Noam Kimmel, <a href="/A352178/a352178_4.pdf">Asymptotics (upper and lower bounds) for a(n)</a>
%H A352178 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 A352178 Firas Melaih, <a href="/A352178/a352178_3.txt">a(11) = 17</a> [Proves a(11) = 17 from an uploaded paper]
%H A352178 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 A352178 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 A352178 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 A352178 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 A352178 Stan Wagon, <a href="/A347301/a347301_1.pdf">Problem of the Week 1321: Powers of Two</a>, Apr 16 2021.
%F A352178 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 A352178 For n > 2, a(n) <= floor(a(n-1) * n / (n-2)). - _Max Alekseyev_, Jan 23 2023
%e A352178 a(3) = 3 from S = {-1, 3, 5}.
%e A352178 a(4) >= 4 from S = {-3, -1, 3, 5}, a(4) <= A006855(4) = 4, so a(4) = 4.
%e A352178 a(5) >= 6 from S = {-3, -1, 3, 5, 11},  a(5) <= A006855(5) = 6, so a(5) = 6.
%e A352178 From _Thomas Scheuerle_, Sep 26 2022: (Start)
%e A352178 a(13): { -11, -7, -5, -3, -1, 1, 3,  5,  7,  9, 11, 13, 15 }
%e A352178       13
%e A352178       |
%e A352178 9-7-1-3-5-11
%e A352178     |
%e A352178     15  -> Four loose ends k = 4. Eight positive numbers p = 8.
%e A352178 a(13) = 21 < (p-1) + (n-p)*k
%e A352178 a(10): {-9, -5, -3, -1, 3, 5, 7, 9, 11, 13}
%e A352178   13-3-5-11  7-9 -> Two times two loose ends k = 4. Six positive numbers p = 6.
%e A352178 a(10) = 15 < (p-1) + (n-p)*k
%e A352178 (End)
%Y A352178 Cf. A006855, A347301, A357409.
%K A352178 nonn,more
%O A352178 1,3
%A A352178 _N. J. A. Sloane_, Mar 07 2022
%E A352178 a(10) from _Matthew Bolan_, Sep 22 2022 - see link. - _N. J. A. Sloane_, Sep 22 2022
%E A352178 Edited by _N. J. A. Sloane_, Sep 22 2022
%E A352178 a(12)-a(18) from _Max Alekseyev_, Sep 25 2022, Sep 29 2022
%E A352178 a(19)-a(20) from _Max Alekseyev_, Dec 02 2023
%E A352178 a(21) from _Max Alekseyev_, May 01 2024