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 4-cycles.
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.
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 4-cycle.
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(4n-3)+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 (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).
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
Max Alekseyev, On computing sets of integers with maximum number of pairs summing to powers of 2, arXiv:2303.02872 [math.CO], 2023.
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 four-cycles, J. Graph Theory 13 (1) (1989) 29-47
Charlotte 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
Péter Hajnal, Binary Numeration System with Alternating Signed Digits and Its Graph Theoretical Relationship, Algorithms (2024) Vol. 17, Art. No. 55. See p. 9.
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 n-set 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 n-set 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 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).
Stan Wagon, Problem of the Week 1321: Powers of Two, Apr 16 2021.
FORMULA
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
For n > 2, a(n) <= floor(a(n-1) * n / (n-2)). - Max Alekseyev, Jan 23 2023
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
|
9-7-1-3-5-11
|
15 -> Four loose ends k = 4. Eight positive numbers p = 8.
a(13) = 21 < (p-1) + (n-p)*k
a(10): {-9, -5, -3, -1, 3, 5, 7, 9, 11, 13}
13-3-5-11 7-9 -> Two times two loose ends k = 4. Six positive numbers p = 6.
a(10) = 15 < (p-1) + (n-p)*k
(End)
CROSSREFS
KEYWORD
nonn,more
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
a(19)-a(20) from Max Alekseyev, Dec 02 2023
a(21) from Max Alekseyev, May 01 2024
STATUS
approved