1,2

Comments from John Layman, Aug 29 2008 (Start):

I have found a sequence which shows that a(5) of A062714 is less than or equal to 19 and I have also shown that a(5)>18, thus a(5)=19.

It was previously only known that a(5) was 19 or 20.

The following is a sequence of length 19 with terms from 1,2,...,5 that contains as subsequences all of the 120 permutations of 1,2,...,5:

{1,2,3,4,5,1,2,3,4,1,5,2,3,1,4,2,3,5,1}

The proof is shown here:

{1,2,3,4,5,-,-,-,-,-,-,-,-,-,-,-,-,-,-}

{1,2,3,-,5,-,-,-,4,-,-,-,-,-,-,-,-,-,-}

{1,2,-,4,-,-,-,3,-,-,5,-,-,-,-,-,-,-,-}

{1,2,-,4,5,-,-,3,-,-,-,-,-,-,-,-,-,-,-}

{1,2,-,-,5,-,-,3,4,-,-,-,-,-,-,-,-,-,-}

{1,2,-,-,5,-,-,-,4,-,-,-,3,-,-,-,-,-,-}

{1,-,3,-,-,-,2,-,4,-,5,-,-,-,-,-,-,-,-}

{1,-,3,-,-,-,2,-,-,-,5,-,-,-,4,-,-,-,-}

{1,-,3,4,-,-,2,-,-,-,5,-,-,-,-,-,-,-,-}

{1,-,3,4,5,-,2,-,-,-,-,-,-,-,-,-,-,-,-}

{1,-,3,-,5,-,2,-,4,-,-,-,-,-,-,-,-,-,-}

{1,-,3,-,5,-,-,-,4,-,-,2,-,-,-,-,-,-,-}

{1,-,-,4,-,-,2,3,-,-,5,-,-,-,-,-,-,-,-}

{1,-,-,4,-,-,2,-,-,-,5,-,3,-,-,-,-,-,-}

{1,-,-,4,-,-,-,3,-,-,-,2,-,-,-,-,-,5,-}

{1,-,-,4,-,-,-,3,-,-,5,2,-,-,-,-,-,-,-}

{1,-,-,4,5,-,2,3,-,-,-,-,-,-,-,-,-,-,-}

{1,-,-,4,5,-,-,3,-,-,-,2,-,-,-,-,-,-,-}

{1,-,-,-,5,-,2,3,4,-,-,-,-,-,-,-,-,-,-}

{1,-,-,-,5,-,2,-,4,-,-,-,3,-,-,-,-,-,-}

{1,-,-,-,5,-,-,3,-,-,-,2,-,-,4,-,-,-,-}

{1,-,-,-,5,-,-,3,4,-,-,2,-,-,-,-,-,-,-}

{1,-,-,-,5,-,-,-,4,-,-,2,3,-,-,-,-,-,-}

{1,-,-,-,5,-,-,-,4,-,-,-,3,-,-,2,-,-,-}

{-,2,-,-,-,1,-,3,4,-,5,-,-,-,-,-,-,-,-}

{-,2,-,-,-,1,-,3,-,-,5,-,-,-,4,-,-,-,-}

{-,2,-,-,-,1,-,-,4,-,-,-,3,-,-,-,-,5,-}

{-,2,-,-,-,1,-,-,4,-,5,-,3,-,-,-,-,-,-}

{-,2,-,-,-,1,-,-,-,-,5,-,3,-,4,-,-,-,-}

{-,2,-,-,-,1,-,-,-,-,5,-,-,-,4,-,3,-,-}

{-,2,3,-,-,1,-,-,4,-,5,-,-,-,-,-,-,-,-}

{-,2,3,-,-,1,-,-,-,-,5,-,-,-,4,-,-,-,-}

{-,2,3,4,-,1,-,-,-,-,5,-,-,-,-,-,-,-,-}

{-,2,3,4,5,1,-,-,-,-,-,-,-,-,-,-,-,-,-}

{-,2,3,-,5,1,-,-,4,-,-,-,-,-,-,-,-,-,-}

{-,2,3,-,5,-,-,-,4,1,-,-,-,-,-,-,-,-,-}

{-,2,-,4,-,1,-,3,-,-,5,-,-,-,-,-,-,-,-}

{-,2,-,4,-,1,-,-,-,-,5,-,3,-,-,-,-,-,-}

{-,2,-,4,-,-,-,3,-,1,5,-,-,-,-,-,-,-,-}

{-,2,-,4,-,-,-,3,-,-,5,-,-,1,-,-,-,-,-}

{-,2,-,4,5,1,-,3,-,-,-,-,-,-,-,-,-,-,-}

{-,2,-,4,5,-,-,3,-,1,-,-,-,-,-,-,-,-,-}

{-,2,-,-,5,1,-,3,4,-,-,-,-,-,-,-,-,-,-}

{-,2,-,-,5,1,-,-,4,-,-,-,3,-,-,-,-,-,-}

{-,2,-,-,5,-,-,3,-,1,-,-,-,-,4,-,-,-,-}

{-,2,-,-,5,-,-,3,4,1,-,-,-,-,-,-,-,-,-}

