Ruby Project Euler # 12 Efficiency

Question

Working on Problem 12 of Project Euler:

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.

What is the value of the first triangle number to have over five hundred divisors?

Here's what I've got:

require 'reusable'

# The idea here is that 2^n is the smallest number with n factors, 
# according to their definition, so it's a good place to start.
# It also happens to be a HUGE number, so I'm worried I'm thinking 
# about this wrong. Did 4999 instead of 5000, just to make sure 
# I didn't overshoot.
start = 2 * 4999

# The faster way to calculate the nth Triangle number
def nthTriangle(n)
 n * (n + 1) / 2
end

def answer(num)
    i = startingTriangle(num)
    while true
        triangle = i*(i+1)/2
        puts triangle
        factors = numFactors(triangle)
        return "#{triangle} is triangle number #{i}, with #{factors} factors." if factors > num
        i += 1
    end
end

# Basic reversal of the nthTriangle thing to figure
# out which n to start with in the answer function.
def startingTriangle(n)
    power = n - 2
    sqrt(power * 2).to_i - 1
end

puts answer(5000)

And that required file (where I'm trying to put methods I'll reuse in a bunch of Euler problems):

def primesUpTo(n)
  nums = [0, 0] + (2..n).to_a
  (2..sqrt(n).to_i+1).each do |i|
    if nums[i].nonzero?
      (i**2..n).step(i) {|m| nums[m] = 0}
    end
  end
  nums.find_all {|m| m.nonzero?}
end

def prime?(n)
    test = primesUpTo(sqrt(n).to_i)
    test.each do |i|
        if n % i == 0
            return false
        end
    end
    true
end

# Just for faster, more intuitive (to me) array summing
def sum(array)
    array.inject(0) {|s, n| s + n }
end

# Ditto
def product(array)
    array.inject(1) {|p, n| p * n}
end

# I don't like typing the 'Math.'
def sqrt(n)
    Math.sqrt(n)
end

# Returns an array of arrays of the prime factors of num
# Form [[factor1, power1],[factor2, power2]]
# Ex: primeFactors(12) == [[2,2],[3,1]]
def primeFactors(n)
    array = []
    # 2 3 
    primesUpTo((n/2).to_i+1).select{ |i| n % i == 0 }.each do |p|
        pcount = 1
        n = n / p
        while n % p == 0
            pcount += 1
            n = n / p
        end
        array << [p, pcount]
    end
    array
end

# Returns the number of factors a number has
# INCLUDING both the number itself and 1
# ex: numFactors(28) = 6
def numFactors(n)
    return 2 if prime?(n)
    product = 1
    primeFactors(n).each do |i|
        product *= i[1] + 1
    end
    product
end

My problem is that my code is really super slow. If I start at 1 instead of my start number, it takes a minute + before it gets to like 200000 (nowhere near 2^4999). But apart from scrapping the library prime-number solution and adding all primes to an array I keep referring to -- which I feel would only make it a small amount faster -- I can't think of how to make this much faster. And it needs to be WAY faster.

Am I thinking about this all wrong? Any suggestions?

Also useful would be any suggestions for how to improve the efficiency of any of my library methods, which I'll probably be using again and again. I wanted to make them from scratch so I understood them, but I'm afraid they're very inefficient.

Answer 1

From your code:

The idea here is that 2^n is the smallest number with n factors

From the stated Project Euler task:

We can see that 28 is the first triangle number to have over five divisors.

I'm not sure why you think 2^n is the smallest number with n factors, but the example given in the question clearly proves your assumption wrong, as 2^5 = 32, which is greater than 28.

My solution starts the search at 1 and is reasonably efficient. I don't use primes at all.

Addendum: For the sake of completeness, the other large issue besides starting at a number far too high is searching for greater than 5000 divisors rather than greater than 500, as you noticed and pointed out in the comments.