1,3

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.

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.

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

Table of n, a(n) for n=1..10.

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]

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

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.

Stan Wagon, Problem of the Week 1321 (Solution)

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.

Cf. A006855, A347301.

Sequence in context: A247425 A236444 A286809 * A244239 A006855 A301766

Adjacent sequences:  A352175 A352176 A352177 * A352179 A352180 A352181

nonn,more,changed

N. J. A. Sloane, Mar 07 2022

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

approved