Project Euler Problem 52

Solution

Answer: 142857

We seek the smallest positive integer $x$ such that

$$2x,;3x,;4x,;5x,;6x$$

all contain exactly the same digits as $x$, merely permuted.

A number with this property is sometimes called a permuted multiple.

---

Mathematical Analysis

The key condition is:

$$\text{digits}(x)=\text{digits}(2x)=\cdots=\text{digits}(6x)$$

where “digits” means the multiset of decimal digits.

A natural way to test whether two numbers contain the same digits is:

• convert to strings,
• sort the digits,
• compare the sorted strings.

For example:

$$125874 \to "125874" \to "124578"$$

$$251748 \to "251748" \to "124578"$$

so they match.

---

Important Observation: Same Number of Digits

If $x$ has $d$ digits, then $6x$ must also have $d$ digits.

Suppose $x$ has $d$ digits. Then

$$10^{d-1} \le x < 10^d$$

For $6x$ to also have $d$ digits:

$$6x < 10^d$$

so

$$x < \frac{10^d}{6}$$

This drastically narrows the search range.

For example, among 6-digit numbers:

$$100000 \le x < \frac{1000000}{6} \approx 166666$$

So only a small interval needs checking.

---

Algorithm

For each positive integer $x$:

1. Compute a canonical representation of its digits:

$$s(x)=\text{sorted digits of }x$$ 2. Check whether

$$s(x)=s(2x)=s(3x)=s(4x)=s(5x)=s(6x)$$ 3. The first such $x$ is the answer.

This brute force search is efficient because the solution occurs fairly early.

---

Python Implementation

def signature(n):
    """
    Return a canonical representation of the digits of n.
    Numbers with the same digits will have the same signature.
    """
    return ''.join(sorted(str(n)))

x = 1

while True:
    # Compute the digit signature of x
    sig = signature(x)

    # Check whether 2x through 6x have identical digit signatures
    if all(signature(k * x) == sig for k in range(2, 7)):
        print(x)
        break

    x += 1

---

Code Walkthrough

Function: signature

def signature(n):
    return ''.join(sorted(str(n)))

This converts the number into a string, sorts its digits, and joins them back together.

Example:

signature(125874)

• str(125874) → "125874"
• sorted(...) → ['1','2','4','5','7','8']
• join(...) → "124578"

Likewise:

signature(251748)

also produces "124578".

Thus the two numbers contain exactly the same digits.

---

Main Search Loop

x = 1

while True:

We test positive integers in increasing order.

---

Compute Signature

sig = signature(x)

Store the digit pattern of $x$.

---

Check Multiples

if all(signature(k * x) == sig for k in range(2, 7)):

This verifies:

$$2x,3x,4x,5x,6x$$

all have the same digit signature as $x$.

The all(...) expression returns True only if every comparison succeeds.

---

Output and Stop

print(x)
break

The problem asks for the smallest such integer, so the first one found is the answer.

---

Small Example Verification

The problem statement gives:

$$125874 \times 2 = 251748$$

Check signatures:

signature(125874) == signature(251748)

Both equal:

"124578"

So the example works correctly.

---

Final Verification

Running the program produces:

$$x = 142857$$

Now verify:

$$2x = 285714$$

$$3x = 428571$$

$$4x = 571428$$

$$5x = 714285$$

$$6x = 857142$$

Each is clearly a cyclic permutation of the same six digits:

$$1,2,4,5,7,8$$

Thus all conditions are satisfied.

---

Answer: 142857