1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
|
require 'spec_helper'
require 'prime'
=begin
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?
help:
* http://www.wikihow.com/Determine-the-Number-of-Divisors-of-an-Integer
* https://www.khanacademy.org/math/pre-algebra/factors-multiples/prime_factorization/v/prime-factorization
=end
class TriangleNumbers
include Enumerable
def each(&block)
n = 1
loop do
block.call(sum_of(n))
n += 1
end
end
private
def sum_of(n)
n.downto(0).inject(0) { |total, m| total += m }
end
end
describe 'problem 12' do
describe TriangleNumbers do
it 'produces the first 7 triangle numbers' do
expect(subject.take(7)).to eql([1, 3, 6, 10, 15, 21, 28])
end
it 'produces the first 10 triangle numbers' do
expect(subject.take(10)).to eql([1, 3, 6, 10, 15, 21, 28, 36, 45, 55])
end
end
class Divisors
def divisors_for(n)
1.upto(n).find_all do |x|
(n % x).zero?
end
end
def number_of_divisors_for(n)
prime_factors = n.prime_division
powers_plus_one = prime_factors.map do |(prime, exponent)|
exponent + 1
end
powers_plus_one.inject(1) { |total, power| total *= power }
end
end
describe Divisors do
it 'returns each factor for a number' do
{
1 => [1],
2 => [1, 2],
3 => [1,3],
4 => [1,2,4],
5 => [1, 5],
6 => [1,2,3,6],
7 => [1, 7],
8 => [1, 2, 4, 8],
9 => [1, 3, 9],
10 => [1,2,5,10],
11 => [1, 11],
12 => [1, 2, 3, 4, 6, 12],
13 => [1, 13],
14 => [1, 2, 7, 14],
15 => [1,3,5,15],
16 => [1, 2, 4, 8, 16],
21 => [1,3,7,21],
24 => [1, 2, 3, 4, 6, 8, 12, 24],
28 => [1, 2, 4, 7, 14, 28],
}.each do |key, values|
expect(subject.divisors_for(key)).to eql(values)
end
end
it 'brute forces the answer' do
subject = TriangleNumbers.new
divisors = Divisors.new
result = subject.find do |n|
divisors.number_of_divisors_for(n) >= 500
end
expect(result).to eql(76576500)
end
end
end
|
