GDC Project Euler: problem 12 – Jaroslaw Pawlak

  • Difficulty: rather easy

  • First solution:

There are no many solutions to the problem. Main looks as follows:

int i = 0;
int number = 0;
while (numberOfDivisors(number += ++i) <= 500) {}
// number here is the answer

The only possible changes may be in numberOfDivisors(int number). My first implementation (when I just wanted to make it work) was a simple brute solution:

int result = 0;
for (int i = 1; i <= number; i++) {

if (number % i == 0) {

result++

}

}
return result;

  • Techniques used:

Java program with my own implementation of divisors counter algorithm.

  • How much time did it take:

First solution has been written in about ten minutes. Answer then was found in 20 minutes. Final solution was implemented in about 50 minutes and answer was found in 115ms.

The algorithm used above was incredibly inefficient. I have come up with an idea to use a formula which calculates the number of divisors from the a1^b1 * a2^b2 * … * an^bn form of a number, where ‘a’ are prime. I have implemented my own structure for this purpose. I have writing it in Java and used two ArrayLists of Integers – one with prime numbers, the other one with exponents. At the startup, list of prime numbers contains only 2. New prime numbers are generated only if necessary (i.e. some number greater than 1 is not divisible by any of current prime numbers). I have used the following solution for prime number finding. Sieve of Eratosthenes could work faster but would require to specify a size of a list in advance, while this solution does it dynamically, depends or program requirements. I have also used this structure for other Project Euler problems.

private static ArrayList<Integer> prime

= new ArrayList<Integer>();

private static void addNew() {

for (int i = getBiggest() + 1;; i++) {

if (!isDivisible(i)) {

prime.add(i);
break;

}

}

}
private static int getBiggest() {

return prime.get(prime.size() – 1);

}
private static boolean isDivisible(int number) {

for (int i = 0; i < prime.size(); i++) {

if (number % prime.get(i) == 0) {

return true;

}

}
return false;

}

In case of accessing i’th prime number, if i >= prime.size(),
then addNew() must be invoked i – prime.size() times + 1.

private static ArrayList<Integer> exp

= new ArrayList<Integer>();

private static int numberOfDivisors(int number) {

exp.clear();
for (int i = 0; i < prime.size();) {

exp.add(0);
while (number % prime.get(i) == 0) {

exp.set(i, exp.get(i) + 1);
number /= prime.get(i);

}

i++;
if (number == 1) {

break;

}
if (prime.size() == i) {

addNew();

}

}

int result = 1;
for (int i = 0; i < exp.size(); i++) {

result *= exp.get(i) + 1;

}

return result;

}

I think that this approach may be further optimized (anyway 19 minutes into 115ms is a nice progress, isn’t it? ;) ). For example exp array list is not necessary, it could be exchanged by simple integer representing current exponent. Before taking next exponent from the list, result had to be changed.

  • Problems encountered:

The answer was too big and the simplest brute solution was unable to find it in a reasonable time. More efficient implementation of finding the number of divisors had to be implemented.

  • What I have learned:

Although, brute solutions are much faster to implement, it must be considered how big numbers they will be used for. In some cases it may be a waste of time to implement an efficient (faster but longer and more difficult to understand) solution if calculation time would change from e.g. 300 to 100 nanoseconds. In other cases, optimizations are necessary, especially if using a large amount of division in a computer program (which is quite slow operation). Writing a more efficient solution may sometimes also make it more universal (as it happened in this case) which allows code re-usage. On the other hand, universal solution can make computations much slower and dedicated solution may be necessary – I will describe this problem further in my solution to the problem 191.

About Jaroslaw Pawlak

I have done MSci in Computer Science at King’s College London and currently work as Software Engineer specialising in Java. I spend most of my time in front of computer improving my programming (and other) skills or just relaxing with a good game. I also train some sports but at the moment I am not a member of any club. I love cycling and volleyball, but I have also played a lot of football, tennis and trained martial arts.

Posted on June 9, 2011, in GDC Project Euler Challenge, Project Euler. Bookmark the permalink. 2 Comments.

  1. can somebody make it simpler i dont understand and im really stuck on question 12

  2. Assume you have a method numberOfDivisors(int number), which returns a total number of divisors of given number. You have to invoke this method with numbers 1, 3, 6, 10, 15, 21, 28 and so on, until method returns at least 500.

    n’th triangle number is expressed by the formula (1+n)*n/2. It is not necessary but you may find it useful.

    In this problem, any implementation of numberOfDivisors(int) method works (brute one finds an answer in less than 30 minutes on Intel 5 CPU). What I have used is more complex but also more efficient and uses prime factorization (http://en.wikipedia.org/wiki/Prime_factor):
    If you already have a number written as prime factorization, e.g. 1350 = 2 * 3^3 * 5^2, the total number of its divisors is multiplication of exponents increased by one, i.e. (1+1) * (3+1) * (2+1) = 2 * 4 * 3 = 24.

    https://github.com/Jarcionek/Project-Euler/blob/master/src/utilities/Prime.java – have a look here for some code often used in Project Euler ;) If you still had any doubts, let me know.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: