// you’re reading...
1 Star2 Stars3 Stars4 Stars5 Stars (13 votes, average: 5.00 out of 5)
Loading...

Project Euler Solutions

Project Euler 47 Solution

Project Euler 47 Solution

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

Project Euler 47Each 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.

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

Project Euler 47 Solution

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

Afterthoughts

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

Discussion

6 Responses to “Project Euler 47 Solution”

  1. 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?

    Posted by Abdallah | November 16, 2014, 11:55 AM
  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

Post a comment