Problem #49 involves arithmetic sequences where the elements of the sequences are rearrangements of the digits in the other terms of the sequence. The problem reads:
Project Euler Problem 49: Prime permutations
The arithmetic sequence, 1487, 4817, 8147, in which each of the terms increases by 3330, is unusual in two ways: (i) each of the three terms are prime, and, (ii) each of the 4-digit numbers are permutations of one another.
There are no arithmetic sequences made up of three 1-, 2-, or 3-digit primes, exhibiting this property, but there is one other 4-digit increasing sequence.
What 12-digit number do you form by concatenating the three terms in this sequence?
My solution for this problem probably falls into the category of brute force, and unfortunately, it does not run in under a second in Python 2.7. Here is my solution:
Solution #1: Brute Force Approach
We begin by using a sieve to get a list of all the four digit primes. Next, we run through the list and do casework on the first and third terms in the arithmetic sequence. The second term can be found by averaging the others, and once it is verified that the second term is in the list of primes and that each prime is a rearrangement of the digits in the other primes, the problem is solved. Here is an implementation of this approach in Python 2.7:
'''
Author: Walker Kroubalkian
Sieve Approach to Project Euler Problem #49
'''
import time
def sieveEratosthenes(n):
myPrimes = []
primePossible = [True]*(n+1)
primePossible[0] = False
primePossible[1] = False
for (i,possible) in enumerate(primePossible):
if possible:
for x in range(i*i, (n+1), i):
primePossible[x] = False
myPrimes.append(i)
return myPrimes
def equivalentString(a,b):
aList = []
bList = []
a = str(a)
b = str(b)
for x in a:
aList.append(x)
for x in b:
bList.append(x)
return sorted(aList) == sorted(bList)
def projectEulerProblemFortyNine():
allPrimes = sieveEratosthenes(10000)
fourDigit = []
for x in allPrimes:
if x>1000:
fourDigit.append(x)
allTriples = []
l = len(fourDigit)
for a in range(l):
for b in range(a+1, l):
v1 = fourDigit[a]
v2 = fourDigit[b]
v3 = (v1+v2)/2
if v3 in fourDigit:
if equivalentString(v1, v2) and equivalentString(v1, v3):
allTriples.append(sorted([v1,v2,v3]))
final = []
for x in allTriples:
s = ""
for y in x:
s+=str(y)
final.append(s)
return final
start = time.time()
print projectEulerProblemFortyNine()
print ("--- %s seconds ---" % (time.time()-start))
'''
Prints
['148748178147', '296962999629']
--- 5.9415140152 seconds ---
for no input
'''
And with that, we’re done. It took 5.94 seconds to run through all the 4-digit primes… yikes. I may come back to this problem to look for a more efficient solution eventually.
Thanks for reading! See you tomorrow.
The Inner Machinations of Walker 