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
|
# File 'lib/numb/achain.rb', line 28
def self.factor(n)
build_tree = ->(n) do
return if n == 1
p = n.prime_factors.first
q = n/p
q, p = p - 1, 1 if p == n
{left: q, value: n, right: p}.tap do |node|
node[:right] = build_tree[p] if p > 1
node[:left] = build_tree[q] if q > 1
end
end
current, chain = (t = build_tree[root = n]), [x = 1]
make_chain =->(node) do
[:right, :left].each do |dir|
if node[dir] == 2 then chain << x *= 2
elsif node[dir] and node[dir] != 1
x = make_chain[node[dir]]
end
node[:x] = x if dir == :right
end
if node[:value] == root and node[:right] == 1
if r = node[:right]
x += r.respond_to?(:fetch) ? r[:x] || 0 : r
end
chain << x
elsif node[:value] != root and node[:right] == 1
x += node[:x] if node.respond_to?(:fetch) and node[:x]
node.delete(:x)
chain << x
end
x
end
make_chain[t]
chain
end
|