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

$$ 14 = 2 × 7 \\ 15 = 3 × 5 $$

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

$$ 644 = 2² × 7 × 23 \\ 645 = 3 × 5 × 43 \\ 646 = 2 × 17 × 19. $$

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

Version 1: Fun times with Itertools

First let's load up the prime factorization function we implemented earlier. Recall that this function returns a Counter with the prime factor as the key, and its exponent as the value.



In [1]:

    
%load_ext autoreload
%autoreload 2



In [2]:

    
from common.utils import prime_factors



In [3]:

    
from itertools import count, tee
from six.moves import map, reduce, zip

Define an $n$-wise iterator over an iterator, inspired by the implementation of pairwise in the Itertools recipes. It get $n$ iterators for the iterable, advances the $i$th iterator by $i$, and zips them back together.



In [4]:

    
def nwise(iterable, n=2):
    iters = tee(iterable, n)
    for i, it in enumerate(iters):
        for _ in range(i):
            next(it, None)
    return zip(*iters)

See some example calls below.



In [5]:

    
list(nwise(range(10), 9))









    Out[5]:





[(0, 1, 2, 3, 4, 5, 6, 7, 8), (1, 2, 3, 4, 5, 6, 7, 8, 9)]



In [6]:

    
list(nwise(range(10), 4))









    Out[6]:





[(0, 1, 2, 3),
 (1, 2, 3, 4),
 (2, 3, 4, 5),
 (3, 4, 5, 6),
 (4, 5, 6, 7),
 (5, 6, 7, 8),
 (6, 7, 8, 9)]

Now we can define our function, which (lazily) evaluates the prime factors of all integers greater than 1 and iterates over them $n$-wise (can be thought of as a sliding window of size $n$.) We use len to count the number of distinct factors (since the factors are returned as a Counter) and return the window if the numer of distinct prime factors of all numbers in the window is equal to $m$.



In [7]:

    
def consecutive_distinct_factors(n, m):
    """
    The first consecutive n numbers 
    to have m distinct prime factors
    """
    for factors in nwise(map(prime_factors, count(2)), n):
        if all(map(lambda x: len(x) == m, factors)):
            return factors



In [8]:

    
consecutive_distinct_factors(2, 2)









    Out[8]:





(Counter({2: 1, 7.0: 1}), Counter({3: 1, 5.0: 1}))

We could modify the loop in the method to return the first number from the window, rather than the prime factors of all the numbers in the window, but this makes our implementation unecessarily long and messy. Also, the prime factorizations actually yield more information, and while we could return both, we can also just uniquely determine the multiple from the prime factors.



In [9]:

    
# recall Python's built-in pow function
pow(3, 3)









    Out[9]:





27



In [10]:

    
c = prime_factors(24); c









    Out[10]:





Counter({2: 3, 3: 1})



In [11]:

    
# recall that map can be applied 
# to a variable number of lists, 
# i.e. map(func, (a0, a1, ...), (b0, b1, ...)) -> [func(a0, b0), func(a1, b1), ...]
list(map(pow, c.keys(), c.values()))









    Out[11]:





[8, 3]

Define the prod function, which is analogous to Python's built-in sum function.



In [12]:

    
prod = lambda xs: reduce(lambda x, y: x*y, xs, 1)

By convention, $x^0 = 1$ for all $x$ and $0! = 1$



In [13]:

    
prod([])









    Out[13]:





1



In [14]:

    
# calculate 6!
prod(range(1, 6+1))









    Out[14]:





720



In [15]:

    
prod(map(pow, c.keys(), c.values()))









    Out[15]:





24



In [16]:

    
multiple = lambda factors: prod(map(pow, factors.keys(), factors.values()))

Evaluate $2^3 \cdot 3$



In [17]:

    
multiple(c)









    Out[17]:





24

Now we can get the actual number, rather than the prime factorization.



In [18]:

    
list(map(multiple, consecutive_distinct_factors(2, 2)))









    Out[18]:





[14.0, 15.0]



In [19]:

    
list(map(multiple, consecutive_distinct_factors(3, 3)))









    Out[19]:





[644, 645.0, 646]



In [20]:

    
list(map(multiple, consecutive_distinct_factors(4, 4)))









    Out[20]:





[134043.0, 134044, 134045, 134046.0]

The answer is 134043