cp's OEIS Frontend

It is assumed that we start with a single letter in the copy buffer.

Alternatively, a(n-1) = maximal value of Product (k_i-1) for any way of writing n = Sum k_i.

1. The description above assumes that the text is deselected after the Copy command is invoked.

2. This sequence is the solution to the equivalent problem formulated as {insert, "Select All+ Copy" macro (without deselection), Paste}.

3. This sequence is a "paradigm-shift" sequence with procedure length p =1 (in the sense of A193455).

4. The optimal number of pastes per copy, as measured by the geometric growth rate (p+z root of z), is z = 4. [noninteger maximum between 3 and 4]

5. The function a(n) = maximum value of the product of the terms k_i, where Sum (k_i) = n+1-i_max.

6. All solutions will be of the form a(n) = m^b * (m+1)^d.

Similar to A038373 but with octant grid instead of quadrant. An octant grid is either half of a quadrant grid when divided on the diagonal and including the diagonal grid squares. Its shape is that of a right triangle with a stair step edge on the hypotenuse. Coordinates of squares satisfy x>=0 and y>=0 and x>=y.

Guttmann-Torrie series coefficients c_n^2 for square lattice, with wedge angle Pi/4. - N. J. A. Sloane, Jul 06 2015

Draw n line segments on a piece of paper in such a way that if we make cuts along those lines, only triangular pieces are formed (apart from the "outside" region). Sequence gives maximal number of triangles that can be obtained.

Inspection of Loy's web page shows that these are known to be optimal only for n up to about 7.

Loy gives the following lower bounds for n = 1, 2, 3, ...: 0, 0, 1, 2, 4, 7, 10, 14, 18, 22, 27, 32, 38, 44, 50, 54, 60, 72, 76, 84, 92, 110, 114, 122, 130, 156, 160, 210

See also A000375, which is the main entry for this problem.

Comments from Joshua Zucker, Jan 24 2007: (Start)

For some n, there are some longest chains which end up sorted and some which don't, like n = 6, with the following four chains that end sorted and one that does not:

The examples below use 0 through n-1 instead of 1 through n.

((#(4 5 3 0 2 1) #(2 0 3 5 4 1) #(3 0 2 5 4 1) #(5 2 0 3 4 1) #(1 4 3 0 2 5) #(4 1 3 0 2 5) #(2 0 3 1 4 5) #(3 0 2 1 4 5) #(1 2 0 3 4 5) #(2 1 0 3 4 5) #(0 1 2 3 4 5))

(#(3 4 5 1 0 2) #(1 5 4 3 0 2) #(5 1 4 3 0 2) #(2 0 3 4 1 5) #(3 0 2 4 1 5) #(4 2 0 3 1 5) #(1 3 0 2 4 5) #(3 1 0 2 4 5) #(2 0 1 3 4 5) #(1 0 2 3 4 5) #(0 1 2 3 4 5))

(#(3 0 4 1 5 2) #(1 4 0 3 5 2) #(4 1 0 3 5 2) #(5 3 0 1 4 2) #(2 4 1 0 3 5) #(1 4 2 0 3 5) #(4 1 2 0 3 5) #(3 0 2 1 4 5) #(1 2 0 3 4 5) #(2 1 0 3 4 5) #(0 1 2 3 4 5))

(#(2 5 4 0 3 1) #(4 5 2 0 3 1) #(3 0 2 5 4 1) #(5 2 0 3 4 1) #(1 4 3 0 2 5) #(4 1 3 0 2 5) #(2 0 3 1 4 5) #(3 0 2 1 4 5) #(1 2 0 3 4 5) #(2 1 0 3 4 5) #(0 1 2 3 4 5)))

(#(3 0 5 4 1 2) #(4 5 0 3 1 2) #(1 3 0 5 4 2) #(3 1 0 5 4 2) #(5 0 1 3 4 2) #(2 4 3 1 0 5) #(3 4 2 1 0 5) #(1 2 4 3 0 5) #(2 1 4 3 0 5) #(4 1 2 3 0 5) #(0 3 2 1 4 5))

And for some n, e.g., n=12, none of the longest chains end up sorted (and hence A000375 and A000376 are different). I did an exhaustive search with n = 12 working backwards from sorted and found 63 as the longest chain beginning with one of these four:

#(9 10 6 0 2 7 1 8 11 5 3 4)

#(9 10 6 0 1 2 7 8 11 5 3 4)

#(7 8 11 5 0 6 10 9 2 1 3 4)

#(5 0 1 7 10 3 11 8 9 6 2 4)

But 65 is attainable if you don't assume it ends up sorted. (End)

Comment from Quan T. Nguyen, William Fahle (tuongquan.nguyen(AT)utdallas.edu), Oct 21 2010: (Start)

(6 14 9 2 15 8 1 3 4 12 18 5 10 13 16 17 11 7) is the only permutation of length 18 that takes 191 steps (also called longest-winded permutation) of "topswopping moves" before it goes to the identity permutation (i.e., in sorted order).

For n=17, (2 10 15 11 7 14 5 16 6 4 17 13 1 3 8 9 12) is the only longest-winded permutation (or order of cards) that takes 159 steps of "topswopping moves" before it terminates in sorted order, i.e., (1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17). (End)

Comment from Moritz Franckenstein, Apr 16 2011: (Start)

n=18 -> 191

6 14 9 2 15 8 1 3 4 12 18 5 10 13 16 17 11 7

n=19 -> 207

2 3 7 8 4 19 10 15 17 6 1 11 5 18 12 9 13 14 16

3 7 2 8 4 19 10 15 17 6 1 11 5 18 12 9 13 14 16

n=20 -> 231

5 20 6 3 2 15 10 1 16 9 18 14 19 7 12 17 8 11 13 4

3 20 5 6 2 15 10 1 16 9 18 14 19 7 12 17 8 11 13 4

5 20 2 6 3 15 10 1 16 9 18 14 19 7 12 17 8 11 13 4 (End)

Knuth's algorithm can be extended by considering unsorted large unmovable segments: xxx645, e.g. will never move 6, 4, or 5. - Quan T. Nguyen, William Fahle (waf013000(AT)utdallas.edu), Oct 12 2010

For n=17, there are two longest-winded permutations (or orders of cards) that take 159 steps of "topswopping moves" before the top card is 1. (8 15 17 13 9 4 6 3 2 12 16 14 11 5 10 1 7) terminates at (1 6 2 4 9 3 7 8 5 10 11 12 13 14 15 16 17), and (2 10 15 11 7 14 5 16 6 4 17 13 1 3 8 9 12) terminates in sorted order, i.e., (1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17). - Quan T. Nguyen, William Fahle (tuongquan.nguyen(AT)utdallas.edu), Oct 21 2010

Lower bounds for the next terms are a(18)>=191, a(19)>=221, a(20)>=249, a(21)>=282, a(22)>=335, a(23)>=382. - Hugo Pfoertner, May 21 2011; updated Oct 08 2016