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

One of the big topics in number theory – Prime factorization – is once again the topic of a Project Euler problem. Problem 47 reads

The first two consecutive numbers to have two distinct prime factors are:

14 = 2 x 7
15 = 3 x 5

The first three consecutive numbers to have three distinct prime factors are:

644 = 2² x 7 x 23
645 = 3 x 5 x 43
646 = 2 x 17 x 19.

Find the first four consecutive integers to have four distinct primes factors. What is the first of these numbers?

I would love to say that I have found some clever way to approach this problem, but the fact is that I haven’t. The only solution I have found is to brute force it.  I have made a modified version of the factorization algorithm to return the number of distinct prime factors for a number. In C# this looks like

private int NumberOfPrimeFacors(int number) {
    int nod = 0;
    bool pf;
    int remain = number;

    for (int i = 0; i < primeList.Length; i++) {
        // In case there is a remainder this is a prime factor as well
        // The exponent of that factor is 1
        if (primeList[i] * primeList[i] > number) {
            return ++nod;
        }

        pf = false;
        while (remain % primeList[i] == 0) {
            pf = true;
            remain = remain / primeList[i];
        }
        if (pf){
            nod++;
        }

        //If there is no remainder, return the count
        if (remain == 1) {
            return nod;
        }
    }
    return nod;
}

Once we have that function it is fairly simple to make a loop that looks for a number of consecutive integers with this number of distinct prime factors. My code looks like

primeList = ESieve(100000);
int targetpf = 4;
int targetConsec = 4;
int consec = 1;
int result = 2 * 3 * 5 *7;

while (consec < targetConsec) {
    result++;
    if (NumberOfPrimeFacors(result) >= targetpf) {
        consec++;
    } else {
        consec = 0;
    }
}

This algorithm will store the last of the 4 prime integers in result, and then it is trivial to find the first. The result of running the code is

The first of the 4 consecutive integers to have
4 distinct prime factors is 134043
Solution took 40 ms

Wrapping up

I have made a simple lower bound of 235*7 = 210, which I know must be the lower bound, since this is the 4 smallest primes. I am pretty sure that we could tighten this bound significantly if we wanted to, but I haven’t found a way to do this.

As usual the source code is available. Comments, questions and/or other solutions are as always welcome.

The nice headline image of prime numbers is taken by chrisinplymouth who has granted the use through the creative commons license. My alteration of the photo is of cause shared under the same license.

Posted by Kristian

19 comments

how to find the number of numbers in range 2,10000 whose distinct primes factors is 5?

I am not sure what you mean? Do you mean numbers that only have 5 as a prime factor, or do you mean numbers with 5 prime different prime factors?

After failing miserably at the brute force solution (time related problem), I managed to finally find a nice solution.


def count_divisors(n):
"""
Count the prime divisors for all the numbers below n
"""
div = [0] * n
for i in xrange(2, n):
if div[i] == 0:
yield i, 1 # prime number
for j in xrange(i, n, i):
div[j] += 1 # add divisor to all multiples
else:
yield i, div[i]

N = 4 # N consecutive numbers with N divisors
prev = deque([0] * N) # hold the last N divisor counts
for number, divisors in count_divisors(10 ** 6): # started with 3, and added 0s until I found the result
prev.popleft()
prev.append(divisors)
if sum(prev) == N ** 2:
print "First number in sequence: %d" % (number - N + 1)
break

0.36 seconds in Python 2.7.5

Sorry, I forgot to add formatting.

def count_divisors(n):
    """
    Count the prime divisors for all the numbers below n
    """
    div = [0] * n
    for i in xrange(2, n):
        if div[i] == 0:
            yield i, 1  # prime number
            for j in xrange(i, n, i):
                div[j] += 1  # add divisor to all multiples
        else:
            yield i, div[i]

N = 4  # N consecutive numbers with N divisors
prev = deque([0] * N) # hold the last N divisor counts
for number, divisors in count_divisors(10 ** 6): # started with 3, and added 0s until I found the result
    prev.popleft()
    prev.append(divisors)
    if sum(prev) == N ** 2:
        print "First number in sequence: %d" % (number - N + 1)
    break

Vlad, can u post all the code pls?

prev = deque([0] * N) # hold the last N divisor counts
NameError: name 'deque' is not defined

The missing code is a python import


from collections import deque

2 ms.
Back to basics, something like:
“My first sieve of Eratosthenes”.

Started with : 0 1 2 3 4 5 6 7 8 9
Crossed off? 0 0 0 0 1 0 2 0 1 1

using System;
using System.Diagnostics;
class E47
{
    static void Main()
    {
        var sw = new Stopwatch();
        sw.Start();
        uint max = 150000;
        uint[] n = new uint[max + 1];
        uint i, j;
        for (i = 2; i <= max / 2; i++)
        {
            j = i;
            if (n[j] == 0) for (j += i; j <= max; j += i) n[j]++;
        }
        i = 1000; j = 0;
        for (i = 1000; i <= max && j < 4; i++)
        {
            if (n[i] == 4) j++;
            else j = 0;
        }
        sw.Stop();
        Console.WriteLine(sw.ElapsedMilliseconds + " ms");
        if(j>=4)for (j = i - j; j < i; j++) Console.WriteLine(j);
        else Console.WriteLine("No Solution, increase max");
        Console.ReadLine();
    }
}

Why is NumberOfPrimeFacors() more complicated than simply checking divisibility, like so?

for p in primes:
  if n % p == 0:
    nod += 1
return nod

