Project Euler #47: find four consecutive integers, each with four distinct prime factors

Question

Project Euler Problem 47

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

This is my solution for problem 47 on Project Euler.

def primes2(n):
    """ Input n>=6, Returns a list of primes, 2 <= p < n """
    n, correction = n-n%6+6, 2-(n%6>1)
    sieve = [True] * (n//3)
    for i in range(1,int(n**0.5)//3+1):
      if sieve[i]:
        k=3*i+1|1
        sieve[      k*k//3      ::2*k] = [False] * ((n//6-k*k//6-1)//k+1)
        sieve[k*(k-2*(i&1)+4)//3::2*k] = [False] * ((n//6-k*(k-2*(i&1)+4)//6-1)//k+1)
    return [2,3] + [3*i+1|1 for i in range(1,n//3-correction) if sieve[i]]

def findSeq(lst):
    """ Returns the index of the first term of a 4 term arithmetic sequence """
    for x in range(len(lst)-2):
        if sum(lst[x:x+4]) == (4*lst[x]+6):
                return x
    return False

def generateFactors(num,values,factors):
    if len(values[num]) > 0:
        factors += values[num]
        return factors
    else:
        for i in range(2,num-1):
            if num % i == 0:
                return generateFactors(num//i,values,factors+[i])
n = 200000

primes = set(primes2(n))

factors = dict([[x,[]] for x in range(2,n)])

for item in factors.keys():
    if item in primes:
        factors[item] = [item]
    else:
        factors[item] = generateFactors(item,factors,[])

fourFact = [item for item in factors.keys() if len(set(factors[item])) == 4]

pos = findSeq(fourFact)

print(fourFact[pos])

The primes2 function isn't my code but I have included it for completeness. I am looking for feedback on my implementation and how to optimise the code.

Answer 1

Since you already have a nice implementation of a prime sieve, you should make use of it when checking for prime factors. Note that prime factors are needed, not all factors. I definitely would not use a recursive algorithm for this. It can fail with a stack limit and you need a lot of unreadable code just to set up the data structures.

I would use something simple like this:

from math import sqrt

def prime_factors(n, primes=None):
    """(int) -> iterable of ints

    Yields the prime factors of a number, excluding 1.
    Optionally takes an iterable of pre-computed prime numbers.
    """
    max_p = int(sqrt(n)) + 1
    if primes is None:
        primes = primes2(max_p)
    for p in primes:
        while n > 1 and n % p == 0:
            n //= p
            yield p
        if n == 1 or p >= max_p:
            break
    if n > 1:
        yield n

The second part of the task can be done in multiple ways. You have chosen to just define a maximum value up to which to search, filter all numbers with the right number of prime factors and then search for an increasing sequence. This will take quite a bit of memory, potentially, depending on where the answer is.

An easier way is to only remember the last four numbers with the right number of prime factors using a collections.deque with a maxlen=4, and check if they are an increasing sequence:

from itertools import count
from collections import deque

def diff(it):
    it = iter(it)
    x = next(it)
    for y in it:
        yield y - x
        x = y

def is_increasing_sequence(it):
    return all(d == 1 for d in diff(it))

if __name__ == "__main__":
    d = deque([], maxlen=4)
    for n in count(1):
        if len(set(prime_factors(n))) == 4:
            d.append(n)
            if len(d) == 4 and is_increasing_sequence(d):
                print(d[0])
                break

This can be sped up by re-introducing a maximum number to check and pre-computing the prime numbers for the prime number factorization:

if __name__ == "__main__":
    max_n = 200000
    primes = primes2(max_n)
    d = deque([], maxlen=4)
    for n in range(1, max_n):
        if len(set(prime_factors(n, primes=primes))) == 4:
            d.append(n)
            if len(d) == 4 and is_increasing_sequence(d):
                print(d[0])
                break

This solves the problem in less than a second on my machine, which is similar to your code.

Note that I followed Python's official style-guide, PEP8, which recommends lower_case for functions and variables and surrounded my code with an if __name__ == "__main__": guard to allow importing from this script without running the code. This is especially important for Project Euler, as you will need e.g. the prime sieve and the prime number factorization again in other problems.