CODEWITHSUNDEEP
ruby
Joseph Ma
Joseph Ma

Reputation: 31

Project Euler #12

12 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:

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?

define a method that lists the factors of a number iterate through the sequence til a triangle is found with 500 factors return the number that has 500 factors if factors.count == 500

def factors(num)
  current_number = 1 
  factors_list= []
  while current_number <= num
    if is_factor(num,current_number)
      factors_list << current_number
    end
    current_number += 1 
  end
  return factors_list
end

def is_factor(big,small)
  if big % small == 0 
    return true 
  else 
    false 
  end
end     

def big_triangle(num) #500
  triangles = [1]
  natural_numbers = 1
  while factors(natural_numbers).count != num 
    triangles << natural_numbers
    natural_numbers += 1     
  end
  triangles.select { |n| factors(n).count == num }
end

Upvotes: 2

Views: 155

Answers (1)

Cary Swoveland
Cary Swoveland

Reputation: 110755

We should of course make use of relevant methods that Ruby provides. In this case one such (class) method is Prime::prime_division. For example,

require 'prime'

Prime.prime_division(2106)
  #=> [[2, 1], [3, 4], [13, 1]]

This tells us that 2106 has primes 2, 3, and 13, and that

2**1 * 3**4 * 13**1
  #=> 2106

How many factors does 2106 have? Each factor is of the form

2**a * 3**b * 13**c

where 0 <= a <= 1, 0 <= b <= 4, 0 <= c <= 1. This includes a = b = c = 0, the factor being 1 and a, b, c = 1, 4, 1, the factor being 2106. The number of factors therefore equals

(1+1) * (4+1) * (1+1)
  #=> 20

That is, for each number of times 2 is included (0 or 1), 3 can be included between 0 and 4 times, and for each of those 10 pairs, 13 can be included 0 or 1 times.

To take a simpler example, consider the triangle number 45:

Prime.prime_division(45)
  #=> [[3, 2], [5, 1]]

The number of factors is therefore

(2+1) * (1 + 1)
  #=> 6

Those factors are

3**0 * 5**0 #=>  1
3**0 * 5**1 #=>  5 
3**1 * 5**0 #=>  3 
3**1 * 5**1 #=> 15 
3**2 * 5**0 #=>  9 
3**2 * 5**1 #=> 45

We can therefore write

def nbr_factors(n)
  Prime.prime_division(n).reduce(1){ |t,(_,m)| t * (m+1) }
end

nbr_factors(2106)
  #=> 20
nbr_factors(45)
  #=> 6

The desired result may now be obtained quite easily.

def first_triangle_nbr_with_min_nbr_divisors(min_nbr_divisors)
  tri = 0
  1.step.each do |i|
    tri += i
    break tri if nbr_factors(tri) >= min_nbr_divisors
  end
end

first_triangle_nbr_with_min_nbr_divisors   6 #=>         28
first_triangle_nbr_with_min_nbr_divisors  20 #=>        528
first_triangle_nbr_with_min_nbr_divisors 501 #=> 76_576_500

The last few calculations for the last example are as follows.

...
i=12372, tri=76539378, nbr_factors(tri)=16
i=12373, tri=76551751, nbr_factors(tri)=8
i=12374, tri=76564125, nbr_factors(tri)=96
i=12375, tri=76576500, nbr_factors(tri)=576

Upvotes: 1

Related Questions