cp's OEIS Frontend

The problem is to maximize Sum_{i=1..n} i p(i) - Max_{j=1..n} j p(j) where p is a permutation of {1,...,n}.

The terms up to n = 100 were computed via integer linear programming.

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.

Of course b(n) >= a(n). For b(n) see A352178. - N. J. A. Sloane, Mar 07 2022

b(5) >= 6 from {-3, -1, 3, 5, 11} whereas a(5) = 5 from {-4, -3, -1, 3, 5}.

Comments from Rob Pratt: (Start)

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)

Comments from N. J. A. Sloane, Feb 21 2022: (Start)

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)

From Chai Wah Wu, Sep 21 2022: (Start)

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)

Comments from Eric Snyder, Oct 22 2022: (Start)

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)

Exceptionally, DATA section give first 100 terms.

One might have expected that the GP would be required to have an integer ratio, but in fact we allow rational ratios. The GPs can be assumed to be increasing.

"Pairwise products" includes the squares of the digits.

Suggested by Ricardo Palomino, who mentioned the trivial numbers A007088.

If any digit other than 0 or 1 appears, then all ten digits appear, as can easily be checked for each digit. For example, if 2 appears then 2*2 = 4 appears, which implies that 2*4 = 8 appears and {1,6} (from 4*4 = 16) appear, which implies that 3 appears (from 4*8 = 32), which implies that 3*3 = 9 appears, which implies that {2,7} appear (from 3*9), which implies that {5,6} appear (from 7*8), which implies that 0 appears (from 2*5 = 10).

There are 37 distinct products (10 with one digit and 27 with two digits) of pairs of digits from {0,1,...,9}.

Rob Pratt solved an asymmetric traveling salesman problem (ATSP) on 38 nodes to find the minimum number of digits, which turns out to be 37, and then solved a sequence of integer linear programming problems (minimizing one digit at a time from left to right) to find the minimum such 37-digit number.

This sequence was mentioned by R. K. Guy in the first comment in A004396.

It is conjectured that T(n,k) <= n+k-1.

The array is symmetric: T(n,k) = T(k,n).

The main diagonal T(n,n) appears to equal 2n-2 for n>1. (This diagonal is presently A271907, but if it really is 2n-2 that entry may be recycled.)

The triangle must have nonzero area (three collinear points don't count as a triangle).

Solutions that differ by a rotation and/or reflection are counted as different. - N. J. A. Sloane, Nov 20 2015

The paper by Boyland et al. gives a(13) = 14454384 and a(15) = 1401615406696. - Eric M. Schmidt, Aug 30 2017