

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 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
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)
(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) <= (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
For n > 2, a(n) <= floor(a(n1) * n / (n2)).  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

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



KEYWORD

nonn,more


AUTHOR



EXTENSIONS



STATUS

approved



