cp's OEIS Frontend

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

For this sequence we check the sums for all possible pairs between two distinct members of a set of consecutive odd numbers, we count as valid results of the form 2^m, valid sums are obviously >= 1.

The related sequence A357574 counts the pairs that add to a power of 2.

For sequences of consecutive odd numbers the maximum number of pairs that add to a power of 2 will never be obtained if the sequence starts with numbers greater than 1. Obviously for sequences of all negative numbers, we will not obtain any valid pair.

It appears likely that an optimal solution for A352178 will contain only odd numbers as a mix of odd and even numbers would lead to two unconnected graphs. Let us now assume A352178(k) has an optimal solution in odd numbers only, then there exists a least m such that a(k+m) uses a superset of the same solution pairs used in A352178(k). It would be interesting to know if m has a bound in relation to k.

An optimal set delivering a(n) pairs summing to powers of 2 can be formed by n-A357409(n) first negative odd numbers and A357409(n) first positive odd numbers, that is, by the odd numbers in the interval [-2*(n-A357409(n))+1, 2*A357409(n)-1].

a(n) is in many cases equal to A347301(n) but there are some deviations: a(3) = 2 but A347301(3) = 3, a(29) = 62 but A347301(29) = 61, a(31) = 68 but A347301(32) = 67, a(33) = 74 but A347301(33) = 73, ... . Hence it appears that a(n) may be used as an improved lower bound for A352178(n) in many cases.

Conjecture: a(n+1) - a(n) = k, if n is even then A129868(k-1) < n < A129868(k), if n is odd then A020515(k) <= n < A020515(k+1).