login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 59th year, we have over 358,000 sequences, and we’ve crossed 10,300 citations (which often say “discovered thanks to the OEIS”).

Other ways to Give
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 (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

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

REFERENCES

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

LINKS

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

Max Alekseyev, A New Approach to Finding Upper Bounds for the "Powers of Two" Problem, Preliminary Note, Sep 25 2022

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

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

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.

Stan Wagon, Problem of the Week 1321 (Solution)

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

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.

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)

CROSSREFS

Cf. A006855, A347301, A357409.

Sequence in context: A247425 A236444 A286809 * A244239 A006855 A301766

Adjacent sequences: A352175 A352176 A352177 * A352179 A352180 A352181

KEYWORD

nonn,more,changed

AUTHOR

N. J. A. Sloane, Mar 07 2022

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 2 20:59 EST 2022. Contains 358510 sequences. (Running on oeis4.)