## 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`

.

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[i] ==0: for q in xrange(i, L, i): f[q]+= 1

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`

.

#### Project Euler 47 Solution

Runs < 0.001 seconds in Python 2.7.Use this link to get the Project Euler 47 Solution Python 2.7 source.

#### Answer

Slowly swipe from either end beginning with the white vertical bar to get an idea of the starting or ending digits. For less drama, just double click the answer area. The distance between the two bars will give you an idea of the magnitude. Touch devices can tap and hold the center of the box between the two bars and choose*define*to reveal the answer.

#### 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[[email protected]@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

*Project Euler 47 Solution last updated*

hello…i always get impressed by how much time your code take to run, though i use the same method you use…but the factor here is the “factor” function you have…what method do you use to get the factors of your numbers?

ah ok…i just saw your reference to the factor function..thanks anyway

what do this statement means?

while ci != ns:

n += 1

if len(factor(n)) == nf: ci += 1

else: ci = 0

Variable ‘ci’ is the consecutive integer counter that is incremented by 1 when a number has 4 distinct factors. If we find 4 numbers in a row (consecutive) with this property then we have satisfied the condition of the while statement (and the problem).

len(factor(n)) is the number of distinct factors of the number ‘n’.

644 =2 x 2 x 7 x 23

645 =3 x 5 x 43

646 =2 x 17 x 19

644 and 646 both have the prime factor 2. Then, how come these are the 1st three consecutive numbers to have three distinct prime factors??

I interpreted “distinct” to mean relative to the number, not to the set. Otherwise we would have eight distinct prime factors for the set.

Hope this helps.

You have in code 2*3*5*11, not 2*3*5*7 as start.

Oops! Thanks for catching that. We’ve corrected it.