# 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?

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.002s user 0m0.000s sys 0m0.002s ## 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   0m16.740s
user   0m16.731s
sys    0m0.008s

## 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.393s
user   0m12.368s
sys    0m0.024s