Distinct primes factors

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?



In [1]:

    
from euler import canonical_decomposition



In [2]:

    
d = canonical_decomposition(644)
d









    Out[2]:





{2: 2, 7: 1, 23: 1}



In [3]:

    
len(d)









    Out[3]:





3



In [4]:

    
from itertools import count



In [5]:

    
def foo(n):
    for i in count(2):
        for j in range(i, i + n):
            if len(canonical_decomposition(j)) != n:
                break
        else:
            return i



In [6]:

    
n = 4
%timeit foo(n)
foo(n)









    



1 loop, best of 3: 1.77 s per loop






    Out[6]:





134043



In [7]:

    
from functools import lru_cache



In [8]:

    
@lru_cache(n)
def n_distinct_prime_factors(x):
    return len(canonical_decomposition(x))



In [9]:

    
def foo(n):
    for i in count(2):
        for j in range(i, i + n):
            if n_distinct_prime_factors(j) != n:
                break
        else:
            return i



In [10]:

    
n = 4
%timeit foo(n)
foo(n)









    



1 loop, best of 3: 1.56 s per loop






    Out[10]:





134043



In [11]:

    
def foo(n):
    i = 2
    while True:
        for j in range(i, i + n):
            if len(canonical_decomposition(j)) != n:
                i = j + 1
                break
        else:
            return i



In [12]:

    
n = 4
%timeit foo(n)
foo(n)









    



1 loop, best of 3: 1.49 s per loop






    Out[12]:





134043



In [13]:

    
i = 2
list(range(i-1, i-n-1, -1))









    Out[13]:





[1, 0, -1, -2]



In [14]:

    
def foo(n):
    i = 2
    while True:
        if n_distinct_prime_factors(i) != n:
            i += n
            continue

        # Search backwards.
        for j in range(i-1, i-n-1, -1):
            if j < 2 or n_distinct_prime_factors(j) != n:
                first_good = j + 1
                break
        else:
            first_good = j

        # Search forwards.
        for j in range(i+1, first_good+n):
            if n_distinct_prime_factors(j) != n:
                i = j + n
                break
        else:
            return i



In [15]:

    
n = 4
%timeit foo(n)
foo(n)









    



1 loop, best of 3: 479 ms per loop






    Out[15]:





134043

I like cells 8 and 9 the most. They have the best combination of readability and speed.

Cell 11 is a little faster, but the while loop is ugly.

Cell 14 is fast, but makes my head hurt.