cp's OEIS Frontend

The values up to 1169951 were computed by Joseph DeVincentis, Stan Wagon, and Al Zimmermann. The values appear to rise roughly quadratically, so the next one might be near 10^12 and impossible to find. It is known that the sequence is infinite: that is, the cost function is not bounded.

Start with 1. Apply multiplication or addition to any values (not necessarily distinct) already attained to get a finite sequence of integers ending in n. The cost of addition is one unit, but multiplication is free. Then a(n) is the cost of the least expensive path to n.

The problem is folklore. It is not hard to prove that the cost function is unbounded. The values given were produced by Joseph DeVincentis, Stan Wagon, and Al Zimmermann.

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)

a(n) is the largest number of coins obtainable by making repeated moves in this puzzle: Start with empty boxes B(i), i=1..n, and place one coin in B(1). One can iterate moves of two types: (1) remove a coin from a nonempty B(i) (i <= n-1) and place two coins in B(i+1); (2) remove a coin from a nonempty B(i) (i <= n-2) and switch the contents of B(i+1) and B(i+2).

The derivation and proof of the general formula involving a sequence of up-arrows is by Richard Stong, Dan Velleman, and Stan Wagon.

The next term is too large to include (2^65537, it has 19729 digits).

This function is known as m*(2n). For odd n all values of m*(n) are 0.

The set consists of 96, 128, 144, 160, 176, and all multiples of 8 that are greater than or equal to 192. The values 200, 216, 232, 248, 264, 280 are by Golan, Pratt, and Wagon; these are sufficient to give all further entries that are 8 (mod 16). Freiman and Litsyn proved that there is some M so that the list beyond M consists of all multiples of 8.

The linked file gives sets proving that all the given values are 6-powerful.

The sequence consists of the multiples of 16 that are greater than or equal to 192, together with 144. The result is due to S. Golan, R. Pratt, and S. Wagon, who used integer-linear programming to find powerful sets.

The sequence consists of the multiples of 8 that are greater than or equal to 64, together with 48. The result is due to D. Boyd, Berend, and Golan. It had been conjectured that the sequence began with 64, but Boyd discovered the set

{1,2,7,10,11,12,13,14,16,17,21,22,27,28,32,33,35,36,37,38,39,42,47,48},

which shows that 48 is 5-powerful.

A set A of positive integers is called "special above n" iff every element x > n of A divides the product of all elements y < x of A and does not divide any element y > x; an empty product is taken to be 1.

This is a corrected version of A191550, which was based on Friedman (2000), and has terms 1,1,2,5,8,37,26984.

The entries for a(4), a(5), a(6) appear to be wrong. I added the explicit example that shows a(4) >= 9 (and the proof that a(4) <= 9 is easy). I also added the estimate a(5) > 2^2^2^33. An explicit listing proving this is in the Links; that construction is due to Jim Henle. The 2^2^2^33 lower bound for a(5) makes the comment (retained) that a(7) >= 2^2^2^60 seem suspect: it is surely very much larger than this.

a(5) > 2^2^2^33, a(7) > 2^2^2^60, a(11) > A_3(1000), a(13) > A_4(5000), where A_n is the Ackermann function as defined by Harvey Friedman: A_1(n) = 2n, A_2(n) = 2^n, A_{k+1}(n) = A_k A_k ... A_k(1), where there are n A_k's (see also A014221).

The determination of these values is difficult. Early work is due to D. Boyd. The Golan paper cited has references to the earlier work. Work of Buhler, Golan, Pratt, and Wagon (2021) showed that a(8) is 192.