Detailed mathematical approach

Problem Summary

For an even deck size \(n\), let \(s(n)\) be the smallest number of perfect riffle shuffles needed to return the deck to its original order. The shuffle used here is the perfect out-shuffle: the deck is cut into two equal halves and the cards are interleaved so that the original top card stays on top.

The task is to compute

$\sum_{s(n)=60} n.$

The search space is infinite if treated naively, so the solution turns the shuffle into a modular permutation problem and then filters a finite divisor set.

Mathematical Approach

Number the positions from \(0\) at the top to \(n-1\) at the bottom. Because \(n\) is even, the deck splits into two halves of size \(n/2\), and a perfect out-shuffle interleaves those halves in a rigid, deterministic way.

Step 1: Model One Shuffle as a Permutation

If a card starts in the top half, at position \(i\) with \(0\le i<n/2\), then after the out-shuffle it moves to position \(2i\).

If a card starts in the bottom half, at position \(i=n/2+j\) with \(0\le j<n/2\), then it moves to position \(2j+1\). Rewriting that in terms of \(i\) gives

$2j+1=2\left(i-\frac{n}{2}\right)+1=2i-(n-1).$

Therefore, for every position except the bottom card, the shuffle is described by

$f(i)\equiv 2i \pmod{n-1}\qquad (0\le i\le n-2),$

while the bottom card stays fixed at position \(n-1\). The top card is also fixed, since \(f(0)=0\).

Step 2: Repeated Shuffles Give a Multiplicative Order

Applying the same permutation \(k\) times multiplies the position index by \(2^k\) modulo \(n-1\):

$f^{(k)}(i)\equiv 2^k i \pmod{n-1}\qquad (0\le i\le n-2).$

The deck returns to its original order exactly when every position is restored, so we need

$2^k i\equiv i\pmod{n-1}$

for all \(i\). Checking \(i=1\) already forces

$2^k\equiv 1\pmod{n-1}.$

Since \(n\) is even, \(n-1\) is odd, so \(\gcd(2,n-1)=1\) and the multiplicative order is defined. Hence

$\boxed{s(n)=\operatorname{ord}_{n-1}(2).}$

Step 3: Restrict Candidates Using \(2^{60}-1\)

Set

$m=n-1.$

If \(s(n)=60\), then \(\operatorname{ord}_m(2)=60\). By the definition of multiplicative order, that implies

$2^{60}\equiv 1\pmod m,$

so \(m\) must divide \(2^{60}-1\):

$m\mid(2^{60}-1).$

Therefore every valid deck size has the form \(n=d+1\), where \(d\) is a divisor of \(2^{60}-1\). This is the key reduction: instead of testing all even \(n\), we only test the divisors of one fixed integer.

Step 4: Enforce Exact Order Rather Than a Smaller Divisor

Dividing \(2^{60}-1\) is only a necessary condition. A divisor \(d\) might satisfy \(2^{60}\equiv 1\pmod d\) but still have order \(1,2,3,4,5,6,10,12,15,20,\) or \(30\).

The prime divisors of \(60\) are \(2\), \(3\), and \(5\). So \(\operatorname{ord}_d(2)=60\) is equivalent to

$2^{60}\equiv 1\pmod d,$

$2^{30}\not\equiv 1\pmod d,\qquad 2^{20}\not\equiv 1\pmod d,\qquad 2^{12}\not\equiv 1\pmod d.$

This prime-divisor test is sufficient because if the true order were a proper divisor \(r\) of \(60\), then \(60/r\) would have at least one prime factor \(p\in\{2,3,5\}\). That would imply \(r\mid 60/p\), and then \(2^{60/p}\equiv 1\pmod d\), contradicting the test.

Step 5: Worked Example with Shuffle Order \(8\)

The implementations include a smaller checkpoint before the order-\(60\) run, so it is useful to see the same method on \(s(n)=8\).

First compute

$2^8-1=255=3\cdot 5\cdot 17.$

Its divisors are

$1,\ 3,\ 5,\ 15,\ 17,\ 51,\ 85,\ 255.$

Now apply the exact-order test. A valid divisor must satisfy \(2^8\equiv 1\pmod d\), but also \(2^4\not\equiv 1\pmod d\) and \(2^2\not\equiv 1\pmod d\).

The divisors that pass are

$17,\ 51,\ 85,\ 255.$

Therefore the corresponding deck sizes are

$18,\ 52,\ 86,\ 256,$

and their sum is

$18+52+86+256=412.$

This is exactly the checkpoint verified by the implementation.

Step 6: Final Summation Formula

Combining the previous steps, the desired total is

$\boxed{\sum_{s(n)=60} n=\sum_{\substack{d\mid(2^{60}-1)\\ \operatorname{ord}_d(2)=60}}(d+1).}$

So the entire problem reduces to three finite tasks: factor \(2^{60}-1\), enumerate its divisors, and keep only those divisors for which \(2\) has exact order \(60\).

How the Code Works

The C++, Python, and Java implementations all follow the same mathematical pipeline. They first factor \(2^{60}-1\) using fast modular arithmetic, a deterministic primality test suitable for 64-bit integers, and Pollard's rho splitting for composite factors. Once the prime factorization is known, they recursively generate every divisor.

For each divisor, the implementation performs fast modular exponentiation to test the order conditions above. Any divisor that satisfies the exact-order filter contributes \(d+1\) to the running sum. Before computing the target case \(60\), the code also checks the smaller order-\(8\) example whose total is \(412\), providing a direct sanity check that the divisor generation and order filter agree.

The three languages differ only in arithmetic details. The C++ version uses native 128-bit multiplication for safe modular products, Python uses arbitrary-precision integers, and Java uses an overflow-safe modular multiplication routine. The underlying algorithm is otherwise identical.

Complexity Analysis

For this specific problem, the target order \(60\) is fixed, so the total running time is effectively constant. More structurally, the expensive step is factoring \(2^{60}-1\); after that, the algorithm enumerates all divisors and performs a constant number of modular exponentiations for each one.

If \(\tau(2^{60}-1)\) denotes the number of divisors of \(2^{60}-1\), then the filtering phase costs \(O(\tau(2^{60}-1)\log 60)\) modular multiplications after factorization, because each candidate is tested with exponents \(60\), \(30\), \(20\), and \(12\). Memory usage is \(O(\tau(2^{60}-1))\) if the full divisor list is stored, and can be viewed as linear in the number of generated divisors.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=622
2. Faro shuffle: Wikipedia — Faro shuffle
3. Multiplicative order: Wikipedia — Multiplicative order
4. Modular arithmetic: Wikipedia — Modular arithmetic
5. Pollard's rho algorithm: Wikipedia — Pollard's rho algorithm