Divisors of triangle numbers (Euler 12)

Question

I have found a couple of topics related to this very problem, I just want to know why my code returns incorrect data. So we have to find the first triangle number having more than 500 divisors. Details can be found here: http://projecteuler.net/problem=12 And here is my code:

Int64 triangularnum = 1;
            for (Int64 num = 2; num > 0; num++)
            {
                if(has501Divisors(triangularnum))
                {
                    MessageBox.Show(triangularnum.ToString());
                    break;
                }
                triangularnum += num;
            }



private bool has501Divisors(Int64 candidate)
        {
            bool has501 = false;
            int count = 0;
            for (int i = 1; i < Math.Sqrt(candidate); i++)
            {
                if (candidate % i == 0) count += 1;
                if (count > 501)
                {
                    return true;
                }
            }
            return has501;
        }

This gives me number 842161320 which is apparently incorrect.

Instead of writing a method "Has501Divisors", you could have written a method called "CountDivisors". By testing and debugging that method on small numbers you'd quickly find out that you made a mistake and were under-counting the divisors. Learning how to effectively break problems down into testable subsystems is a skill that will serve you well in the future. — Eric Lippert, Aug 22 '13 at 14:57

score 3 · Accepted Answer · answered Aug 22 '13 at 14:49

You should increment your count number by 2 not 1.

Also your

if (count > 501)

part is incorrect because your boundary should 500 not 501. Change it to count > 500 instead of.

static void Main(string[] args)
{
    Console.WriteLine(Find());
}

public static int Find()
{
    int number = 0;
    for (int i = 1; ; i++)
    {
        number += i; // number is triangle number i
        if (CountDivisorsOfNumber(number) > 500)
            return number;
    }
}


private static int CountDivisorsOfNumber(int number)
{
     int count = 0;
     int end = (int)Math.Sqrt(number);
     for (int i = 1; i < end; i++)
     {
         if (number % i == 0)
             count += 2;
     }
     if (end * end == number) // Perfect square
         count++;
     return count;
}

This prints 76576500 and looks like a right solution.

score 2 · Answer 2 · answered Aug 22 '13 at 14:50

2

The problem is you are limiting your loop to the square root, which is smart, however that means you need to increment your count by two, not by 1 to account for both divisors.

Change your incrementation to this:

if (candidate % i == 0) count += 2;

Additionally, your count check checks for greater than 501 divisors, not 500.

answered Aug 22 '13 at 14:50

vcsjones

138,677
31
291
286

Ohh. Thanks, I'm quite blind. – fishmong3r Aug 22 '13 at 14:54
3

@fishmong3r: Also, what if the number is a square triangular number? Suppose you are counting the divisors of 36, which is both square and triangular. Your program counts 1, 2, 3 and 4, and skips 6, 9, 12, 18 and 36. vcsjones' suggestion of incrementing by two doesn't give you the correct answer here; the correct answer is 9 but the suggested program gives you 8. – Eric Lippert Aug 22 '13 at 15:01
2

Ah, quite right. Soner Gönül's answer does cover how to correctly handle that. It works by luck that the correct result is not a square. – vcsjones Aug 22 '13 at 15:07

score -1 · Answer 3 · edited Aug 23 '13 at 06:36

-1

Quick look but your check isn't ok:

if (count > 501)

This will stop at count 502, not 501.

for (int i = 1; i < Math.Sqrt(candidate); i++)

9 is divisible by 3, so you should use <= here. Also, you're divising by 1, you should start at i = 2.

edited Aug 23 '13 at 06:36

Soner Gönül

97,193
102
206
364

answered Aug 22 '13 at 14:49

Carra

17,808
7
62
75

2

Is 1 not a divisor? It seems to meet the definition of a divisor. – Eric Lippert Aug 22 '13 at 14:58
1

It is a trivial divisor but it's being used in the example so yes, you're right. – Carra Aug 23 '13 at 07:02

Divisors of triangle numbers (Euler 12)

3 Answers3