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

0, 1, 3, 4, 6, 7, 9, 11, 13, 15, 17, 19, 21, 24, 26, 29, 31, 34, 36, 39, 41

Offset: 1

Author

N. J. A. Sloane, Mar 07 2022

Keywords

• nonn
• more

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

Examples

			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)
		

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.

Crossrefs

Cf. A006855, A347301, A357409.

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

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