Euler Solution 49

From ProgSoc Wiki

Jump to: navigation, search

Solutions for Problem 49

The arithmetic sequence 1487, 4817, 8147 (each 3330 more than the previous element) is interesting as these numbers are all prime and are permutations of the same digits. There is one other such sequence of 4 digit primes, find it.

Haskell by SanguineV

Runtime: 29.909ms (on aglaope)

import Data.List

{- Prime numbers as usual. -}
primes :: [Integer]
primes = 2:3:primes'
  where
    1:p:candidates  = [6*k+r | k <- [0..], r <- [1,5]]
    primes'        = p : filter isPrime candidates
    isPrime n       = all (not . divides n) $ takeWhile (\p -> p*p <= n) primes'
    divides n p     = n `mod` p == 0

{- Find the digits of an integer as a list of integers -}
digs :: Integer -> [Integer]
digs n | n < 10 = [n]
digs n = [mod n 10] ++ (digs (div n 10))

{- Determine if an element is in a sorted list, restrict to Integers -}
elem' :: Integer -> [Integer] -> Bool
elem' i [] = False
elem' i (x:xs) | x == i = True
elem' i (x:xs) | x > i = False
elem' i (x:xs) = elem' i xs

{- Given a list of integers, if three of them are arithmetic, return those 3 -}
arith :: [Integer] -> [Integer]
arith x | length x < 3 = []
arith (x1:x2:xs) | elem' (x2 + (x2 - x1)) xs = [x1,x2,x2 + x2 - x1]
arith (x1:x2:xs) = (arith ([x1] ++ xs)) ++ (arith ([x2] ++ xs))

{- All the 4 digit primes. -}
prims = takeWhile (< 10000) (dropWhile (< 1000) primes)

{- Do some preprocessing:
 - 1. find the digits of each prime and sort them: e.g. 8147 -> [[1],[4],[7],[8]]
 - 2. sort all the primes based on their digits
 - 3. group primes with the same digits together
 - 4. drop any prime group with less than 3 primes (of 4 digits) -}
prims2 = filter (\x -> length x > 2) 
             (groupBy (\a b -> fst a == fst b) 
                 (sort (map (\x -> (sort (digs x),x)) prims)))

{- Check all the prepocessed (grouped by same digits) primes and if they are
 - arithmetic then determine which 3 elements, if not wipe them.
 - Drop all the wiped elements and then print the resulting groups (two of them
 - as one group is already know we want the other).
 - You can then concatonate the digits of the group you want manually. -}
main = print (filter (\x -> length x > 0) (map (\x -> arith (map snd x)) prims2))

Python by Althalus

Runtime: 2.09s

from primeFunctions import genPrimes #Includes a sieve, prime tests, and other functions

def isPerm(n1,n2):
        n1,n2 = str(n1),str(n2)
        if len(n1) != len(n2): return False
        return all(n1.count(c) == n2.count(c) for c in n1) 

primes = [x for x in genPrimes(10000) if x > 999]

count = 0 
for p1 in primes:
    count += 1
    for p2 in primes[count:]:
        if isPerm(p1,p2):
            p3 = (p2 + (p2 - p1))
            if p1 != 1487 and p3 in primes:
                if isPerm(p1,p3):
                    print "answer: ", p1, p2, (p2 + (p2 - p1))
                    print "time: ", time() - start
Personal tools