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.

• user203258: @ vnp I fully understand what you said except for the part of the seven levels of indentation, can you explain how this is doable by folding it into the loop? concerning studying some math, in fact I actually started doing so not for long but I'm currently studying.
• user203258: I guess what you mean by folding into the loop is I have to calculate 2x, 3x, 4x, 5x, 6x for every number even if it is not a permutation, if that's what you mean then I will be doing 6 calculations per number(whether a permutation or not) anyway if that's not what you mean please show some example for me to understand

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
```