# Project Euler Problem 47 Solution

## Question

The first two consecutive numbers to have two distinct prime factors are:

\displaystyle \begin{aligned} 14 & = 2 \times 7 \\ 15 & = 3 \times 5 \end{aligned}

The first three consecutive numbers to have three distinct prime factors are:

\displaystyle \begin{aligned} 644 & = 2^2 \times 7 \times 23 \\ 645 & = 3 \times 5 \times 43 \\ 646 & = 2 \times 17 \times 19 \end{aligned}

Find the first four consecutive integers to have four distinct primes factors. What is the first of these numbers?

import Data.List (nub)

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

factorize :: Int -> [Int]
factorize n = primeFactors n primes where
primeFactors 1 _ = []
primeFactors _ [] = []
primeFactors m (p:ps) | m < p * p = [m]
| r == 0 = p : primeFactors q (p:ps)
| otherwise = primeFactors m ps
where (q, r) = quotRem m p

uniqueFactors :: Int -> Int
uniqueFactors = length . nub . factorize

chunks :: Int -> [a] -> [[a]]
chunks n l | length chunk < n = []
| otherwise = chunk : chunks n (tail l)
where chunk = take n l

candidates :: [[Int]]
candidates = [cons | cons <- chunks 4 [1..], all ((== 4) . uniqueFactors) cons]

main :: IO ()
main = print $head$ head candidates
$ghc -O2 -o consecutive-factors consecutive-factors.hs$ time ./consecutive-factors
real   0m0.096s
user   0m0.096s
sys    0m0.000s

## Python

#!/usr/bin/env python
import math

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 distinct_prime_factors(n):
return set(factorize(n))

def main():
chain = []
search = 4
for n in range(1, 1000000):
if len(distinct_prime_factors(n)) == search:
chain.append(n)
print(next(chain[i:i+search] for i, n in enumerate(chain) if chain[i:i+search] == list(range(n, n+search)))[0])

if __name__ == "__main__": main()
$time python3 consecutive-factors.py real 0m16.815s user 0m16.796s sys 0m0.016s ## Ruby #!/usr/bin/env ruby require 'mathn' puts (1..1000000).each_cons(4).detect { |nums| nums.all? { |n| n.prime_division.length == 4 } }[0] $ time ruby consecutive-factors.rb
real   0m1.656s
user   0m1.648s
sys    0m0.004s