Reputation: 31
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
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