Euler Problem 12

The sequence of triangle numbers is generated by adding the natural numbers. So the 7^(th) 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?

Dumb. Dumb. Dumb. Yes — me. 

This one has me stressed out for a couple days with headaches, trying to understand fancy algorithms like Elliptical Curve factorization because simple concepts like Trial Division were taking FOR-E-VER. I was submitting solution after solution (playing with primes) and failing each time. But the answer was staring me right in the face.

To quote Wiki: … the trial factors need go no further than \scriptstyle\sqrt{n} because, if n is divisible by some number p, then n = p×q and if q were smaller than p, n would have earlier been detected as being divisible by q or a prime factor of q.

Cool, now my Trial Division was friggin’ fast, but then why was I still missing factors above root n?

I solved it by looking at a simple example: The factors of 36, which is a triangle number. Based on the above comment I would only have to iterate to 6. But how do I catch factors like 9 & 18? Because in addition to each factor found under root 6, the remainder of dividing 36 by that factor is also a factor! Duh!

import java.util.ArrayList;

public class Euler12
{
    public static void main(String[] args)
    {
        System.out.print(“Problem 12:\n”);
        Euler12 e = new Euler12();
        System.out.print(“Answer = ” + e.Problem()+ “\n”);
    }
    public String Problem ()
    {
        ArrayList<Long> factors = new ArrayList<Long>();
        int max = 0;
        long answer = 0;
        for (int i = 1; i <= 20000; i++)
        {
            long sum = 0;
            for (int n = 1; n <= i; n++)
            {
                sum += n;
            }
            factors.clear();
            factors.add(1L);
            factors.add(sum);
            for (int n = 2; n <= Math.ceil(Math.sqrt(sum)); n++)
            {
                if (sum % n == 0 && factors.contains((long)n) == false)
                {
                    factors.add((long)n);
                    if (factors.contains((long)sum/n) == false)
                    {
                        factors.add((long)sum/n);
                    }
                }
            }
            if (factors.size() > max)
            {
                max = factors.size();
            }
            System.out.print(“i:tri:fac:max “+i+”:”+sum+”:”+factors.size()+”:”+max+”\n”);
            if (max > 500)
            {
                answer = sum;
                break;
            }
        }
        return String.valueOf(answer);
    }
}

 

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 )

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