login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

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

%I #216 Dec 25 2024 04:27:33

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

%N 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.

%C 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.

%C 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

%C The following remarkable theorem is due to M. S. Smith (email of Mar 06 2022).

%C Theorem: G contains no 4-cycles.

%C 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.

%C Since the t_i are distinct, b_1 != b_4, b_2 != b_1, b_3 != b_2, and b_4 != b_3.

%C We also have

%C (*) b_1+b_3 = b_2+b_4 = t_1+t_2+t_3+t_4.

%C 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

%C Let c(n) = A006855(n) denote the maximum number of edges in a graph on n nodes containing no 4-cycle.

%C Corollary: a(n) <= c(n).

%C 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).

%C Another corollary is that a(n) is bounded asymptotically by (n/4)*(sqrt(4n-3)+1) (see A006855).

%C The theorem is remarkable, since before the only known values of a(n) were the trivial values for n <= 3.

%C In summary, we have a(n) >= A347301(n) for n >= 6, and

%C a(n) <= A006855(n) for all n.

%C From _Thomas Scheuerle_, Sep 23 2022: (Start)

%C 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).

%C From this we can conclude that all cycles in the graph G must contain at least one negative number.

%C Conjecture A: The count of negative numbers in an optimal solution is either equal to the count of positive numbers or one less.

%C This leads to Conjecture B: a(n) <= floor((n+1)*3/2). (End)

%C _Max Alekseyev_ points out that both conjectures are wrong.

%C (A) Counterexamples are given by examples from A347301:

%C a(12) = 19: { -9, -7, -5, -3, -1, 1, 3, 5, 7, 9, 11, 13 }

%C a(13) = 21: { -11, -7, -5, -3, -1, 1, 3, 5, 7, 9, 11, 13, 15 }

%C (B) For n=14, this bound is 22, but it is smaller than a(14) = 24. _N. J. A. Sloane_, Sep 25 2022

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

%H Max Alekseyev, <a href="https://arxiv.org/abs/2303.02872">On computing sets of integers with maximum number of pairs summing to powers of 2</a>, arXiv:2303.02872 [math.CO], 2023.

%H Matthew Bolan, <a href="/A352178/a352178.pdf">Stan Wagon 1321 Solution</a>, Sep 22, 2022 [Shows that a(10) = 15]

%H Alex Bradley, <a href="/A352178/a352178_1.pdf">Pairwise Powers of 2 Problem</a>, Sep 22 2022 [Short proof that there do not exist four distinct numbers all of whose pairwise sums are powers of 2]

%H C. R. J. Clapham, A. Flockhart, and J. Sheehan, <a href="https://doi.org/10.1002/jgt.3190130107">Graphs without four-cycles</a>, J. Graph Theory 13 (1) (1989) 29-47

%H Charlotte Darroch, <a href="/A352178/a352178_7.txt">Comments on Stan Wagon's Powers of 2 Problem</a>, Sep 22 2022

%H Christof Haase, <a href="/A352178/a352178_2.txt">Decidability of the Powers of Two Problem</a>, Sep 22 2022

%H Péter Hajnal, <a href="https://doi.org/10.3390/a17020055">Binary Numeration System with Alternating Signed Digits and Its Graph Theoretical Relationship</a>, Algorithms (2024) Vol. 17, Art. No. 55. See p. 9.

%H Brady Haran and N. J. A. Sloane, <a href="https://youtu.be/IPoh5C9CcI8">Problems with Powers of Two</a>, Youtube Numberphile Video, Sep 21 2022

%H Brady Haran and N. J. A. Sloane, <a href="https://www.numberphile.com/stop-press">STOP PRESS: Postscript to Problems with Powers of Two</a>, Sep 21 2022

%H Noam Kimmel, <a href="/A352178/a352178_4.pdf">Asymptotics (upper and lower bounds) for a(n)</a>

%H Firas Melaih, <a href="/A352178/a352178_3.pdf">On The OEIS Sequence A352178</a> [Shows a(10) = 15, a(12) < 21, and some impossibility results on the graphs]

%H Firas Melaih, <a href="/A352178/a352178_3.txt">a(11) = 17</a> [Proves a(11) = 17 from an uploaded paper]

%H Rob Pratt, <a href="/A352178/a352178_5.txt">The best lower bounds known for 1 <= n <= 100 as of Sep 25 2022</a> [Gives n, best lower bound known, and an example of an n-set achieving that bound]

%H Thomas Scheuerle, <a href="/A352178/a352178_6.txt">The best lower bounds known for 1 <= n <= 351 as of Sep 28 2022</a> [Gives n, best lower bound known, and an example of an n-set achieving that bound]

%H István Selek, <a href="/A352178/a352178_2.pdf">A possible proof of the Powers of Two problem</a>, Sep 22 2022 [A solution for the case n = 4 using linear algebra]

%H N. J. A. Sloane, <a href="https://vimeo.com/704569041/4ffa06b95e">The On-Line Encyclopedia of Integer Sequences: An illustrated guide with many unsolved problems</a>, Guest Lecture given in Doron Zeilberger's Experimental Mathematics Math640 Class, Rutgers University, Spring Semester, Apr 28 2022: <a href="https://sites.math.rutgers.edu/~zeilberg/EM22/C27.pdf">Slides</a>; <a href="http://NeilSloane.com/doc/Math640.04.2022.pdf">Slides (an alternative source)</a>.

%H Stan Wagon, <a href="/A347301/a347301_1.pdf">Problem of the Week 1321: Powers of Two</a>, Apr 16 2021.

%F 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

%F For n > 2, a(n) <= floor(a(n-1) * n / (n-2)). - _Max Alekseyev_, Jan 23 2023

%e a(3) = 3 from S = {-1, 3, 5}.

%e a(4) >= 4 from S = {-3, -1, 3, 5}, a(4) <= A006855(4) = 4, so a(4) = 4.

%e a(5) >= 6 from S = {-3, -1, 3, 5, 11}, a(5) <= A006855(5) = 6, so a(5) = 6.

%e From _Thomas Scheuerle_, Sep 26 2022: (Start)

%e a(13): { -11, -7, -5, -3, -1, 1, 3, 5, 7, 9, 11, 13, 15 }

%e 13

%e |

%e 9-7-1-3-5-11

%e |

%e 15 -> Four loose ends k = 4. Eight positive numbers p = 8.

%e a(13) = 21 < (p-1) + (n-p)*k

%e a(10): {-9, -5, -3, -1, 3, 5, 7, 9, 11, 13}

%e 13-3-5-11 7-9 -> Two times two loose ends k = 4. Six positive numbers p = 6.

%e a(10) = 15 < (p-1) + (n-p)*k

%e (End)

%Y Cf. A006855, A347301, A357409.

%K nonn,more

%O 1,3

%A _N. J. A. Sloane_, Mar 07 2022

%E a(10) from _Matthew Bolan_, Sep 22 2022 - see link. - _N. J. A. Sloane_, Sep 22 2022

%E Edited by _N. J. A. Sloane_, Sep 22 2022

%E a(12)-a(18) from _Max Alekseyev_, Sep 25 2022, Sep 29 2022

%E a(19)-a(20) from _Max Alekseyev_, Dec 02 2023

%E a(21) from _Max Alekseyev_, May 01 2024