{-,2,-,-,5,-,-,-,4,1,-,-,3,-,-,-,-,-,-}

{-,2,-,-,5,-,-,-,4,-,-,-,3,1,-,-,-,-,-}

{-,-,3,-,-,1,2,-,4,-,5,-,-,-,-,-,-,-,-}

{-,-,3,-,-,1,2,-,-,-,5,-,-,-,4,-,-,-,-}

{-,-,3,-,-,1,-,-,4,-,-,2,-,-,-,-,-,5,-}

{-,-,3,-,-,1,-,-,4,-,5,2,-,-,-,-,-,-,-}

{-,-,3,-,-,1,-,-,-,-,5,2,-,-,4,-,-,-,-}

{-,-,3,-,-,1,-,-,-,-,5,-,-,-,4,2,-,-,-}

{-,-,3,-,-,-,2,-,-,1,-,-,-,-,4,-,-,5,-}

{-,-,3,-,-,-,2,-,-,1,5,-,-,-,4,-,-,-,-}

{-,-,3,-,-,-,2,-,4,1,5,-,-,-,-,-,-,-,-}

{-,-,3,-,-,-,2,-,4,-,5,-,-,1,-,-,-,-,-}

{-,-,3,-,-,-,2,-,-,-,5,-,-,1,4,-,-,-,-}

{-,-,3,-,-,-,2,-,-,-,5,-,-,-,4,-,-,-,1}

{-,-,3,4,-,1,2,-,-,-,5,-,-,-,-,-,-,-,-}

{-,-,3,4,-,1,-,-,-,-,5,2,-,-,-,-,-,-,-}

{-,-,3,4,-,-,2,-,-,1,5,-,-,-,-,-,-,-,-}

{-,-,3,4,-,-,2,-,-,-,5,-,-,1,-,-,-,-,-}

{-,-,3,4,5,1,2,-,-,-,-,-,-,-,-,-,-,-,-}

{-,-,3,4,5,-,2,-,-,1,-,-,-,-,-,-,-,-,-}

{-,-,3,-,5,1,2,-,4,-,-,-,-,-,-,-,-,-,-}

{-,-,3,-,5,1,-,-,4,-,-,2,-,-,-,-,-,-,-}

{-,-,3,-,5,-,2,-,-,1,-,-,-,-,4,-,-,-,-}

{-,-,3,-,5,-,2,-,4,1,-,-,-,-,-,-,-,-,-}

{-,-,3,-,5,-,-,-,4,1,-,2,-,-,-,-,-,-,-}

{-,-,3,-,5,-,-,-,4,-,-,2,-,1,-,-,-,-,-}

{-,-,-,4,-,1,2,3,-,-,5,-,-,-,-,-,-,-,-}

{-,-,-,4,-,1,2,-,-,-,5,-,3,-,-,-,-,-,-}

{-,-,-,4,-,1,-,3,-,-,-,2,-,-,-,-,-,5,-}

{-,-,-,4,-,1,-,3,-,-,5,2,-,-,-,-,-,-,-}

{-,-,-,4,-,1,-,-,-,-,5,2,3,-,-,-,-,-,-}

{-,-,-,4,-,1,-,-,-,-,5,-,3,-,-,2,-,-,-}

{-,-,-,4,-,-,2,-,-,1,-,-,3,-,-,-,-,5,-}

{-,-,-,4,-,-,2,-,-,1,5,-,3,-,-,-,-,-,-}

{-,-,-,4,-,-,2,3,-,1,5,-,-,-,-,-,-,-,-}

{-,-,-,4,-,-,2,3,-,-,5,-,-,1,-,-,-,-,-}

{-,-,-,4,-,-,2,-,-,-,5,-,-,1,-,-,3,-,-}

{-,-,-,4,-,-,2,-,-,-,5,-,3,1,-,-,-,-,-}

{-,-,-,4,-,-,-,3,-,1,-,2,-,-,-,-,-,5,-}

{-,-,-,4,-,-,-,3,-,1,5,2,-,-,-,-,-,-,-}

{-,-,-,4,-,-,-,3,-,-,-,2,-,1,-,-,-,5,-}

{-,-,-,4,-,-,-,3,-,-,-,2,-,-,-,-,-,5,1}

{-,-,-,4,-,-,-,3,-,-,5,-,-,1,-,2,-,-,-}

{-,-,-,4,-,-,-,3,-,-,5,2,-,1,-,-,-,-,-}

{-,-,-,4,5,1,2,3,-,-,-,-,-,-,-,-,-,-,-}

{-,-,-,4,5,1,-,3,-,-,-,2,-,-,-,-,-,-,-}

{-,-,-,4,5,-,2,-,-,1,-,-,3,-,-,-,-,-,-}

{-,-,-,4,5,-,2,3,-,1,-,-,-,-,-,-,-,-,-}

{-,-,-,4,5,-,-,3,-,1,-,2,-,-,-,-,-,-,-}

{-,-,-,4,5,-,-,3,-,-,-,2,-,1,-,-,-,-,-}

