Years ago, I came across a book of magic tricks. Unfortunately, I am not able to find the book. One of the tricks starts with a seemingly shuffled set of cards, ace through king. The magician then takes the top card and transfers it to the bottom of the deck. The next card is layed face up on the table (out). This sequence is repeated until all thirteen cards are layed out, in order, on the table. Another variation is similar. The magician spells out the name of each card, and each time a letter is spoken, he transfers a card from the top to the bottom. The magician then says the name of the expected card as he places the top card face up on the table. For example, the magician would say "A-C-E ace" and then reveals that the ace is on the top of the deck. "T-W-O two", and then he reveals the two from the top. This continues until the last card has been revealed. As with most tricks, the method is simple. The deck simply has to be prepared beforehand for each trick. The book shows a diagram of how the deck should be stacked, but I just did the trick in reverse, and the cards moved to their proper positions.
How does this relate to mathematics and programming? Pull out a deck of cards. Now create a smaller deck using three cards (ace, 2, 3). It will help to leave the cards face up since this is not a magic trick. Just like in the first trick, move the top card under the deck. Move the new top card out onto the table. Repeat this under-out sequence until you run out of cards, but instead of spreading the cards out on the table, create a new deck and stick the new cards on top. You will now find the cards shuffled (3, ace, 2). Repeat this again (2, 3, ace). And again (ace, 2, 3). It took three "shuffles" (how about we call them pseudo-shuffles) to reorganize the deck. Let's try the same thing but with five cards (ace, 2, 3, 4, 5).
Here are the sequences for each pseudo-shuffle:
1: (3, 5, ace, 4, 2)
2: (ace, 2, 3, 4, 5)
Strange. It took three pseudo-shuffles with a deck of three cards, but it took only two for a deck of five cards. We can use the number of cards as the index and then the number of pseudo-shuffles as the output.
Here is a portion of the sequence:
1 1
2 1
3 3
4 3
5 2
6 5
7 7
8 3
9 9
10 21
11 6
12 10
13 13
14 15
15 15
16 15
17 30
18 12
19 42
20 65
Looking at these numbers, I do not see any obvious pattern, other than that the numbers generally increase, and there are several numbers that have the same value as their index.
Calculating these numbers is quite slow because the pseudo-shuffle operation takes a lot of time. I wrote a C++ program to calculate numbers, and after 24 hours of running the program continuously, I only have 311 numbers in the sequence. And I thought primes were hard to find. It would be nice to find an equation to describe the sequence (a series for example), but that is not currently possible because I cannot find any patterns.
I have noticed one property that is always true that may help me speed up the calculation.
1 2 3
3 1 2
2 3 1
1 2 3
Looking at the above sequence of shuffles, it is clear that all the operation is doing is shifting the cards by one. As a result, it makes sense that it takes three shuffles to reorganize the cards. In fact, it does not seem like it would be too complicated to modify the program to predict this. However, if we look at a deck of size four, the pattern changes.
1 2 3 4
1 3 4 2
1 4 2 3
1 2 3 4
The pattern remains the same, except that the 1 stays in the same place the whole time. I am not sure that it is possible to predict the result of a shuffle, but if the sequence is run through once, the 1 could be ignored and the program could predict the result based on the shifting of the three remaining cards. Let's take a look at five cards.
1 2 3 4 5
3 5 1 4 2
1 2 3 4 5
That doesn't look too hard. The 4 remains in the same spot, so we can eliminate that, and we are left with four cards. Looking at the remaining cards, we can see that the 1 and 3 swap and the 2 and 5 swap. Two loops with a length of two. I think the program could be modified to recognize that. It could also be told to ignore the duplicate loop of two as well.
1 2 3 4 5 6
5 1 3 6 4 2
Let's stop there. For a deck of six cards, five pseudo-shuffles should be required. Let's try to figure that out without using brute force.
First, find the loops:
5 moves: 1 → 2 → 6 → 4 → 5 → 1
1 move: 3 → 3
Second, since the deck is only in order if each card has completed its loop, find the least common multiple:
LCM(1, 5) = 5
That seems to have worked. How about a more realistic deck size of 52 cards:
1.
Original:
h.a h.2 h.3 h.4 h.5 h.6 h.7 h.8 h.9 h.10 h.j h.q h.k c.a c.2 c.3 c.4 c.5 c.6 c.7 c.8 c.9 c.10 c.j c.q c.k
d.a d.2 d.3 d.4 d.5 d.6 d.7 d.8 d.9 d.10 d.j d.q d.k s.a s.2 s.3 s.4 s.5 s.6 s.7 s.8 s.9 s.10 s.j s.q s.k
Post Shuffle:
s.2 h.9 c.q s.10 d.7 c.4 h.a s.6 d.j d.3 c.8 h.k h.5 s.q s.8 s.4 d.k d.9 d.5 d.a c.10 c.6 c.2 h.j h.7 h.3
s.k s.j s.9 s.7 s.5 s.3 s.a d.q d.10 d.8 d.6 d.4 d.2 c.k c.j c.9 c.7 c.5 c.3 c.a h.q h.10 h.8 h.6 h.4 h.2
2.
h.a → h.7 → c.q → h.3 → c.k → s.a → d.7 → h.5 → h.k → h.q → s.8 → c.2 → c.10 → c.8 → h.j → c.j
→ s.2 → h.a
h.2 → s.k → d.a → c.7 → s.4 → c.3 → s.6 → h.8 → s.10 → h.4 → s.q → c.a → s.7 → d.4 → d.q → d.8
→ d.10 → d.9 → c.5 → s.5 → d.5 → c.6 → c.9 → s.3 → d.6 → d.j → h.9 → h.2
h.6 → s.j → d.2 → d.k → c.4 → h.6
h.10 → s.9 → d.3 → h.10
3.
17
27
5
3
4.
LCM(17, 27, 5, 3) = 2295
And that is the correct result. I did the work by hand, which took a while, but I am sure that performing the pseudo-shuffle operation 2295 times would have taken much longer. I wonder how long that would actually take? One pseudo-shuffle on a deck of 52 cards took me 1:40, so multiplying that by 2295 results in 2 days, 15 hours, and 45 minutes. I saved a bit of time.
Well, it looks like I solved my problem. I guess I will have to make a new version of the program sometime.
2022-10-08:
I wrote one. It is much faster than the original. A deck size of 312 gives 73,776,261 in a fraction of a second.
Links:
Khan academy version of pseudo-shuffle.cpp. It also has a visulization of the numbers. The series grew too quickly, so the y-axis is logarithmic.
Number sequence on Khan Academy
It is also possible to do more than one "under" before an "out" is done. This leads to a 2D series. X is the deck size, and y is the number of cards to go under. The brightness of the blue is the number of shuffles. Red means that the result took to long to output. Green is like blue, but occurs when the deck size is equal to the number of shuffles. Please be patient while it renders. It took my computer around four minutes. Keep in mind that it is not as impressive as you think it will be.
2D number sequence visualization
Files:
Unformatted number sequence. This pseudo_shuffle program will continue from where it left off if it is given this file.
Number sequence (txt)
Pretty version
Formatted sequence (txt)
Source code
Pseudo-shuffle program (cpp)
Formated sequence generator (c)
Sequence generator optimized using the above method (lisp)