views:

828

answers:

8

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.

Given an integer n, display the first triangle number having at least n divisors.

Sample Input: 5

Output 28

Input Constraints: 1<=n<=320

I was obviously able to do this question, but I used a naive algorithm:

  1. Get n.

  2. Find triangle numbers and check their number of factors using the mod operator.

But the challenge was to show the output within 4 seconds of input. On high inputs like 190 and above it took almost 15-16 seconds. Then I tried to put the triangle numbers and their number of factors in a 2d array first and then get the input from the user and search the array. But somehow I couldn't do it: I got a lot of processor faults. Please try doing it with this method and paste the code. Or if there are any better ways, please tell me.

+3  A: 

Well, you don't go into a lot of detail about what you did, but I can give you an optimization that can be used, if you didn't think of it...

If you're using the straightforward method of trying to find factors of a number n, by using the mod operator, you don't need to check all the numbers < n. That obviously would take n comparisons...you can just go up to floor(sqrt(n)). For each factor you find, just divide n by that number, and you'll get the conjugate value, and not need to find it manually.

For example: say n is 15.

We loop, and try 1 first. Yep, the mod checks out, so it's a factor. We divide n by the factor to get the conjugate value, so we do (15 / 1) = 15...so 15 is a factor.

We try 2 next. Nope. Then 3. Yep, which also gives us (15 / 3) = 5.

And we're done, because 4 is > floor(sqrt(n)). Quick!

If you didn't think of it, that might be something you could leverage to improve your times...overall you go from O(n) to O(sqrt (n)) which is pretty good (though for numbers this small, constants may still weigh heavily.)

Beska
+3  A: 

I was in a programming competition way back in school where there was some similar question with a run time limit. the team that "solved" it did as follows:

1) solve it with a brute force slow method.
2) write a program to just print out the answer (you found using the slow method), which will run sub second.

I thought this was bogus, but they won.

KM
I was going to suggest this, and it's definitely a fast solution, and a good idea to keep in mind...but you're right: it feels pretty hokey. Kind of the computer programmer's version of beating the Kobeyashi Maru.
Beska
it is bogus, but the answer is the answer, and I don't think you need to calculate it each time, since it shouldn't ever change. kind of like caching the answer ;-)
KM
Its hokey, but if its a solution then that's the fault of the person presenting the problem. A question like this should show example input and output, but never indicate what the actual input params will be, and make the input domain large enough that storing an array of all the possible answers is unreasonable.
Jherico
I learned my lesson, this is how I'd do it, bogus or not.
KM
@Jherico and @KM: oh it's absolutely a good idea. It's perfectly valid...and if I were there, I'd be all over it. But I think, in general, most competitions take pains to avoid allowing this kind of gimmickry, so it might not be something that works too often. (Although, in the real world, it can be a great idea, for reasonable amounts of data!)
Beska
my com sci prof explained to us how the winning team did it, he seemed ok with it. the answer is the answer, was his logic.
KM
That winning answer is a great example of non-linear thinking. If I were the judge and had any sense of humor, I'd give them first and second prizes.
Michael Petrotta
The answer is not bogus, there are plenty of real-world applications where the same technique could be applied successfully. I applaud the prof for creating a good teaching moment.
Mark Ransom
A: 

First, create table with two columns: Triangle_Number Count_of_Factors.

Second, derive from this a table with the same columns, but consisting only of the 320 rows of the lowest triangle number with a distinct number of factors.

Perform your speedy lookup to the second table.

Degan
This is pretty much exactly what KM wrote.
Beska
+2  A: 

see Triangular numbers: a(n) = C(n+1,2) = n(n+1)/2 = 0+1+2+...+n. (Formerly M2535 N1002)

then pick the language you want implement it in, see this:

"... Python

import math
def diminishing_returns(val, scale):
    if val < 0:
        return -diminishing_returns(-val, scale)
    mult = val / float(scale)
    trinum = (math.sqrt(8.0 * mult + 1.0) - 1.0) / 2.0
    return trinum * scale

..."

pageman
A: 

If you solved the problem, you should be able to access the thread on Project Euler in which people post their (some very efficient) solutions.

If you're going to copy and paste a problem, please cite the source (unless it was your teacher who stole it); and I second Wouter van Niferick's comment.

Zwergner
A: 

Well, at least you got a good professor. Performance is important.

Since you have a program that can do the job, you can precalculate all of the answers for 1 .. 320.

Store them in an array, then simply subscript into the array to get the answer. That will be very fast.

EvilTeach
+1  A: 

Here's a hint:

The number of divisors according to the Divisor function is the product of the power of each prime factor plus 1. For example, let's consider the exponential prime representation of 28:

28 = 22 * 30 * 50 * 71 * 110...

The product of each exponent plus one is: (2+1)*(0+1)*(0+1)*(1+1)*(0+1)... = 6, and sure enough, 28 has 6 divisors.

Now, consider that the nth triangular number can be computed in closed form as n(n+1)/2. We can multiply numbers written in the exponential prime form simply by adding up the exponents at each position. Dividing by two just means decrementing the exponent on the two's place.

Do you see where I'm going with this?

Boojum
Alright. So you are saying that rather counting all the factors, I should only find the prime factors.
Daredevil
No, your problem still requires you to determine how many factors there are. But for the nth triangular number, if you find the prime factors of n, and n+1, then that becomes trivial. And since n <= 320, even the brute force approach to finding the prime factors will be nigh instantaneous.
Boojum
+1  A: 

Compile with care, winner of worst code of the year :D

#include <iostream>

bool isPrime( unsigned long long number ){

    if( number != 2 && number  % 2 == 0 )
     return false;

    for( int i = 3;
     i < static_cast<unsigned long long>
     ( sqrt(static_cast<double>(number)) + 1 )
     ; i += 2 ){

     if( number % i == 0 )
      return false;
    }

    return true;
}

unsigned int p;
unsigned long long primes[1024];

void initPrimes(){

    primes[0] = 2;
    primes[1] = 3;
    unsigned long long number = 5;

    for( unsigned int i = 2; i < 1024; i++ ){

     while( !isPrime(number) )
      number += 2;

     primes[i] = number;
     number += 2;
    }

    return;
}


unsigned long long nextPrime(){

    unsigned int ret = p;

    p++;

    return primes[ret];
}

unsigned long long numOfDivs( unsigned long long number ){

    p = 0;
    std::vector<unsigned long long> v;
    unsigned long long prime = nextPrime(), divs = 1, i = 0;


    while( number >= prime ){

     i = 0;

     while( number % prime == 0 ){
      number /= prime;
      i++;
     }

     if( i )
      v.push_back( i );

     prime = nextPrime();
    }

    for( unsigned n = 0; n < v.size(); n++ )
     divs *= (v[n] + 1);

    return divs;
}

unsigned long long nextTriNumber(){

    static unsigned long long triNumber = 1, next = 2;

    unsigned long long retTri = triNumber;

    triNumber += next;
    next++;

    return retTri;
}

int main()
{
    initPrimes();

    unsigned long long n = nextTriNumber();
    unsigned long long divs = 500;

    while( numOfDivs(n) <= divs )
    n = nextTriNumber();

    std::cout << n;

    std::cin.get();
}
AraK