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

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

Written by on 11 June 2011

Topics: Project Euler

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 2*3*5*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.

18 Comments For This Post I'd Love to Hear Yours!

  1. vidi says:

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

  2. Kristian says:

    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?

  3. Vlad says:

    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

  4. Vlad says:

    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
  5. luca says:

    Vlad, can u post all the code pls?

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

  6. Vlad says:

    The missing code is a python import


    from collections import deque

  7. P_P says:

    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();
        }
    }
    
  8. Rodrigo says:

    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?

  9. Kristian says:

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

  10. Jean-Marie Hachey says:

    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)

  11. Jean-Marie Hachey says:

    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.

  12. Arnaud Amiel says:

    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.

  13. mat10tng says:

    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.

  14. Jonathan de La Marche says:

    @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

  15. Julian says:

    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));

  16. Julian says:

    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));

  17. Julian says:

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

  18. vk says:

    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

Trackbacks For This Post

  1. Novel by Numbers | The Expressible Café

Leave a Comment Here's Your Chance to Be Heard!

You can use these html tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

You can use short tags like: [code language="language"][/code]

The code tag supports the following languages: as3, bash, coldfusion, c, cpp, csharp, css, delphi, diff,erlang, groovy, javascript, java, javafx, perl, php, plain, powershell, python, ruby, scala, sql, tex, vb, xml

You can use [latex]your formula[/latex] if you want to format something using latex

This site uses cookies.