I was working on problem 52 yesterday, and thought I might share my insights.
The problem requires you to find the smallest integer n such that n, 2n, 3n, 4n, 5n, and 6n are all anagrams of one another.
As with many Project Euler challenges, it pays to fiddle with the maths before trying to find the answer in code. In this case, we can see that n must be less than 1/6th of the next power of ten. Why? Simple: if n is greater than or equal to 1/6th of the next power of ten, then n * 6 will have more digits than n, which immediately precludes the possibility that the two numbers will be anagrams of one another.
Bearing that in mind, here is my Python solution, which found the answer in 1.7 seconds.
def check_anagram(n):
stuff = []
for i in range(1,7):
stuff.append(sorted(list(str(n*i))))
if stuff.count(stuff[0]) == len(stuff): #1
print("RESULT!")
print([n, n*2, n*3, n*4, n*5, n*6])
return True
return False
counter = [i for i in range(1,1000000) if len(str(i*6)) == len(str(i))]
for i in counter:
if check_anagram(i) == True:
break
There is a fairly huge optimisation to be made here. While I like the line marked #1 above, it requires us to first gather up all the sorted versions of the multiples of n before performing a test. If instead we generate the sorted multiples one at a time and test them for equivalence to n immediately, we save a lot of sorting; plus, we no longer have to keep a running list of all the sorted multiples. Here's an implementation that runs in 1.1 seconds. I've also moved the "victory" code out of the check_anagram function.def check_anagram(n):
stuff = sorted(str(n))
for i in range(2,7):
if stuff != sorted(str(n*i)):
return False
return True
counter = [i for i in range(1,1000000) if len(str(i*6)) == len(str(i))]
for i in counter:
if check_anagram(i) == True:
print("RESULT!")
print([i, i*2, i*3, i*4, i*5, i*6])
break
UPDATE: Upon returning to this, I realised I made at least one huge error: my counter should have been a generator and not a list. Making it a generator expression means the evaluation becomes lazy, thereby preventing using a large amount of memory to store the whole list of numbers to test, instead generating the next number only when needed (and implicitly stopping when we reach our solution). Updated code:def check_anagram(n):
stuff = sorted(str(n))
for i in range(2,7):
if stuff != sorted(str(n*i)):
return False
return True
counter = (i for i in range(1,1000000) if len(str(i*6)) == len(str(i)))
for i in counter:
if check_anagram(i) == True:
print("RESULT!")
print([i, i*2, i*3, i*4, i*5, i*6])
break
