ruby - 欧拉计划 #12

Question

12 三角形数列由自然数相加生成。所以第 7 个三角形数是 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28。前十项是:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

让我们列出前七个三角形数的因数:

• 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

我们可以看到 28 是第一个有超过五个因数的三角形数。

第一个除数超过五百的三角形数是多少？

定义一个列出数字因数的方法遍历序列直到找到一个包含 500 个因子的三角形返回具有 500 个因子的数字如果 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

Answer 1

我们当然应该利用Ruby提供的相关方法。在这种情况下，一种这样的(类)方法是 Prime::prime_division .例如，

require 'prime'

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

这告诉我们 2106 有素数 2 , 3 , 和 13 , 而那个

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

2106有多少因素有？每个因素的形式都是

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

哪里0 <= a <= 1 , 0 <= b <= 4 , 0 <= c <= 1 .这包括 a = b = c = 0 ，因子为 1和 a, b, c = 1, 4, 1 ，因子为 2106 .因此，因子数等于

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

也就是对于每个次数2包括( 0 或 1 )，3可以包含在 0 之间和 4次，对于这 10 对中的每一对，13可以包含0或 1次。

举一个更简单的例子，考虑三角形数45 :

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

因此因子的个数是

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

这些因素是

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 

因此我们可以写

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

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

现在可以很容易地获得所需的结果。

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

最后一个例子的最后几个计算如下。

...
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