Project Euler Problem #52

Problem #52 is one of the few problems on Project Euler where many people will already know the answer before solving the question. The question reads:

Project Euler Problem 52: Permuted multiples
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.

As stated above, the number x with this property is incredibly well known and most people who make it to this question will probably know the answer by heart. Here is a programming solution just for completeness:

Solution #1: Brute Force Approach

We can observe that in order for the given property to be true, x, 2x, 3x, 4x, 5x, and 6x have to each have the same sum of digits. In order for this to be possible, x has to be a multiple of 9. From here we can simply iterate through all of the multiples of 9 until we find a value of x with the given property. Here is an implementation of this approach in Python 2.7:

 '''
 Author: Walker Kroubalkian
 Brute Force Approach to Project Euler Problem #52
 '''
 
 import time
 
 def enumerateString(a):
     aChars = []
     aNums = []
     for x in a:
         if x not in aChars:
             aChars.append(x)
             aNums.append([x,1])
         else:
             aNums[aChars.index(x)][1]+=1
     return aNums
 
 def isPermutation(a,b):
     return sorted(enumerateString(str(a))) == sorted(enumerateString(str(b)))
 
 def projectEulerProblemFiftyTwo(n):
     c = 9
     found = 0
     current = -1
     while(found<n):
         none = False
         for x in range(2,7):
             if(not isPermutation(c,x*c)):
                 none = True
                 break
         if not none:
             found+=1
             current = c
         c+=9
     return current
 
 start = time.time()
 print projectEulerProblemFiftyTwo(1)
 print ("--- %s seconds ---" % (time.time()-start))
 
 '''
 Prints
 
 142857
 --- 0.100811958313 seconds ---
 
 for input of n = 1.
 ''' 

And with that, we’re done. The question would have been much better if it had asked for the nth smallest number x with this property. In case you’re curious, the first few numbers are 142857, 1428570, 1429857, 14285700, 14298570, 14299857, etc. Ignoring the multiples of 10 in this list, we see an interesting pattern where it seems that the number 14299…99857 has this property for an arbitrary number of 9’s. It would be interesting to prove whether all numbers in this list are of this form. Regardless, there is a much better solution that I imagine most people who solved this question used:

Solution #2: Mathematical Knowledge Approach

We can simply recall that the digits in the first period of each of the fractions 1/7, 2/7, 3/7, 4/7, 5/7, and 6/7 are all rearrangements of 142857. Thus, 142857 is a number with this property. Guessing that this is the smallest number with this property, we’re done.

This fact adds to the property we discussed earlier. Multiplying each number in our list which is not a multiple of 10 by 7, we get 999999, 10008999, 100098999, 1000998999, etc. With this fact, we can guess that for n>=2, the nth number in this list will be (1000*10^(n+2) + (10^(n-2)-1)*10^4 + 8999)/7. With this result, we have an explicit form for infinitely many numbers x with this property.

Thanks for reading! See you tomorrow.