(No Ratings Yet)

## Project Euler Problem 47 Solution

#### Problem Description

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

Simple approach that took only a few minutes to write. Start with the smallest possible number that has 4 distinct prime factors (210 = 2 x 3 x 5 x 7). Continue to increment from that number until four consecutive numbers have four distinct prime factors.

#### Solution

Runs < 5 seconds in Python.

```from Euler import factor   ci = 1 nf = 4 #number of distinct factors ns = 4 #number of consecutive integers n = 2*3*5*7 #starting candidate for search while ci != ns: n += 1 if len(factor(n)) == nf: ci += 1 else: ci = 0   print "Answer to PE47 = ", n-nf+1```

• More information on the Euler module can be found on the tools page.
• OEIS A075044
• Mathematica: `i=1;NestWhile[4==Length@FactorInteger@i++&,,Nand,4];i-4`

## Discussion

### 6 Responses to “Project Euler Problem 47 Solution”

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

Posted by Tony Veijalainen | December 29, 2010, 2:39 PM
2. 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??

Posted by rumi | February 12, 2011, 2:33 PM
• 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.

Posted by Mike | February 19, 2011, 12:42 AM
3. what do this statement means?

while ci != ns:
n += 1
if len(factor(n)) == nf: ci += 1
else: ci = 0

Posted by drel | October 18, 2011, 11:37 AM
• 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’.

Posted by Mike | October 18, 2011, 8:30 PM