In this question, a certain algorithm was presented:
Start with a deck of $n$ cards.
Take the top card off and set it on the table on top of any cards already there
Move the new top card to the bottom of the deck
Go to step 1 if there are still cards in the deck. When there are no more cards in the deck, one round has passed
Pick up the cards from the table; this is the new deck. If the new deck is in the original order, we are done. Otherwise, repeat from step 1.
As I show in my answer to that question, there are a few peculiarities.
- Powers of two go through few rounds before the cards are in the original order. For example, while the numbers around $64$ take $60+$ rounds before returning to their original state, $64$ takes only $12$ rounds. It appears that every power of two other than two results in $4m$ rounds where $m\in\Bbb N$.
- Prime numbers go through an unusually large number of rounds. For example, while the numbers around $31$ all take less than $100$ rounds, $31$ takes $210$ rounds.
- There are doubtless other interesting properties of this algorithm
What is significant about this algorithm that causes prime numbers and powers of two to have peculiar output?
In response to Victor Engel's comment, here is a proof that the algorithm will always return the deck to the starting case:
- We know that each round is a one-to-one function from a deck ordering to another deck ordering (this should be clear from the way it is set up; it is reversible).
- We know that there are a finite number of deck orderings.
Assume that there is a case where the algorithm does not go back to the starting ordering.
$\implies$ In that case, either there are an infinite number of orderings, or there is a loop somewhere in the sequence.
But we know that there are a finite number of orderings (see 2.).
$\implies$ there is a loop somewhere in the sequence.
$\implies$ either it loops back to the starting ordering or it loops to another ordering in the sequence.
But we know that it doesn't loop back to the starting ordering because that contradicts our assumption that it doesn't.
Thus, the sequence loops to another ordering in the sequence.
This is a contradiction. In order for the sequence to loop to another ordering in the sequence, the function would have to be not one-to-one because two elements in the domain would map to the same element in the range.
$\therefore$ We conclude that repeated applications on the algorithm always leads back to the original case.
As a side note, this same proof works for proving that the repeated application of a certain algorithm on a rubix cubes always leads back to the original rubix cube