|
|
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, 36, 39
(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 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
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)
(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
|
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]
Firas Melaih, a(11) = 17 [Proves a(11) = 17 from an uploaded paper]
|
|
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.
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,changed
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|