(Copied verbatim from: A Project Euler thread I made in December of 2009.)
Lets say you have cards numbered from 1 to 5. You want to organize them into a stack such that you can move 1 card from the top to the bottom and turn over the next card to reveal a 1. Put it off to the side and move two cards from the top of the stack (one at a time) to the bottom. The next card is revealed and is a 2, which is then set aside. Repeat until you have 1 card left which will be 5. In order to achieve this, the cards must be ordered as such: [3, 1, 4, 5, 2] But what if I want to order 10 cards this way? Well...the required pre-order is then [9, 1, 8, 5, 2, 4, 7, 6, 3, 10]. Then I started wondering if there were any cases where the card's number was its actual position in the stack before the dealing. What a surprise! 7 ([5, 1, 3, 4, 2, 6, 7]) has 4! It turns out that 7 is the first number where the sequence generated thus has more than 2 self-collisions, as I call them. The first one to have 5 is 543, the first one to have 6 is 3117, and the first one to have 7 is 3226. I have not found one for 8 yet, but there may be a 9 before the first 8. If anyone can find an analytical solution to the following questions...I will be greatly amazed... :P
What is the first one to have 8 self-collisions? What about 9? What about 10?
P.S. The sequence for 5 can be generated thus (easily generalized):
xxxxx x1xxx x1xx2 31xx2 314x2 31452