4
\$\begingroup\$

Project Euler Problem 12 asks to find the value of the first triangular number to have over 500 divisors, where the \$n\$th triangular number is \$\sum_{i=1}^{n} i\$.

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.

I have the following code written in C#. I never had the patience to wait for the program to finish but the code shows the right answer because I tried the example on their website. My code has a very long runtime and I don't know what to do to optimize it. I've waited for like 5-6 minutes on a AMD 4x cores 3.10 GHz and nothing...

static void Main(string[] args) {

        Stopwatch time = new Stopwatch();
        time.Start();

        int trianglenumber = 0;
        int divizori = 0;

            for (int i = 1; i < Int32.MaxValue; i++) {
                int tempnumber = 0;
                for (int j = 1; j < i; j++) {
                    tempnumber += j;
                }
                for (int k = 1; k < tempnumber+1; k++) {
                    if (tempnumber % k == 0) {
                        divizori++;
                    }
                }
                if (5 < divizori) {
                    trianglenumber = tempnumber;
                    break;
                }
                divizori = 0;
            }

            time.Stop();

            double timp = time.ElapsedMilliseconds ;

            Console.WriteLine(trianglenumber);
            Console.Write("Runtime: " + timp/1000+ " seconds");
            Console.ReadKey();


    }
\$\endgroup\$
  • 1
    \$\begingroup\$ Also, there are faster ways to sum a series than iteration. \$\endgroup\$ – RubberDuck Aug 17 '14 at 12:33
  • \$\begingroup\$ What the purpose of the test i < Int32.MaxValue ? \$\endgroup\$ – Emanuele Paolini Aug 17 '14 at 12:57
  • \$\begingroup\$ Emanuele I don't know the limit so I use the maxvalue of the int32. I used 130 divisors. With this code I got 2.33 seconds. Installed a isPrime method and if the number is prime, skip it. Got 1.185 seconds on 130 divisors. \$\endgroup\$ – cacatpisatmazga Aug 17 '14 at 12:58
  • 1
    \$\begingroup\$ The entire point of the Euler problems is that you should figure them out, not have other people figure them out for you. \$\endgroup\$ – Guffa Aug 17 '14 at 16:00
  • \$\begingroup\$ @Guffa I would have thought that the purpose is to learn, which is probably better with help. As long as people explain why doing it one way is better than another then it's okay in my opinion. \$\endgroup\$ – craftworkgames Aug 18 '14 at 22:47
2
\$\begingroup\$

You should change your algorithm. First note that triangle numbers can be written as: \$ T_n = \frac{n(n+1)}{2} \$ then notice that \$n\$ and \$n+1\$ cannot share a common divisor. So you can find all the divisors of \$T_n\$ just by finding the divisors of \$n\$ and \$n+1\$ (and removing a factor 2) and multiplying them together. This alone should greatly improve your algorithm turning it (the part inside the main loop) from \$O(n^2)\$ to \$O(n)\$.

Then you could make a table of prime number to quickly find the factorization of \$n\$ and \$n+1\$. Once you know the prime factors of \$n\$ you can find the number of all divisors of \$n\$. See, for example, here: http://www.marksmath.com/math/problems/count-div.html

addendum

First advice is actually enough. Here is the code (I don't know C#, hope it compiles):

static int count_divisors(int n) {
  int count = 0;
  for (int k=1;k<=n;++k) {
    // this loop can be reduced further by noticing that
    // apart from n itself there is no divisor with k*2>n
    if (n % k == 0) count++;
  }
  return count;
}

static void Main(string[] args) {
  int last_d = 0; // cache the computation for previous n
  for (int n=0;;++n) {
    int triangular = n*(n+1)/2; // only used for debugging and clarity
    int d; // number of divisors of (n+1) (or (n+1)/2 if (n+1) is even)
    if (n%2==0)
      d = count_divisors(n+1);
    else
      d = count_divisors((n+1)/2); // n+1 is even                               
    // # of divisors of n * (n+1)/2 is the product of divisors
    // since two consecutive numbers do not share any divisor (apart from 1)
    int total = d*last_d;
    if (total>500) {
      Console.WriteLine("found: " + triangular);
      break;
    }
    last_d = d; // cache the computation
  }
}
\$\endgroup\$
  • \$\begingroup\$ I didn't get the part from " So you can find all the divisors of Tn just by finding the divisors of n and n+1 (and removing a factor 2). This alone should greatly improve you.... " \$\endgroup\$ – cacatpisatmazga Aug 17 '14 at 13:45
  • \$\begingroup\$ made this: pastebin.com/RmQWJEb4 , guess what, even slower \$\endgroup\$ – cacatpisatmazga Aug 17 '14 at 13:57
  • \$\begingroup\$ I have added the code. Gives 76576500 as solution. \$\endgroup\$ – Emanuele Paolini Aug 17 '14 at 14:29
  • 1
    \$\begingroup\$ Why are you answering a C# question with C code?? No they are nowhere near similar enough for this sort of thing. \$\endgroup\$ – Vogel612 Aug 17 '14 at 14:50
  • \$\begingroup\$ Yeah, C is very different from C#... Thanks for trying to answering me tho'. \$\endgroup\$ – cacatpisatmazga Aug 17 '14 at 14:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.