Permuted multiples in python

Question

How can I improve efficiency/readability of the following code?

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.

https://projecteuler.net/problem=52

#! /usr/bin/env python
def sameDigits(a, b):
 return sorted(str(a)) == sorted(str(b))
def main():
 found = False
 i = 2
 while not found:
 x2 = i * 2
 x3 = i * 3
 x4 = i * 4
 x5 = i * 5
 x6 = i * 6
 if (
 sameDigits(i, x2)
 and sameDigits(i, x3)
 and sameDigits(i, x4)
 and sameDigits(i, x5)
 and sameDigits(i, x6)
 ):
 found = True
 print(i)
 i += 1
if __name__ == "__main__":
 main()

Answer 1

Readablility/pythonization

PEP8 is your friend

Use recommended practices, like using snake_case instead of camelCase for functions and variables.

Short-circuit evaluation

and and or operators evaluate the second argument only if the first can't tell the value - like False for and and True for or. So, if you move all multiplications in a condition, some of them will not be calculated.

if same_digits(i, x*2) and same_digits(i,x*3) and ...

Move repeating expressions into loops

Luckily, Python has functions to check several expressions for True at once: any for at least one True and all for all. They work with a short-circuit and can work with any iterable - like generator expression:

if all(same_digits(i, x*j) for j in range(1,7)):

Generating an infinite loop with itertools.count()

There's a more pythonic way to have something like unlimited range: itertools.count()

from itertools import count
for i in count(2):
 #no need to increment i

Using break instead of found variable

Though not a structured feature, it can be useful

for ...:
 if ...:
 break

Separate algorithm and input-output

Return the value from the function, not output it. return statement works just like break, so we can omit it.

All together

from itertools import count
def same_digits(a, b):
 return sorted(str(a))==sorted(str(b))
def main():
 for i in count(2):
 if all(same_digits(i, x*j) for j in range(1,7)):
 return i
if __name__ == "__main__":
 print(main())

Optimizations

I don't think you can change the complexity of an algorithm, but you can avoid unnecessary actions. Profile the code for everything below - Python is a very high-level programming language, and built-in functions can prove faster then better algorithms for small optimizations .

same_digits

Instead of using str, divide (with divmod) both numbers and count digits in a list - adding for a and subtracting for b. If at some point you reach negative value or lengths are different - return False. Counting digits is slightly faster than sorting, and you avoid dividing after problem is found.

Multiples of 9

The number with this property should be a very specific. The sum of its digits remains the same after multiplication (because digits are the same). If the number is a multiple of 3, the sum of its digits also will be the multiple of 3, the same for 9. But \3ドルi\$ is a multiple of 3 and has the same digits, so \$i\$ will be the multiple of 3, \$i=3k\$. Once again, \3ドルi=9k\$ will be the multiple of 9, so i will be the multiple of 9. No sense to check not multiples of 9:

for i in count(9,9):

6*i should have the same number of digits

The second idea is that 6*i should have the same number of digits with i. You can refactor the loop into nested loops: outer for the number of digits (name it d) and inner for numbers from 100...08 (d digits) to 100..00 (d+1 digits)/6, everything bigger will make 6*i have d+1 digit.

Answer 2

Pavlo Slavynskyy's answer is excellent!

Depending how concerned you are with performance, the built-in Counter class might work for counting digits (or it might be really slow; IDK).

Another small point: The way the same_digits function is being used, the digits of i are being checked six (or seven) times. That should be avoidable...

You don't strictly need a loop for the task at hand; next has some gotchas, but should work well here. Taking "no explicit loops" all the way gives us something like

from collections import Counter
from itertools import chain, count
from functools import reduce
from more_itertools import pairwise # or copypast from https://docs.python.org/3/library/itertools.html#itertools-recipes
def f():
 return next(
 i
 for i
 in chain.from_iterable(range(low, high, 9)
 for (low, high)
 in zip((10**d + 8 for d in count(1)),
 (10**d // 6 for d in count(2))))
 if all(m1 == m2
 for (m1, m2)
 in pairwise(frozenset(Counter(str(i * m)).items())
 for m
 in range(1, 7)))
 )

Frankly that could use some more documentation :)