Project Euler Problem 62

Solution

Answer: 127035954683

We seek the smallest cube for which exactly five permutations of its digits are also cubes.

The key observation is that digit permutations preserve the multiset of digits. So instead of comparing cubes pairwise, we can classify cubes by a canonical “digit signature”.

A natural signature is:

• Sort the digits of the cube.
• Any two numbers that are permutations of each other will share the same sorted-digit string.

For example:

$$345^3 = 41063625$$

Sorting digits:

$$41063625 \to 01234566$$

Now:

$$384^3 = 56623104 \to 01234566$$

$$405^3 = 66430125 \to 01234566$$

So all three cubes belong to the same signature class.

---

Mathematical Analysis

Suppose:

$$n^3 = c$$

Define the signature:

$$\sigma(c) = \text{sorted digits of } c$$

Then:

$$\sigma(a^3)=\sigma(b^3)$$

if and only if $a^3$ and $b^3$ are permutations of each other.

Therefore, the problem reduces to:

Find the smallest cube whose signature class contains exactly five cubes.

---

Efficient Strategy

Brute force comparison between all cubes would be expensive.

Instead:

1. Generate cubes sequentially.
2. Compute each cube’s digit signature.
3. Store cubes grouped by signature in a dictionary.
4. When a signature accumulates five cubes, record it.
5. Ensure the class has exactly five cubes (not more).

A subtle issue:

• If we stop immediately upon reaching five cubes, a later cube might create a sixth permutation.

To avoid this, process cubes grouped by digit length.

Why?

• Any permutation has the same number of digits.
• Once we move to cubes with more digits, no more cubes can belong to the previous digit-length classes.

Thus:

• Process all cubes with $d$ digits.
• After finishing that digit length, inspect the groups.
• Any group with exactly five cubes is finalized.

---

Python Implementation

from collections import defaultdict

# Dictionary:
# key   -> sorted digit signature
# value -> list of cubes having that signature
groups = defaultdict(list)

n = 1
current_length = 1

while True:
    cube = n ** 3

    # Number of digits in the cube
    length = len(str(cube))

    # When digit length changes, previous groups are complete
    if length > current_length:

        # Check all groups from the previous digit length
        candidates = [
            cubes for cubes in groups.values()
            if len(cubes) == 5
        ]

        # If any valid group exists, return the smallest cube
        if candidates:
            answer = min(min(cubes) for cubes in candidates)
            print(answer)
            break

        # Reset for the next digit length
        groups.clear()
        current_length = length

    # Create canonical digit signature
    signature = ''.join(sorted(str(cube)))

    # Store cube in its group
    groups[signature].append(cube)

    n += 1

---

Code Walkthrough

Imports

from collections import defaultdict

defaultdict(list) automatically creates an empty list for unseen signatures.

---

Main storage

groups = defaultdict(list)

Example structure:

{
    '01234566': [41063625, 56623104, 66430125]
}

---

Iterating through cubes

cube = n ** 3

Generates:

$$1^3, 2^3, 3^3, \dots$$

---

Digit length detection

length = len(str(cube))

Permutations must have identical digit counts.

When digit length changes, we know no future cube can belong to earlier groups.

---

Signature creation

signature = ''.join(sorted(str(cube)))

Example:

41063625 -> "01234566"

All permutations map to the same key.

---

Group accumulation

groups[signature].append(cube)

We collect all cubes sharing the same digit multiset.

---

Detecting exactly five permutations

candidates = [
    cubes for cubes in groups.values()
    if len(cubes) == 5
]

We search for groups containing exactly five cubes.

---

Verifying the Example

The problem states:

$$345^3 = 41063625$$

$$384^3 = 56623104$$

$$405^3 = 66430125$$

All share the same signature:

"01234566"

and there are exactly three such cubes.

So the method correctly reproduces the example.

---

Final Computation

Running the algorithm yields:

$$127035954683$$

This equals:

$$5027^3$$

Its digit permutations produce exactly five cubes.

---

Final Verification

• It is indeed a cube:

$$5027^3 = 127035954683$$

• The permutation class contains exactly five cubes.
• No smaller cube satisfies the condition.

Therefore the result is correct.

Answer: 127035954683