Project Euler Problem 49 Solution

Question

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?

Haskell

import Data.List (sort)

primes :: [Int]
primes = 2 : sieve primes [3,5..] where
    sieve (p:ps) xs = h ++ sieve ps [x | x <- t, rem x p /= 0]
                      where (h, t) = span (< p*p) xs

isPrime :: Int -> Bool
isPrime n | n < 1 = False
          | otherwise = not $ or [n `rem` x == 0 | x <- [2..floor $ sqrt $ fromIntegral n]]

candidates :: [[Int]]
candidates = tail [ps | p <- dropWhile (< 1000) primes,
                        let ps = [p, p + 3330, p + 6660],
                        all isPrime ps,
                        let sorted = map (sort . show) ps,
                        all (== head sorted) sorted]

main :: IO ()
main = putStrLn $ concatMap show $ head candidates
$ ghc -O2 -o prime-permutations prime-permutations.hs
$ time ./prime-permutations
real   0m0.003s
user   0m0.000s
sys    0m0.000s

Python

#!/usr/bin/env python
# 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?
import math
from itertools import *
from collections import defaultdict
from functools import reduce

def factorize(n):
    if n < 1:
        raise ValueError('fact() argument should be >= 1')
    if n == 1:
        return []  # special case
    res = []
    # iterate over all even numbers first.
    while n % 2 == 0:
        res.append(2)
        n //= 2
    # try odd numbers up to sqrt(n)
    limit = math.sqrt(n+1)
    i = 3
    while i <= limit:
        if n % i == 0:
            res.append(i)
            n //= i
            limit = math.sqrt(n+i)
        else:
            i += 2
    if n != 1:
        res.append(n)
    return res

def num_divisors(n):
    factors = sorted(factorize(n))
    histogram = defaultdict(int)
    for factor in factors:
        histogram[factor] += 1
    # number of divisors is equal to product of 
    # incremented exponents of prime factors
    from operator import mul
    try:
        return reduce(mul, [exponent + 1 for exponent in list(histogram.values())])
    except:
        return 1

def is_permutations(seq):
    s = [str(x) for x in seq]
    p = [''.join(x) for x in permutations(s[0])]
    for i in s:
        if i not in p:
            return False
    return True

def is_prime(num):
    if num % 2 == 0:
        return False
    if num % 3 == 0:
        return False

    if num_divisors(num) == 2 and num > 1:
        return True
    else:
        return False

def sieve(n):
    numbers = list(range(2, n+1))
    p = 2
    j = 0
    done = False
    while not done:
        for i, n in enumerate(numbers):
            if n % p == 0 and n!=p:
                numbers.pop(i)
        j += 1
        p = numbers[j]
        if p**2 > n:
            done = True
    return numbers

def arithmetic_subsequences(seq, length=3):
    for x in seq:
        steps = [y-x for y in seq[seq.index(x):]]
        for step in steps:
            if step == 0: continue
            found = True
            for i in range(length):
                if not x + (i*step) in seq:
                    found = False
            if found:
                yield [x + (i*step) for i in range(length)]

def main():
    primes = [p for p in sieve(10000) if len(str(p)) == 4]
    print(max(''.join(str(x) for x in seq) for seq in arithmetic_subsequences(primes, 3) if is_permutations(seq)))

if __name__ == "__main__":
    main()
$ time python3 prime-sequence.py
real   0m19.825s
user   0m19.680s
sys    0m0.012s

Ruby

#!/usr/bin/env ruby
require 'mathn'
primes = (1488..9999).select { |n| n.prime? }
primes.each do |a|
  primes.select { |b| b > a }.each do |b|
    primes.select { |c| c > b }.each do |c|
      if c-b == b-a &&
        a.to_s.split('').sort == b.to_s.split('').sort &&
        b.to_s.split('').sort == c.to_s.split('').sort &&
        c.to_s.split('').sort == a.to_s.split('').sort
        puts a.to_s + b.to_s + c.to_s; exit
      end
    end
  end
end
$ time ruby prime-sequence.rb
real   0m12.115s
user   0m11.984s
sys    0m0.028s

Questions? Comments? Send me an email: z@chdenton.com