CODEWITHSUNDEEP
ruby
cvu
cvu

Reputation: 502

(running forever) Finding a triangular # with over 500 factors

I am currently working on the peuler question. I think I have the correct code since I tested it with the one that was provided in the example. However, when I try to run it to find the first triangular number with over 500 factors, it stays running for over 15 minutes. But when I try and find the first triangular number with over 100 factors, it finds it in under a minute.

Please see below:

My question is how can I get this too calculate quicker? Because it seems to be stuck?

#Project 12 #http://projecteuler.net/problem=12

def triangle(x) #finds the (x)st triangular number
    x=(1..x)
    return x.inject(:+)
end

def factors(x) #calculates how many factors (x) has
    factors =[]
    range=(1..x)
    range.each {|num|
    if x%num==0 
        factors << num
    end
    }
    return factors.length
    end 

def project12(x) #finds the first triangular number that has over (x) factors
i=1
    until factors(triangle(i)) > x
        i += 1
    end
return triangle(i)
end

print project12(500)

Upvotes: 1

Views: 139

Answers (1)

David
David

Reputation: 7456

So, in triangle(x), you do x-1 additions. You run through this at i and up to i in your code, so we have (i-1) + (1 + 2 + 3 + 4 + 5 + 6 + ... + i - 1) which approximates to i^2/2. Then, in factors your code runs essentially at x time. You do this for every triangle(i), so we have 1*triangle(1) + 2*triangle(2) + 3*triangle(3) + 4*triangle(4) + ... + i*triangle(i) = 1*0 + 2*1 + 3*2 + 4*3 + ... + i*(i-1), which is approximately i^3/3 - i/3.

What does this mean? It means that based on my sketch your program runs at approximately i^3/3 - i/3 + (i-1) iterations. This is cubic time and definitely does not scale.

If, for example we had to do this up until i = 50, this would run 41699 times through. Now, let us imagine doing it just one time more: 44255 times if i = 51. That's definitely not going to scale.

Upvotes: 5

Related Questions