Merge Triplets to Form Target Triplet

project-euler
programming
Some simple observations
Author
Affiliation

Kim Hung Bui

Project Euler - 52. Permuted Multiples

Published

July 19, 2025

It can be seen that the number, \(125874\), and its double, \(251748\), contain exactly the same digits, but in a different order.

Find the smallest positive integer, \(x\), such that \(2x\), \(3x\), \(4x\), \(5x\), and \(6x\), contain the same digits.

1 Brute Force Idea (\(O(n^2)\) or worse)

Test each number x starting from 1, and check if 2x, ..., 6x are permutations of x. While that works, it’s not efficient if we don’t restrict the search space.

2 Key observations (To Reduce the Search Space)

2.1 Same number of digits:

If x has d digits, 6x must not have more digits than x, or they can’t be permutations.

So

len(x) == len(6x)

Example: If x = 100, then 6x = 600, same digit count (3). But x = 200, then 6x = 1200 (4 digits), not possible.

That gives a range to search in:

for x in range(10**(d-1), 10**d):
    ...

2.2 Digit permutation check:

Instead of sorting each time (\(O(n\log n)\)), use:

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

then

c = canonical(x)
all(c == canonical(i * x) for i in range(2, 7))

This function is creating a canonical (standardized) form of any number:

  • str(n) converts the number to a string (e.g., 123 → '123')

  • sorted(...) puts the digits in ascending order (e.g., '321' → ['1','2','3'])

  • ''.join(...) joins them back to a single string (e.g., ['1','2','3'] → '123')

So:

canonical(123) == '123'
canonical(231) == '123'
canonical(312) == '123'

All are permutations of the same digits ⇒ same canonical form

Time Complexity

  • Each check is ~O(1) due to short digit lengths

  • The loop is linear in x (but bounded by 6-digit numbers)

  • Much faster than O(n²) since the search space is tightly controlled

Code 
def canonical(n):
    return ''.join(sorted(str(n)))

def has_same_digits(x):
    c = canonical(x)
    return all(canonical(x * i) == c for i in range(2, 7))

def find_smallest_permuted_multiple():
    x = 100000
    while True:
        if has_same_digits(x):
            return x
        x += 1

print(find_smallest_permuted_multiple())  # Output: 142857
142857