

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.


4



0, 1, 3, 4, 6, 7, 9, 11, 13, 15, 17, 19, 21, 24, 26, 29, 31, 34
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,3


COMMENTS

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.
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
The following remarkable theorem is due to M. S. Smith (email of Mar 06 2022).
Theorem: G contains no 4cycles.
Proof. Suppose the contrary, and assume the vertices t_1, t_2, t_3, t_4 form a 4cycle, 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.
Since the t_i are distinct, b_1 != b_4, b_2 != b_1, b_3 != b_2, and b_4 != b_3.
We also have
(*) b_1+b_3 = b_2+b_4 = t_1+t_2+t_3+t_4.
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
Let c(n) = A006855(n) denote the maximum number of edges in a graph on n nodes containing no 4cycle.
Corollary: a(n) <= c(n).
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).
Another corollary is that a(n) is bounded asymptotically by (n/4)*(sqrt(4n3)+1) (see A006855).
The theorem is remarkable, since before the only known values of a(n) were the trivial values for n <= 3.
In summary, we have a(n) >= A347301(n) for n >= 6, and
a(n) <= A006855(n) for all n.
From Thomas Scheuerle, Sep 23 2022: (Start)
Subgraphs of G consisting only of edges between positive numbers are free from any cycles. Proof: If b + c = 2^t then either (b1)XOR(c) or (b)XOR(c1) will be 2^t1. The properties of XOR allow in this case only a chain for Sidon sets. (XOR means bitwise exclusive or).
From this we can conclude that all cycles in the graph G must contain at least one negative number.
Conjecture A: The count of negative numbers in an optimal solution is either equal to the count of positive numbers or one less.
This leads to Conjecture B: a(n) <= floor((n+1)*3/2). (End)
Max Alekseyev points out that both conjectures are wrong.
(A) Counterexamples are given by examples from A347301:
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 }
(B) For n=14, this bound is 22, but it is smaller than a(14) = 24. N. J. A. Sloane, Sep 25 2022


REFERENCES

M. S. Smith, Email to N. J. A. Sloane, Mar 06 2022.


LINKS

Table of n, a(n) for n=1..18.
Max Alekseyev, A New Approach to Finding Upper Bounds for the "Powers of Two" Problem, Preliminary Note, Sep 25 2022
Matthew Bolan, Stan Wagon 1321 Solution, Sep 22, 2022 [Shows that a(10) = 15]
Alex Bradley, Pairwise Powers of 2 Problem, Sep 22 2022 [Short proof that there do not exist four distinct numbers all of whose pairwise sums are powers of 2]
C. R. J. Clapham, A. Flockhart, and J. Sheehan, Graphs without fourcycles, J. Graph Theory 13 (1) (1989) 2947
Daniel Darroch, Comments on Stan Wagon's Powers of 2 Problem, Sep 22 2022
Christof Haase, Decidability of the Powers of Two Problem, Sep 22 2022
Brady Haran and N. J. A. Sloane, Problems with Powers of Two, Youtube Numberphile Video, Sep 21 2022
Brady Haran and N. J. A. Sloane, STOP PRESS: Postscript to Problems with Powers of Two, Sep 21 2022
Noam Kimmel, Asymptotics (upper and lower bounds) for a(n)
Firas Melaih, On The OEIS Sequence A352178 [Shows a(10) = 15, a(12) < 21, and some impossibility results on the graphs]
Firas Melaih, a(11) = 17 [Proves a(11) = 17 from an uploaded paper]
Rob Pratt, The best lower bounds known for 1 <= n <= 100 as of Sep 25 2022 [Gives n, best lower bound known, and an example of an nset achieving that bound]
Thomas Scheuerle, The best lower bounds known for 1 <= n <= 351 as of Sep 28 2022 [Gives n, best lower bound known, and an example of an nset achieving that bound]
István Selek, A possible proof of the Powers of Two problem, Sep 22 2022 {A solution for the case n = 4 using linear algebra]
N. J. A. Sloane, The OnLine 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).
Stan Wagon, Problem of the Week 1321: Powers of Two, Apr 16 2021.
Stan Wagon, Problem of the Week 1321 (Solution)


FORMULA

a(n) <= (p1) + (np)*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) <= (p1) + (np)*(k1) does hold in most cases.  Thomas Scheuerle, Sep 26 2022


EXAMPLE

a(3) = 3 from S = {1, 3, 5}.
a(4) >= 4 from S = {3, 1, 3, 5}, a(4) <= A006855(4) = 4, so a(4) = 4.
a(5) >= 6 from S = {3, 1, 3, 5, 11}, a(5) <= A006855(5) = 6, so a(5) = 6.
From Thomas Scheuerle, Sep 26 2022: (Start)
a(13): { 11, 7, 5, 3, 1, 1, 3, 5, 7, 9, 11, 13, 15 }
13

9713511

15 > Four loose ends k = 4. Eight positive numbers p = 8.
a(13) = 21 < (p1) + (np)*k
a(10): {9, 5, 3, 1, 3, 5, 7, 9, 11, 13}
133511 79 > Two times two loose ends k = 4. Six positive numbers p = 6.
a(10) = 15 < (p1) + (np)*k
(End)


CROSSREFS

Cf. A006855, A347301, A357409.
Sequence in context: A247425 A236444 A286809 * A244239 A006855 A301766
Adjacent sequences: A352175 A352176 A352177 * A352179 A352180 A352181


KEYWORD

nonn,more,changed


AUTHOR

N. J. A. Sloane, Mar 07 2022


EXTENSIONS

a(10) from Matthew Bolan, Sep 22 2022  see link.  N. J. A. Sloane, Sep 22 2022
Edited by N. J. A. Sloane, Sep 22 2022
a(12)a(18) from Max Alekseyev, Sep 25 2022, Sep 29 2022


STATUS

approved



