Shuffle again and again and again...

An interesting question is how this applies to a deck of $n$ cards.

Any permutation $\sigma \in S_n$ can be written uniquely (up to commutative swapping of the factors) as the product of disjoint cycles. The sum of lengths of these cycles is obviously $n$ or less. The index $|\sigma|$ (i.e. the smallest power $k > 0$ for which $\sigma^k = \text{id}$ ) is equal to the least common multiple of the cycle lengths: $\sigma = \prod_{i = 1}^m C_i\ \ \ \ \ \therefore\ \ \ \ \ \ |\sigma| = \text{lcm}(|C_1|, \dots, |C_m|).$ This number $k$ is the smallest number of shuffles of type $\sigma$ after which the deck returns to its original state.

To answer the question, then, we need to find the maximum of these least common multiples $k$ : $\max_{\sigma \in S_n} |\sigma|.$ To find this maximum, we don't need to consider all $\sigma$ ; it is sufficient to work with the cycle structure, i.e. we consider all unordered lists (bags) $\langle c_1, c_2, \dots, c_m \rangle \ \ \ \ \text{such that}\ \sum c_i \leq n.$ Now suppose that $c_j = a\cdot b$ for coprime numbers $a,b > 1$ . Then it pays to replace $c_j$ by two values $a$ and $b$ : after all, this does not change the lcm but it does reduce the sum $\sum c_i$ , allowing for the addition of more cycles. Therefore we can choose all $c_i$ to be powers of prime numbers. Obviously, there is no advantage of having two powers of the same prime number; removing the smaller of the two does not change the lcm.

Thus we need only consider set $\langle p_1^{e_1}, \dots, p_m^{e_m} \rangle$ consisting of powers of distinct primes, whose sum is less than $n$ .

For $n = 8$ , we consider sets chosen from one or more of the sets $\{ 2,4,8\}$ ; $\{3\}$ ; and $\{5\}$ : $8 = 8;\ \ \ 4\cdot 3 = 12;\ \ \ 2\cdot 5 = 10;\ \ \ 3\cdot 5 = \boxed{15}.$ This maximum number of 15 shuffles is obtained by any permutation of the form $\sigma = (a_1\ a_2\ a_3)\ (b_1\ b_2\ b_3\ b_4\ b_5)$ , where all $a_i$ and $b_i$ are distinct.

For $n = 52$ , the situation is more interesting. The cycle lengths of interest are $\{2,4,8,16,32\};\ \{3,9,27\};\ \{5,25\};\ \{7,49\};\ \{11\};\ \{13\};\ \{17\};\ \{19\};\ \{23\};\ \{29\};\ \{31\};\ \{37\};\ \{41\};\ \{43\};\ \{47\}.$ We can have no more than one of the last six primes. Exploring the possibilities (e.g. using computer code) we find the cycle structure $4,5,7,9,11,13.$ Thus, for a complete set of cards the maximum number of shuffles is $180\:180$ , using a permutation of the form $(a_1\ a_2\ a_3\ a_4)\ (b_1\ \dots\ b_5)\ (c_1\ \dots\ c_7)\ (d_1\ \dots\ d_9)\ (e_1\ \dots\ e_{11})\ (f_1\ \dots\ f_{13})\ (o_1)\ (o_2)\ (o_3),$ where the 52 indices mentioned are all distinct. (The three cards $o_1, o_2, o_3$ remain in place in each shuffle.)

Consider this shuffling:

$12345678 \to 23451786$

This would take 15 shuffles to return to the first position, since you have two "loops" of 3 and 5 which are coprime. Each loop returns to their original position after every 3 and 5 turns. So, the total number of shuffles needed would be $5 \cdot 3 = 15$

Now, to show that this is the worst case... Well, 3 and 5 are the coprime numbers that add up to 8, that yield the largest product, therefore I believe this is the worst you can do.

We want to know the largest order of an element of the permutation group $S_8$ . To do this, we must know the various cycle types of elements of $S_8$ . These are $1,2,3,4,5,6,7,8,2\times2,2\times3,2\times4,2\times5,2\times6,3\times3,3\times4,3\times5,4\times4,2\times2\times2,2\times2\times3,2\times2\times4,2\times3\times3,2\times2\times2\times2$ and these cycle types have orders $1,2,3,4,5,6,7,8,2,6,4,10,6,3,12,15,4,2,6,4,6,2$ respectively. Thus the elements of $S_8$ with the largest order are the $3\times5$ cycles, and hence the largest possible order is $\boxed{15}$ .

A card will always follow a cycle of positions in the deck. For example, if only card $1$ is moved to position $3$ , the cycle would be $1$ , $3$ , $2$ , and then back to $1$ .

All cards within a cycle will take the same number of shuffles before returning to their starting positions. In the example above, cards $1$ , $2$ and $3$ will return to their starting positions after $3$ shuffles.

The number of shuffles it takes to return the entire deck to its starting position is the lowest common multiple of all cycles. For example, in a larger deck with cycles of $4$ , $6$ and $10$ , the number of shuffles would be $60$ .

The set of numbers which sum to $8$ , and whose $lcm$ is highest, is $3$ and $5$ , resulting in a shuffle count of $\boxed{15}$ .

I think the problem is not well expressed.

It is written: "(...) what is the largest number of identical shufflings you need (...)"

With 15 shuffles you are guaranteed to return to the original order (somewhere along the way). With 16 shuffles you also are guaranteed, because you are with 15.

To me, 15 is a lower limit, not upper. So the problem should be: "(...) what is the smallest number of identical shufflings you need (...)"

Edit: corrected! My first contribute into this community ^_^

This problem gets very easy if you think this way. You have a bijection between the numbers 1 to 8. Suppose you have no other bijection inside this one (i.e. if 1, 2 and 3 form a loop, then you have a bijection between these numbers), then after 8 turns you will get the same deck again. However you can have 2 or more bijections. Suppose you have 2 loops, one with 5 numbers and the other with 3. You will get the same deck after 15 shuffles. The number of shuffles that will get you the same deck is the lcm of the loop sizes.

With 1 loop you have 8 shuffles maximum

With 2 loops you have lcm(3,5) = 15

With 3 loops you have lcm(3,4,1)=12

With 4 loops you have lcm(3,2,2)=6

With 5 o more the loops will have length of 4 or less, since 16 is impossible the lcm is not bigger than 15

So the answer is 15.

If one were to apply this as some sort of trick, then one alternative question is the smallest number required for any perfect shuffle to return to the starting position. In other words, the cards are shuffled n times and then revealed to be in their original order.

I believe this would require 840 shuffles.

Landau's function g(8)=15 is the Answer.

Here, g(n) is the largest least common multiple (lcm) of any partition of n ( for n=8, 5+3=8, 5×3=15) , or the maximum number of times a permutation of n elements can be recursively applied to itself before it returns to its starting sequence.

Read more about Landau's function here:

https://en.m.wikipedia.org/wiki/Landau%27s_function

Check integer sequence A000793 in the OEIS named after Edmund Landau for g(n).

Answer=15