CODEWITHSUNDEEP
rubyalgorithm
megashigger
megashigger

Reputation: 9053

Algorithm that finds first triangle number with > 500 factors is running to slow

This is my algorithm that finds the first triangle number with > x factors. I can run it up to about x = 150, and after that it takes forever. What changes can I make to speed it up? Thanks!

def triangle_numbers_max_divisors(x)
    triangle_numbers = []
    divisors = 0
    a = 1; b = 2

    until divisors > x
        divisors = 0
        triangle_numbers.push(a)
        a = a + b; b += 1

        for i in 1..triangle_numbers.last
            if triangle_numbers.last % i == 0
                divisors += 1
            end
        end
    end
    triangle_numbers.last
end

Upvotes: 0

Views: 475

Answers (3)

Cary Swoveland
Cary Swoveland

Reputation: 110725

The reasons your code is running slowly have been given in other answers. Here is a Ruby-like way to code the algorithm. It took about about 10 seconds to solve.*

Code

def triangle_numbers_max_divisors(min_nbr_factors)
  (1..Float::INFINITY).reduce(0) do |tnbr, n|
    tnbr += n
    return tnbr if nbr_factors(tnbr) >= min_nbr_factors
    tnbr
  end
end

def nbr_factors(n)
  m = Math.sqrt(n)
  2 * 1.upto(m).count { |i| (n % i).zero? } - ((n == m * m) ? 1 : 0)
end   

p triangle_numbers_max_divisors(500) #=> 76_576_500

Explanation

  • You only want a single value, so there is no need to keep divisors. Just count them.
  • If n is a perfect square, the term - ((n == m * m) ? 1 : 0 causes n's square root to be counted only once.
  • Sometimes you will see (1..Float::INFINITY) written as (1..1.0/0).

. * On a recent-vintage Macbook Pro

Upvotes: 2

Rafa Paez
Rafa Paez

Reputation: 4860

Looks like you are trying to solve the Problem number 12 of the Project Euler called Highly divisible triangular number.

I have tried to improve your code but unfortunately your solution is slow and inefficient the per se, it cannot be radically improved without changing the approach. Take a look at this solution and also to this SO thread.

Upvotes: 3

John C
John C

Reputation: 1981

I don't know if this is current, but there appears to be a problem re-allocating the space for the array. At 127, your code only takes about six seconds to run, then jumps to thirty seconds at 128. It levels off again for a while.

If you pre-allocate the array with something like triangle_numbers = Array.new(x), you'll lose the concise .last syntax and will have to track the array index, but the code runs in roughly quadratic time across the board. That means it'll still get disproportionately slower for each increase, but there's not much you can do about that and you shouldn't hit any weird discontinuities.

Upvotes: 2

Related Questions