Neil & others, There's something wrong with A000375 & A000376 (or with me). The first says A000375 Topswops (1): shuffle n cards labeled 1..n. If top card is m, reverse order of top m cards. a(n) is max number of steps before top card is 1. 0, 1, 2, 4, 7, 10, 16, 22, 30, 38, 51, 65, 80, 101, 113, 139 The second says A000376 Topswops (2): shuffle n cards labeled 1..n. If top card is m, reverse order of top m cards. a(n) is max number of steps before deck is sorted. 1, 2, 4, 7, 10, 16, 22, 30, 38, 51, 63, 80, 101, 112, 130, 159 In the ordinary way, the deck will not get sorted, since once 1 has come to the top, no more sorting will take place. Somewhat artificially, when 1 comes to the top, you could put it aside and then reduce all the numbers on the other cards by 1 and repeat. It would be good to have some examples of what is going on. With 4 cards there are just two perms which require 4 flips: 3142 --> 4132 --> 2314 --> 3214 --> 1234 2413 --> 4213 --> 3124 --> 2134 --> 1234 In these cases the deck finishes up sorted. Is this always the case if you start with a perm which requires the max number of flips? If so, then the two sequences should be the same. R.
This threw me, too, when I looked at it. Closer examination shows that A000376 is usually equal to A000375, but occasionally smaller. I think this means that A000376 is restricting attention to the cases where the topswop does wind up sorting the cards. I.e., longest time to get 1 to the top for those permutations which wind up sorted when the 1 gets to the top. I agree that a better explanation in A000376 would be useful. Franklin T. Adams-Watters ________________________________________________________________________ Check Out the new free AIM(R) Mail -- 2 GB of storage and industry-leading spam and email virus protection.
Hi Richard and all, [Examples below in my notation, 0 through n-1 instead of 1 through n] Most of the time, the longest chain does end up sorted, as in Richard's example with n = 4 where both of the longest chains end up sorted. 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: ((#(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 a few n (at least not very common among small values!) none of the longest chains end up sorted (and hence A000375 and A000376 are different). n = 12 is an example. I did the exhaustive search 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. --Joshua Zucker
participants (3)
-
franktaw＠netscape.net -
Joshua Zucker -
Richard Guy