Detailed mathematical approach

Problem Summary

We seek the smallest cube for which exactly five permutations of its decimal digits are also cubes. The key word is exactly: a signature that produces five cubes is valid only if no sixth cube with the same digits appears later in the same digit-length range.

The familiar checkpoint example is the 3-member family \(345^3 = 41063625\), \(384^3 = 56623104\), and \(405^3 = 66430125\). All three cubes contain the same digits, merely in a different order. Problem 62 asks for the analogous phenomenon with family size \(5\), and then asks for the smallest cube inside that family.

Mathematical Approach

The implementations do not compare cubes pairwise. Instead, they turn each cube into a canonical digit signature and group together all cubes with the same signature. The only subtle point is deciding when a group of size \(5\) is final rather than temporary.

Canonical signature of a cube

Write

$c(n)=n^3.$

For any positive integer \(x\), define its digit signature by sorting its decimal digits:

$\sigma(x)=\operatorname{sort}(\text{digits}(x)).$

Two integers are permutations of one another if and only if they have the same multiset of digits, and that is equivalent to having the same sorted digit string. Therefore two cubes belong to the same permutation family exactly when

$\sigma(c(a))=\sigma(c(b)).$

This converts the problem from “search among all digit permutations” into “group equal signatures together”.

Digit-length buckets are independent

Permuting digits preserves the number of digits, so a \(d\)-digit cube can only be paired with other \(d\)-digit cubes. That lets us split the search into independent buckets

$B_d=\{n\ge 1: 10^{d-1}\le n^3\lt 10^d\}.$

Inside one bucket, define the signature class

$G_{d,s}=\{n^3 : n\in B_d,\ \sigma(n^3)=s\}.$

Every valid family of cubic permutations is one of these classes. A rearrangement that would place a zero in front is irrelevant here, because it would no longer be a \(d\)-digit number and therefore would not lie in the same bucket.

Why the first successful bucket already determines the answer

Suppose \(d_0\) is the first digit length for which at least one class \(G_{d_0,s}\) has size \(5\). Any cube in a later bucket has more digits and is therefore numerically larger than every cube in bucket \(d_0\). So once bucket \(d_0\) is fully processed, the global answer must be the smallest cube among the size-5 classes inside that bucket.

This is the main invariant behind the streaming solution: we never need to keep data from older digit lengths after a bucket has been closed and checked.

Why “first time a count reaches 5” is not enough

A signature can hit count \(5\) partway through a bucket and later grow to \(6\). That would violate the word “exactly”. Therefore the correct stopping rule is:

Check a bucket only after all cubes with that digit length have been generated, and then accept those signature classes whose final size is exactly \(5\).

This explains why the implementations wait until the digit count changes before they inspect the accumulated groups.

Worked example: the size-3 checkpoint

The checkpoint family uses

$345^3=41063625,\qquad 384^3=56623104,\qquad 405^3=66430125.$

All three cubes have the same signature

$\sigma(41063625)=\sigma(56623104)=\sigma(66430125)=01234566.$

So within the 8-digit bucket there is a class \(G_{8,01234566}\) of size \(3\). The implementations use this known fact as a checkpoint: if the target family size is changed from \(5\) to \(3\), the returned cube must be \(41063625\), the smallest member of that class.

How the Code Works

Streaming through cubes

The C++, Python, and Java implementations iterate through \(n=1,2,3,\dots\), compute \(n^3\), measure its digit count, build the signature by sorting the decimal representation, and append the cube to the list stored under that signature. At any moment the map contains data only for the current digit-length bucket.

Closing a bucket safely

When the digit count increases, the previous bucket is complete. The implementation then scans all stored signature classes, keeps those whose final size equals the requested family size, and returns the smallest cube among them if any exist. If none exist, the map is cleared and the next bucket begins. The same code path works for the original target \(5\) and for the built-in checkpoint target \(3\).

Complexity Analysis

If the search stops after testing roots up to \(N\), and the largest cube encountered has \(d\) decimal digits, then constructing one signature costs \(O(d \log d)\) because the implementations sort the digits. The map update is \(O(1)\) on average in the hash-based versions and \(O(\log S)\) in the ordered-map variant, where \(S\) is the number of active signatures in the current bucket.

Hence the total running time is \(O(N(d \log d + \log S))\) in the most conservative view, and effectively \(O(N d \log d)\) in the hash-based view. Memory usage is proportional to the current bucket: the implementations store one list of cubes per active signature, so the space requirement is \(O(B)\), where \(B\) is the number of cubes whose digit length matches the current bucket, and certainly \(O(N)\) in the worst case.

Footnotes and References

1. Problem page: Project Euler 62
2. Cube number: Wikipedia - Cube number
3. Permutation: Wikipedia - Permutation
4. Multiset: Wikipedia - Multiset
5. Hash table: Wikipedia - Hash table