{-,-,-,-,5,1,2,3,4,-,-,-,-,-,-,-,-,-,-}

{-,-,-,-,5,1,2,-,4,-,-,-,3,-,-,-,-,-,-}

{-,-,-,-,5,1,-,3,-,-,-,2,-,-,4,-,-,-,-}

{-,-,-,-,5,1,-,3,4,-,-,2,-,-,-,-,-,-,-}

{-,-,-,-,5,1,-,-,4,-,-,2,3,-,-,-,-,-,-}

{-,-,-,-,5,1,-,-,4,-,-,-,3,-,-,2,-,-,-}

{-,-,-,-,5,-,2,-,-,1,-,-,3,-,4,-,-,-,-}

{-,-,-,-,5,-,2,-,-,1,-,-,-,-,4,-,3,-,-}

{-,-,-,-,5,-,2,3,-,1,-,-,-,-,4,-,-,-,-}

{-,-,-,-,5,-,2,3,4,1,-,-,-,-,-,-,-,-,-}

{-,-,-,-,5,-,2,-,4,1,-,-,3,-,-,-,-,-,-}

{-,-,-,-,5,-,2,-,4,-,-,-,3,1,-,-,-,-,-}

{-,-,-,-,5,-,-,3,-,1,-,2,-,-,4,-,-,-,-}

{-,-,-,-,5,-,-,3,-,1,-,-,-,-,4,2,-,-,-}

{-,-,-,-,5,-,-,3,-,-,-,2,-,1,4,-,-,-,-}

{-,-,-,-,5,-,-,3,-,-,-,2,-,-,4,-,-,-,1}

{-,-,-,-,5,-,-,3,4,1,-,2,-,-,-,-,-,-,-}

{-,-,-,-,5,-,-,3,4,-,-,2,-,1,-,-,-,-,-}

{-,-,-,-,5,-,-,-,4,1,-,2,3,-,-,-,-,-,-}

{-,-,-,-,5,-,-,-,4,1,-,-,3,-,-,2,-,-,-}

{-,-,-,-,5,-,-,-,4,-,-,2,-,1,-,-,3,-,-}

{-,-,-,-,5,-,-,-,4,-,-,2,3,1,-,-,-,-,-}

{-,-,-,-,5,-,-,-,4,-,-,-,3,1,-,2,-,-,-}

{-,-,-,-,5,-,-,-,4,-,-,-,3,-,-,2,-,-,1}

---End---

Some upper bounds (not necessarily the strongest known) for a(6) through a(19) are 28, 39, 52, 67, 84, 103, 124, 147, 172, 199, 227, 258, 291 and 326. [From Jon E. Schoenfield (jonscho(AT)hiwaay.net), Sep 13 2008]

Contribution from Jon E. Schoenfield (jonscho(AT)hiwaay.net), Jul 27 2009: (Start)

For n > 2, a(n) <= (n-1)^2 + 3, and an easy solution at this upper bound can be obtained by cycling n-3 times through the digits 2 through n and appending the digits 2 and 3 once at the end, inserting a 1 at the beginning and after every n-2 digits thereafter until the last digit is reached, and finally preappending the digits 1 through n. E.g.:

. n=3 (7 digits): 123 1 2 1 3

. n=4 (12 digits): 1234 1 23 1 42 1 3

. n=5 (19 digits): 12345 1 234 1 523 1 452 1 3

. n=6 (28 digits): 123456 1 2345 1 6234 1 5623 1 4562 1 3

. n=7 (39 digits): 1234567 1 23456 1 72345 1 67234 1 56723 1 45672 1 3

Equivalently, for n > 2, the ith digit can be computed as

. i for i <= n

. 1 for i > n and (i-2) mod (n-1) = 0

. int((i-1)*(n-2)/(n-1)) mod (n-1) + 2 otherwise

However, the above approach is not always optimal; e.g., at n = 16, it gives a valid solution in (16-1)^2 + 3 = 228 digits, but the following (using the letters a through g for the numbers 10 through 16) is an example of a 227-digit solution:

. 123456789a bcdefg1234 56789abcde f1g2345678 9abcde1f2g

. 3456789abc d1e2f3g456 789abc1d2e 3f4g56789a b1c2d3e4f5

. g6789a1b2c 3d4e5f6g78 91a2b3c4d5 e6f7g8192a 3b4c5d6e7f

. 18g293a4b5 c6d17ef82g 394a5b16cd 7ef283g491 56abcd7e2f

. 3814569abc dg72e13456 89abcdf

(End)

D. Galvin, The n-Part Trilogy Problem [BROKEN LINK]

1, 2, 3, 1, 2, 3, 1 contains as a subsequence all of 123, ..., 321 and is minimal, so a(3) = 7.

Sequence in context: A109638 A008332 A065390 this_sequence A006317 A077043 A022330

Adjacent sequences: A062711 A062712 A062713 this_sequence A062715 A062716 A062717

nonn,nice,more

N. J. A. Sloane (njas(AT)research.att.com), Jul 14 2001

a(5) = 19 from John Layman (layman(AT)calvin.math.vt.edu), Aug 29 2008