|
|
COMMENTS
|
For a given set S, we count pairs (s,t) with s in S, t in S, s < t, and s+t equal to a power of 2. (The powers need not be distinct.)
Arises in studying Stan Wagon's Problem of the Week 1321, which asks for the maximum number b(n) if S can be any set of n distinct integers.
The values of a(n) for n <= 100 were found by Rob Pratt using a MILP solver. See links.
b(5) >= 6 from {-3, -1, 3, 5, 11} whereas a(5) = 5 from {-4, -3, -1, 3, 5}.
With [-100,100] bounds, the optimal values for n=11 to 15 are 17, 19, 21, 24, 26.
With [-70,70] bounds, the optimal values for n=16 to 20 are 29, 31, 34, 36, 39.
The following two infinite families of odd consecutive integers appear to yield an n*log n lower bound.
(C1) For n odd, take S = {4-n, 6-n, ..., -3, -1, 1, 3, ..., n, n+2}.
(C2) For n even, take S = {5-n, 7-n, ..., -3, -1, 1, 3, ..., n+1, n+3}.
This is not always optimal. For example, you can do at least 1 better for n = 27 and 28.
n = 27: S = {-23, -21, -19, -17, -15, -13, -11, -9, -7, -5, -3, -1, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29} yields 56;
n = 28: S = {-23, -21, -19, -17, -15, -13, -11, -9, -7, -5, -3, -1, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31} yields 59;
n = 27: S = {-21, -19, -17, -15, -13, -11, -9, -7, -5, -3, -1, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 37} yields 57;
n = 28: S = {-21, -19, -17, -15, -13, -11, -9, -7, -5, -3, -1, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 35, 37} yields 60.
(End)
Construction (C1) can be analyzed as follows. For n = 1, 3, 5, 7, ... the number of powers of 2 are 0, 2, 5, 9, 13, 17, 21, 26, 31, 36, 41, 46, 51, 56, 61, 67, 73, 79, 85, .... (*)
I computed 200 terms of (*), took first differences, and then the RUNS transform, getting essentially A070941, which implies that (*) appears to be A003314((n+1)/2)-3, which is (1/2)*n*log_2(n) - O(n). This is a plausible lower bound on a(n) for all n, and could even be the true order of growth. (End)
If for S = {t_i}_i, all the integers t_i are even, then the set S generates the same number of powers of 2 as {t_i/2}_i. This is because 2a+2b is a power of 2 if and only if a+b is a power of 2.
It appears that a(n) can be achieved using S with only odd integers (this may be true for A352178 as well):
a(2) = 1: { -3, 5 }
a(3) = 3: { -1, 3, 5 }
a(4) = 4: { -3, -1, 3, 5 }
a(5) = 5: { -3, -1, 1, 3, 5 }
a(6) = 7: { -5, -3, -1, 5, 7, 9 }
a(7) = 9: { -5, -3, -1, 3, 5, 7, 9 }
a(8) = 11: { -7, -5, -3, -1, 5, 7, 9, 11 }
a(9) = 13: { -7, -5, -3, -1, 3, 5, 7, 9, 11 }
a(10) = 15: { -9, -5, -3, -1, 3, 5, 7, 9, 11, 13 }
a(11) = 17: { -9, -7, -5, -3, -1, 3, 5, 7, 9, 11, 13 }
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 }
(End)
Construction (C1), along with the variable M from S. Wagon's solution linked below, is not unique to each n. For instance, for n = 128, all of M = {9, 11, 13, 15, 17} result in the same value, a(n) = 399. (However, for n = 4^p, M = 1 + 2^p does seem to be unique.)
If we consider only the central value of M for each n, M appears to be a stepwise function that "prefers" values near powers of 2, or halfway between powers of 2.
Conjecture: Construction (C1), with proper values of M, will compute the majority of maximal values for a(n). The exceptions, like 27, 28 above, seem to cluster near (7/8)*2^k, with a run from n = 54 to n = 59, and another from n = 111 to n = 124 (comparing values from (C1) to those provided by T. Scheuerle in A352178).
These exceptions seem to arise because including 2^k+1 and/or 2^k+3 in the set allows for connections to -1 and -3 (as well as lower negative numbers), where having 2^k-1 or 2^k-3 in the set of values would only connect to lower negative numbers. (End)
|
