Project Euler Problem 622

Project Euler Problem 622

Solution

Answer: 3010983666182123972

Let the deck size be $n$ (even), and index positions from $0$ to $n-1$, where $0$ is the top card.

The shuffle described is the perfect out-shuffle (top and bottom cards remain fixed).

1. Mathematical analysis

Step 1: Describe the permutation

Split the deck into two halves:

• left hand: positions $0,1,\dots,\frac n2-1$
• right hand: positions $\frac n2,\dots,n-1$

The interleaving gives:

$$0,\frac n2,1,\frac n2+1,2,\frac n2+2,\dots$$

A standard fact for the out-shuffle is:

• the bottom card stays fixed,
• every other position transforms by

$$i \mapsto 2i \pmod{n-1}$$

for $0 \le i < n-1$.

Thus after $k$ shuffles,

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

The deck returns to the original configuration exactly when

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

Hence:

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

the multiplicative order of $2$ modulo $n-1$.

This matches the example:

$$n=52 \implies n-1=51.$$

Since

$$2^8 \equiv 1 \pmod{51},$$

and no smaller exponent works,

$$s(52)=8.$$

---

Step 2: Convert the problem

We want:

$$s(n)=60.$$

Let

$$m=n-1.$$

Then:

$$\operatorname{ord}_m(2)=60.$$

By definition of multiplicative order:

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

but $m$ must not divide $2^d-1$ for any proper divisor $d\mid 60$.

So the algorithm is:

1. Compute

$$M=2^{60}-1.$$

1. Enumerate every divisor $m$ of $M$.
2. Keep those with

$$\operatorname{ord}_m(2)=60.$$

1. Sum

$$n=m+1.$$

---

2. Python implementation

from sympy import divisors, n_order

def solve(target_order=60):
    # All valid m = n - 1 must divide 2^target_order - 1
    M = 2**target_order - 1

    total = 0

    # Check every divisor m of M
    for m in divisors(M):
        if m <= 1:
            continue

        # Multiplicative order of 2 modulo m
        if n_order(2, m) == target_order:
            total += (m + 1)

    return total

# Verify the example
example = solve(8)
print("s(n)=8 sum:", example)   # should be 412

# Final answer
answer = solve(60)
print(answer)

---

3. Code walkthrough

M = 2**target_order - 1

If $s(n)=k$, then:

$$n-1 \mid 2^k-1.$$

So every candidate must divide $2^k-1$.

For $k=60$:

$$M = 2^{60}-1.$$

---

divisors(M)

Enumerates every positive divisor of $M$.

We test each divisor as a possible value of:

$$m=n-1.$$

---

n_order(2, m)

Computes the multiplicative order:

$$\min{t>0 : 2^t \equiv 1 \pmod m}.$$

We keep only those with exact order $60$.

---

total += (m + 1)

Since:

$$m=n-1,$$

recover:

$$n=m+1.$$

---

Example check

For $k=8$, the program finds:

$$n = 18,\ 52,\ 86,\ 256$$

whose sum is:

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

matching the problem statement exactly.

---

4. Final verification

• Since $n-1$ must divide $2^{60}-1$, all solutions are finite.
• The example $k=8$ reproduces the given total $412$, validating the method.
• Exhaustively checking all divisors of $2^{60}-1$ guarantees completeness.

Answer: 3010983666182123972