Project Euler problem 12

Question

The statement is as follows :

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,28

We 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?

My implementation :

import java.util.ArrayList;
import java.util.HashMap;
public class Euler_12{

    // This function finds the prime factorization
    // of a given number
    public static int getDivisors(int number){
        ArrayList<Integer> list = new ArrayList<Integer>();
        while(number%2==0){
            list.add(2);
            number/=2;
        }

        for(int i = 3; i<=Math.sqrt(number); i++){
            while(number%i==0){
                list.add(i);
                number/=i;
            }
        }

        if(number>2){
            list.add(number);
        }

        return findDivisors(list);
    }

    // Uses HashMap to convert multiples in form of
    // 2 2 2 2 4 4 to 2^4 x 4^2
    public static int findDivisors(ArrayList<Integer> list){
        int result = 1;
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        for(int i : list){
            if(map.containsKey(i))
                map.put(i, map.get(i)+1);
            else 
                map.put(i, 1);

        }

        // Better take a look at [1]
        // on why I did this
        for(int i : map.keySet()){
            result = result * (map.get(i) + 1);
        }

        // the result is number of divisors
        return result;
    }

    public static int number = 0;
    public static int sequence = 1;
    // Returns the next Triangular number 
    public static int nextTraingularNumber(){
        int temp = number + sequence;
        number = temp;
        sequence++;
        return temp;
    }
    public static void main(String[] args) {
        while(true){
            int i = nextTraingularNumber();
            if(getDivisors(i)>500){
                System.out.println("Found : " + i);
                break;
            }
        }
    }
}

It finds the answer in 0.812 seconds. Looking for improvements, suggestions are welcomed

Answer 1

The \$n\$th triangular number is equal to \$n(n+1)/2\$, which can be factored as \$(n/2)(n+1)\$ or \$n((n+1)/2)\$ depending on whether \$n\$ is even or odd. In either case the two factors are relatively prime, so the number of divisors can be computed as the product of the number of divisors of each factor, which is much faster to run through your getDivisors function.

There are also much more efficient ways to compute the number of divisors: sieving allows you to compute this over a contiguous range of \$n\$ values simultaneously much faster than doing each one individually. Even for individual \$n\$, factoring-based methods will be tend to be faster than systematically trying all divisors up to \$\sqrt{n}\$.

Answer 2

Your code has the right rationale for finding the number of divisors.

Several remarks:

• The improvement that you can make is that you don't need to explicitly make a List<Integer> of all the prime factors and then post-process that list in findDivisors to find the number of divisors. You can merge those two process in a single method by directly adding the prime factors into the final map instead of adding them to a temporary list.

• Prefer to code against interfaces. Instead of

  HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
  

  you should have

  Map<Integer, Integer> map = new HashMap<Integer, Integer>();
  

• The following for loop

  for(int i : map.keySet()){
      result = result * (map.get(i) + 1);
  }
  

  can be written more simply and more effectively by iterating over the values directly:

  for (Integer v : map.values()) {
      result = result * (v + 1);
  }
  

Answer 3

Duplicated logic

In

    while(number%2==0){
        list.add(2);
        number/=2;
    }

    for(int i = 3; i<=Math.sqrt(number); i++){
        while(number%i==0){
            list.add(i);
            number/=i;
        }
    }

you are doing the same thing twice, once with 2, once with i. It's better to just start your loop at 2.

Optimisation

As said in other answers, you could replace Math.sqrt by multiplications.

Making intent clearer

The check if(number>2){ is actually to avoid 1 in the list of divisors. It would be more explicit to write it if(number>1){ (the case 'number == 2' cannot happen anyway as far as I can tell).

Typo

nextTraingularNumber ? :(

Pure function

Instead of having nextTriangularNumber relying on side effects, it might be clearer to define a pure function taking a number and returning the corresponding triangular number.

public static int triangularNumber(int n) {
    return n * (n+1) / 2;
}


public static void main(String[] args) {
    for (int i = 0; ; i++){
        int t = triangularNumber(i);
        if(getDivisors(t)>500){
            System.out.println("Found : " + t);
            break;
        }
    }
}

Answer 4

The getDivisors method should probably be called getNumberOfDivisors.

I don't think your nextTraingularNumber helps very much in terms of clarity - I would keep it simple and leave the logic in the main loop.

You could also use the for loop fully and put your condition on the number of divisors as the condition of the loop instead of breaking.

The main method could look like this (and no more need for the nextTriangularNumber method):

public static void main(String[] args) {
  long triangle = 0;
  for (long i = 1; getNumberOfDivisors(triangle) < 500; i++) {
    triangle += i;
  }
  System.out.println(triangle);
}

which is more compact (7 vs 18 lines) and I think also clearer (fewer lines of code to read => fewer lines to understand).

Answer 5

I would suggest following just about any style guide (but let's say particularly Oracle's) when it comes to white space. For example, the following for loop is far too difficult to read at a glance:

for(int i = 3; i<=Math.sqrt(number); i++){
    while(number%i==0){
        list.add(i);
        number/=i;
    }
}

You should put spaces between operators and punctuation used syntactically. One general exception might be no space between increment and decrement operators, ++ and --. I would write it as:

for (int i = 3; i <= Math.sqrt(number); i++) {
    while (number % i == 0) {
        list.add(i);
        number /= i;
    }
}

The most important thing is to be consistent. You had essentially zero spaces in your for loop, but you use them here:

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

Having white space between variables, operators, syntactic punctuation ((, {, ;, etc.) makes reading your code (at least in my opinion) a million times easier.