Project Euler # 52 Permuted multiples in Python

Question

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.

from time import time


def is_permutation(n1, n2):
    """returns True if n1 is permutation of n2"""
    if n1 == n2:
        return False
    str1 = str(n1)
    str2 = str(n2)
    digits1 = {digit: str1.count(digit) for digit in str1}
    digits2 = {digit: str2.count(digit) for digit in str2}
    if not digits1 == digits2:
        return False
    return True


def check_multiples(n, start=10):
    """checks 2x, 3x, 4x, 5x, 6x and returns the numbers if they are permutations."""
    for x1 in range(start, n):
        x2 = x1 * 2
        if is_permutation(x1, x2):
            x3 = x1 * 3
            if is_permutation(x2, x3):
                x4 = x1 * 4
                if is_permutation(x3, x4):
                    x5 = x1 * 5
                    if is_permutation(x4, x5):
                        x6 = x1 * 6
                        if is_permutation(x5, x6):
                            return x1, x2, x3, x4, x5, x6


if __name__ == '__main__':
    start_time = time()
    print(check_multiples(1000000, 125000)[0])
    print(f'Time: {time() - start_time} seconds.')

Answer 1

• For the umpteenth time, do not write

  if not digits1 == digits2:
      return False
  return True
  

  Do write

  return digits1 == digits2
  

• The magic number 125000 must be explained. Preferably in the code, not in comments.

• Seven levels of indentation should be immediately seen as a big bright red flag, style wise. At least fold it into the loop.

• Seven levels of indentation should be immediately seen as a big bright red flag, algorithm wise. How would you approach a question asking for 16, rather than 6, multiples? As a side note, if you continue with PE, you have a chance to encounter it.

• Expanding on the bullet above, please take my advice and study some math. This problem does have a nice solution. Ponder on the fact that \$142857 * 7 = 1000000 - 1\$. An Euler's generalization of Fermat's Little theorem is a must. PE is very fond of it.

  And stop brute forcing.

Answer 2

Disclaimer: none of this is tested

Getting rid of the multiple levels of indentations

First observation, instead of checking is_permutation(x{n-1}, x{n}), you could check is_permutation(x{0}, x{n}).

def check_multiples(n, start=10):
    """checks 2x, 3x, 4x, 5x, 6x and returns the numbers if they are permutations."""
    for x in range(start, n):
        x2 = x * 2
        if is_permutation(x, x2):
            x3 = x * 3
            if is_permutation(x, x3):
                x4 = x * 4
                if is_permutation(x, x4):
                    x5 = x * 5
                    if is_permutation(x, x5):
                        x6 = x * 6
                        if is_permutation(x, x6):
                            return x, x2, x3, x4, x5, x6

Then, values x{n} are only used once, we do not need a temporary variable for them anymore. We can write:

def check_multiples(n, start=10):
    """checks 2x, 3x, 4x, 5x, 6x and returns the numbers if they are permutations."""
    for x in range(start, n):
        if is_permutation(x, x * 2):
            if is_permutation(x, x * 3):
                if is_permutation(x, x * 4):
                    if is_permutation(x, x * 5):
                        if is_permutation(x, x * 6):
                            return x, x * 2, x * 3, x * 4, x * 5, x *6

Then, this can be written as a single test:

def check_multiples(n, start=10):
    """checks 2x, 3x, 4x, 5x, 6x and returns the numbers if they are permutations."""
    for x in range(start, n):
        if is_permutation(x, x * 2) and
           is_permutation(x, x * 3) and
           is_permutation(x, x * 4) and
           is_permutation(x, x * 5) and
           is_permutation(x, x * 6):
             return x, x*2, x*3, x*4, x*5, x*6

Then, this can be rewritten using the all builtin

def check_multiples(n, start=10):
    """checks 2x, 3x, 4x, 5x, 6x and returns the numbers if they are permutations."""
    for x in range(start, n):
        if all(is_permutation(x, x * i) for i in range(2, 7))
             return x, x*2, x*3, x*4, x*5, x*6

Optimisation - small range

For many values of x, x and 6 * x do not have the same number of digits (and thus can be permutations of each other). You could limit yourself to relevant values of x.

Another way to do it could be to check x * 6 then x * 5 then ... down to x * 2 instead of going the other way round.

Optimisation - reduce duplicated computation

Everytime we compute is_permutation(x, foobar), we re-perform the same processing on the x value. This could be done once and for all:

def get_digit_count(n):
    s = str(n)
    return {digit: s.count(digit) for digit in s}


def check_multiples(n, start=10):
    """checks 2x, 3x, 4x, 5x, 6x and returns the numbers if they are permutations."""
    for x in range(start, n):
        digits = get_digit_count(x)
        if all(digits == get_digits_count(x * i) for i in range(2, 7))
             return x, x2, x3, x4, x5, x6
```