I've been trying to optimize this while making it readable. Thoughts?

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?

@triangle_number = 441
@factors = []
@right_of_tree = []
@left_of_tree = []

def find_triangle_number_with_500_factors
  natural_number = 1000
  while !over_500_factors?
    @factors = []
    @right_of_tree = []
    @left_of_tree = []
    natural_number += 1
  p @triangle_number

def triangle_number_generator(natural_number)
  @triangle_number = natural_number*(natural_number+1) / 2

def find_factors_with_a_factor_tree

def find_combinations_in_left_of_tree
  last_prime_factor = @right_of_tree.last
  (1..@left_of_tree.length).each do |combination_size|
    cxget_combinations(@left_of_tree, combination_size)
    combinations.each do |arr|
      @factors << arr.inject(:*)

def get_combinations(arr, combination_size)

def create_prime_factor_tree(number)
  until number <= 1
    factor = get_initial_divisor(number)
    if factor
      @right_of_tree.push(number / factor)
      number = number / factor  

def get_initial_divisor(number)
  2.upto(number / 2) do |possible_factor|
    if number % possible_factor == 0
      return possible_factor
  return nil

def over_500_factors?
  return true if @factors.size + @right_of_tree.size >= 498

Benchmark.bm do |bm|
  bm.report { find_triangle_number_with_500_factors}

1 Answer 1


Main method

You want your code to tell the story of how you are solving the problem, starting with the general picture and then working down to the details.

Your main method is find_triangle_number_with_500_factors. I suggest you change the name slightly:

  • drop "find" as being useless.
  • don't hardwire "500".

Not hardwiring "500" makes the method more general, facilitates testing and helps explain what the method does. In general, hardwiring is bad and doesn't buy you anything.

Perhaps we might call the method smallest_triangle_number(nbr_factors).

Make the main method simple, showing how the calculation is made is the simplest of terms:

def smallest_triangle_number(nbr_factors)
  n = 0
  nfacs = 0 
  while nfacs < nbr_factors
    n += 1
    tnbr = triangle_number(n)
    nfacs = nbr_factors(tnbr)

To my way of thinking, the shorter the method, the shorter the variable names can be. If a method is short, and you understand what value a variable holds, you don't have to remember its name very long, so it can be short. Here I used n (and nbr) for "number" because I always use that convention. triangle_number(n) obviously is a method that calculates n's triangle number. I can use something short like tnbr because the expression says what it is. Same with nbr_factors and nfacs.

If you want to get fancy you don't have to begin with the number 1. Instead, you could calculate a lower bound on numbers that have triangle numbers with the given number of factors.

Calculate triangle numbers

Next, in order, the method triangle_number(n). Your method is fine, except "generator" doesn't add anything to the name and there is no need for an instance variable. Just return the triangle number, which also helps with the self-documentation of the method:

def triangle_number(nbr)
  nbr * (nbr + 1) / 2

I suggest that you only introduce instance variables when you really need them. For this problem, I don't think you need any.

This problem concerns natural numbers, so I think nbr is enough. (Nobody will ask, "What if nbr is negative, a float, a complex number or a Roman numeral"?) You could instead calculate each triangle number from the previous one, but this is a quick calculation relative to the other work that must be done, and stands alone, so I think that's fine.

Calculate factors

Next up, nbr_factors. You are doing that calculation in two steps, so again, keep the method short to give the reader the big picture:

def nbr_factors(nbr)
  pfacs = prime_factors(nbr)

Again, this is pretty much self-documenting. Notice that I've written the argument as nbr, rather than some variation of triangle_number. That's because the method applies to natural numbers generally, even though we will only use it for triangle numbers. You could of course also write this as:

def nbr_factors(nbr)

That's up to you, but you probably want to use the first form at least while you are debugging and testing.

Calculate number of factors from prime factors

Now let's go out of order and look at the method prime_factors_to_nbr_factors. This one is actually quite easy, as we can employ a version of the Tau function.

Suppose we have constructed prime_factors(n) to return the array:

pfacs = [[f1,n1], [f2,n2],..., [fm, nm]],


fi is the ith prime factor
ni is the number of times fi is a factor


n = f1**n1 * f2**n2 *...* fm**nm

The Tau function tells us the number of factors is:


which in Ruby-speak is:

def prime_factors_to_nbr_factors(prime_factors)
  prime_factors.reduce(1) { |tot,(_,n)| tot *= (n+1) }

It makes sense that the number of factors should not depend on what the particular prime factors are, just how many there are and the number of times each occurs.

(Note that if you don't care about displaying the prime factors, you could have prime_factors--probably renamed--return only [n1, n2,..., nm].)

Suppose, for example:

tnbr = triangle_number(7)
  #=> 28


pfacs = prime_factors(28)
  #=> [[2,2], [7,1]]


prime_factors_to_nbr_factors([[2,2], [7,1]])
  #=> (2+1)*(1+1) => 6

It remains to construct the method prime_factors to return an array similar to pfacs above. As I've rambled on awhile, I'll leave it to others to cover that.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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