Project Euler 12 – Revisited

Written by on 14 May 2011

Topics: Project Euler

A while ago I treated Problem 12 of Project Euler and came up with several solutions as seen here.

Lets just repeat the problem here

The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, …

Let us list the factors of the first seven triangle numbers:

1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28We can see that 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?

In relation to that post Nazia asked me if the code would scale, and that made me realise that the current implementation of the function for calculating the number of divisors is dependent on the prime array that I used to be large enough. If this isn’t the case the calculated number of divisors may very well be wrong. Besides that, using integers limits the solution to numbers less than approximately 2.7 billion.

Changing variables to longs or even ulongs would push the problem a bit, but it wasn’t enough. We still need to allow the prime list to grow if we succeeded the limit. Therefore I revised the code to be more scalable.

Lets start out with the main function which isn’t changed that much. I have changed the prime list from an array to a list and put it as a class property instead of a local variable, so we don’t have to pass it around. The C# code looks like

BigInteger number = 1;
BigInteger i = 2;
long cnt = 0;
long Dn1 = 2;
long Dn = 2;
primeList = ESieve(4000000);
long limit = 10000;

while (cnt < limit) {
    if (i % 2 == 0) {
        Dn = PrimeFactorisationNoD(i + 1);
        cnt = Dn * Dn1;
    } else {
        Dn1 = PrimeFactorisationNoD((i + 1) / 2);
        cnt = Dn * Dn1;
    }
    i++;
}
number = i * (i - 1) / 2;

Besides the prime list I am using a mix of longs and BigIntegers to get something scalable. I want to be able to extend the prime list, but since the Sieve method is really efficient I use it to start the list with. The method for finding the number of divisors has also been changed slightly. Some of the variables has been changed to accommodate larger numbers, and the there is an added section that checks if there are sufficient prime numbers to ensure that we find all of divisors of the number.

private long PrimeFactorisationNoD(BigInteger number) {
    long nod = 1;
    long exponent;
    BigInteger remain = number;
    while (number >= primeList[primeList.Count-1] * primeList[primeList.Count-1]) {
        generateNewPrime();
    }

    for (int i = 0; i < primeList.Count; 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 * 2;
        }

        exponent = 1;
        while (remain % primeList[i] == 0) {
            exponent++;
            remain = remain / primeList[i];
        }
        nod *= exponent;

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

All we need now is a method for generating more primes, in this case I took the function from problem 5 and revised it to be based on BigIntegers.

public void generateNewPrime() {
    bool isPrime = false;
    BigInteger i = primeList[primeList.Count - 1];

    while(!isPrime){
        int j = 0;
        i += 2;
        isPrime = true;
        while (primeList[j] * primeList[j] <= i) {
            if (i % primeList[j] == 0) {
                isPrime = false;
                break;
            }
            j++;
        }
        if (isPrime) {
            primeList.Add(i);
            return;
        }
    }
}

I think we have covered all necessary parts to make the algorithm scale better. Unfortunately these changes means a performance hit. I think the major issue here is the change to BigInteger.

The limiting factor now, is that the prime list can hold 2.7 billion primes. So with the co prime factorisation, which means primes up to 64.373.242.723 and thus we can handle number in the range of 1042. That should be enough for all practical purposes.

Remember that this is only triangle numbers we are dealing with here.

Wrapping up

Thanks to Nazia for asking the question. I would have answered you in the comments, but I needed a bit longer post to explain some thoughts I had. I hope the code enlightened you in one way or another.

The source code is available here.

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

  1. Nazia says:

    Thanks a ton Kristian.. appreciate it… just glanced thru the code.. have not yet run it.
    coming to the performance hit that you mentioned, i do believe arrays to be faster than lists plus the new method “generateNewPrime” which would add new primes will increase the execution time. rest looks good. thanks again…

  2. Nazia says:

    ran both the versions of the code. The “generateNewPrime” method is killing the execution time…
    i set the upper limit to 1000 in both the cases
    with the old code it takes approx 66 secs to find a triangle num with over 12000 divs…
    with the new version it takes 5mins.. thats huge..
    the result is the same, is there any way we can further optimize generateNewPrime() ?

  3. Kristian says:

    I have tried to remove the GenerateNewPrime() from the code and test it with a small example of 500 or 1000 divisors, and there is still a huge performance degrade.

    Instead of finding the exact cause I will encourage you to look into that. It is likely one of the two reasons

    1. We are using BigInteger which is not an integral type
    2. We are using a List instead of an integer array to store the prime list

    Play around with the code, see what you come up with, and please let us know what you figure out. It would be pretty interesting to see what it is that causes the result.

    /Kristian

  4. Nazia says:

    sure… will let you know…

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.