Why go through the trouble of dividing and keeping a remainder, etc?

I am not sure, maybe it isn’t needed.

Jean-Marie Hachey

Table 1
Two series of first consecutive numbers to have the same number of distinct prime factors.

http://img4.hostingpics.net/pics/505868pe47tab1dpfact.jpg

___

Table 2
Five series of first consecutive numbers having the same number of distinct prime factors.

http://img4.hostingpics.net/pics/633957pe47tab2dpfact.jpg

______

Sources:

1) Kristian’s algorithm for Project Euler – Problem 47
http://www.mathblog.dk/files/euler/Problem47.cs
2) 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.
https://oeis.org/A075044
3) Prime Factorization Calculator
http://www.mathblog.dk/tools/prime-factorization/
4) Microsoft Visual C# 2010 Express
5) Microsoft Office Excel (2007)

Jean-Marie Hachey

Table 1
Series of first consecutive integers to have distinct primes factors.

http://img4.hostingpics.net/pics/553771pe47tab1distf.jpg

Results of Table 1 were calculated using P_P’s algo in the comment above.
(Posted on January 31, 2014 at 15:03).
In Table 1, we can see that all the expected results are obtained.
However, the next result (626 804 494 291) cannot be reached.
I tried to get it by replacing uint by ulong with no success yet.

Arnaud Amiel

I am currently playing with the Julia language and going through the project Euler problems again. I used to like checking others answers on the site but now I am checking this blog.

I have brute forced this one too but as it was a bit slow (> 1s) I tried to speed it up. The simple way I found is to step not one number at a time but 4 and check around if you find a candidate. I got a >8 times speed increase here.

For interest, I copy my code below:

function solve047()

const inArow = 4

result = 0
solution = false

#Start our testing with the product of the first inArow primes
test = prod(primes(iceil(inArow*(log(inArow)+log(log(inArow)))))[1:inArow])

while !solution

#Use steps of inArow to find the right number of factors
while length(factor(test)) != inArow
test += inArow
end

howMany = 0

#Look for inArow factors around our candidate
for i = -(inArow-1):(inArow-1)

if length(factor(test+i)) == inArow
howMany += 1
else
howMany = 0
end

#Do we have a solution yet?
if howMany == inArow
solution = true
result = test + i – (inArow – 1)
end

end

#Try again inArow further
test += inArow

end

#We got there in the end
result

end

Thanks for your blog, it regularly gives me some good insights as to what I could have done better.

While my python is quite slow with the brute force, I was wondering about if you instead of only increase the result with only one but better yet, jump over it. I mean, start with 13, 14 are the two conscecutive then it must mean 15 is not. There for the next iteration should start with 16 and not 14.

Jonathan de La Marche

@mat10tng:
You can’t make jumps, because there could be 3, 4 or even more consecutive numbers that fulfill the condition.
For example:
33 = 3 * 11
34 = 2 * 17
35 = 5 * 7
36 = 2^2 * 3^3

Here is my solution. I did not use a prime list and the solution took me 15 ms.

int checkNr = 209; // 2*3*5*7 = 210 -> -1 because the number will be increased by one before we check it.
int tmpNr = checkNr;
int primeFactor = 0;
int factorCount = 0;
int matchCount = 0;
int i = 0;

// Loop until we have four following numbers and each of it has
// four distinct prime factors.
while(matchCount < 4){
checkNr++;
tmpNr = checkNr;
primeFactor = 0;
i = 2; // 2 is the lowest possible prime factor
factorCount = 0;

/*
* Each consecutive number has minimum one prime factor that is lower or equal to the
* square root of the number.
*
* All multiples of a prime will be excluded before they will be reached.
*/
while((i*i) primeFactor){
//The remainder is the largest prime factor.
primeFactor = tmpNr;
factorCount++;
}

// We need 4 matches so if a number has 4 distinct prime factors
// increase the number of matches. Otherwise reset it to 0.
matchCount = factorCount == 4 ? matchCount + 1 : 0;
}

// The searched number is the fourth in the row minus three which is the first in the row.
System.out.println(“Number is ” + (checkNr-3));

Mh, a piece of code was cut of, sorry.

int checkNr = 209; // 2*3*5*7 = 210 -> -1 because the number will be increased by one before we check it.
int tmpNr = checkNr;
int primeFactor = 0;
int factorCount = 0;
int matchCount = 0;
int i = 0;

// Loop until we have four following numbers and each of it has
// four distinct prime factors.
while(matchCount < 4){
checkNr++;
tmpNr = checkNr;
primeFactor = 0;
i = 2; // 2 is the lowest possible prime factor
factorCount = 0;

/*
* Each consecutive number has minimum one prime factor that is lower or equal to the
* square root of the number.
*
* All multiples of a prime will be excluded before they will be reached.
*/
while((i*i) primeFactor){
//The remainder is the largest prime factor.
primeFactor = tmpNr;
factorCount++;
}

// We need 4 matches so if a number has 4 distinct prime factors
// increase the number of matches. Otherwise reset it to 0.
matchCount = factorCount == 4 ? matchCount + 1 : 0;
}

// The searched number is the fourth in the row minus three which is the first in the row.
this.appendMsgln(“Number is ” + (checkNr-3));

Ok, I give up. The code has been cut off again…

Hi!

I was looking at the code for

private int NumberOfPrimeFactors(int number)

Can you check the logic by tracing through the code for number = 28? The remainder when primeList reaches 7 is 14. How can this be a prime factor?

Thanks,
VK

Leave a Reply