Project Euler 47: Find the first four consecutive integers to have four distinct primes factors

Project Euler 47 Problem Description

Project Euler 47: 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?

Analysis

Each integer n is checked for a number of distinct prime factors, nf. If the number has nf distinct prime factors we increment a counter by 1, otherwise the counter is reset to zero. If the counter reaches our desired sequence length, ns, we print the starting value for that sequence and subtract one from the counter as the next number may be both the next number of the current sequence and the first number of another.

Consider the example shown above: if our nf=3 and ns=2 the first sequence is 644 and 645. The second sequence is 645 and 646. This process continues until we reach our predefined limit, L.

This solution was augmented to meet the requirements for the HackerRank Project Euler 47 to find ALL initial sequence values, sorted in ascending order, as more than one may exist withing a specific range.

for i in xrange(2, L):
    if f[i] == nf:
        c+= 1
        if c == ns:
            print i-ns+1
            c-= 1

If, however, that number, n does not have nf distinct prime factors then we calculate the number of distinct prime factors for that number and all multiples of that number until we reach our limit, L.

Sieving the number of distinct prime factors

This is sieving the number of distinct prime factors on the fly and only having to calculate those to consider each number. This method also extends the solution to other combinations of nf ranging from 2 through 6 and ns ranging from 2 through 16.

else:
    c = 0
    if f[n] == 0: f[n::n] = [x+1 for x in f[n::n]]

As an example, for nf=4 and ns=3 with a limit of 50,000 our starting numbers would be 37960, 44484, 45694. More specifically the first sequence of length 3 that have 4 distinct prime factors under 50,000 would be:
37960: 2, 5, 13, 73
37961: 7, 11, 17, 29
37962: 2, 3, 19, 37

The initial value, 37960, is all that is required to report and would be the answer to this question if the parameters were nf=4 and ns=3.

This program and method
solves all test cases for
Project Euler 47 on HackerRank

Project Euler 47 Solution

Afterthoughts

• Reference: The On-Line Encyclopedia of Integer Sequences (OEIS) A075044: a(0) = 1; a(n) = the smallest number k such that n numbers from k to k+n-1 have n distinct prime divisors, or 0 if no such number exists.
  
• Mathematica: i=1;NestWhile[4==Length@FactorInteger@i++&,,Nand,4];i-4
  

nf	ns	start
2	2	14
2	3	20
2	4	33
2	5	54
2	6	91
2	8	141
3	2	230
3	3	644
3	4	1308
3	5	2664
3	6	6850
3	7	10280
3	8	39693
3	9	44360
3	10	48919
3	11	218972
3	14	526095
3	15	17233173
3	16	127890362
4	2	7314
4	3	37960
4	4	answer to this problem
4	5	357642
4	7	1217250
4	8	14273478
4	9	44939642
4	10	76067298
4	11	163459742
5	2	254540
5	3	1042404
5	4	21871365
5	5	129963314
6	2	11243154
6	3	323567034