友愛数の総和を求めるメソッドをテスト駆動開発する(Project Euler 問21)

スポンサーリンク

今回の問題

Amicable numbers

Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n).
If d(a) = b and d(b) = a, where a ≠ b, then a and b are an amicable pair and each of a and b are called amicable numbers.

For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore d(220) = 284. The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220.

Evaluate the sum of all the amicable numbers under 10000.

d(n) を n の真の約数の和と定義する. (真の約数とは n 以外の約数のことである. )
もし, d(a) = b かつ d(b) = a (a ≠ b のとき) を満たすとき, a と b は友愛数(親和数)であるという.

例えば, 220 の約数は 1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110 なので d(220) = 284 である.
また, 284 の約数は 1, 2, 4, 71, 142 なので d(284) = 220 である.

それでは10000未満の友愛数の和を求めよ.

書いた内容

テストの作成と仮メソッド定義

Minitest を用いて、自身を除く約数の総和を求める
d(number)メソッドのテストを仮で記載しました。

まずはテストが通るようにメソッド自体も返り値を直接 284 と記載しました。

require 'minitest/autorun'
require './problem'

require 'minitest/reporters'
Minitest::Reporters.use!

class ProblemTest < Minitest::Test
  def test_sum_of_proper_divisors
    assert_equal 284, d(220)
  end
end
def d(n)
  284
end

自身を除いた約数の総和を出すようにメソッドを修正してテストを通す

約数の総和を求める公式はこちらのサイトで紹介されているものを用いました。
約数の総和を求める二つの公式と証明

prime_divizionメソッドを引数 number に対して用いると
その素因数と指数の組を配列で返します。

これをmapメソッドで順次計算して、injectメソッドで畳み込み演算することで公式の通りの計算をしています。
ただし、number が 1 のときには分母が 0 となりエラーになるので場合分けをしています。

def d(number)
  if number != 1
    geometric_progression_of_divisor = Prime.prime_division(number).map do |n, i|
      (n**(i + 1) - 1) / (n - 1)
    end
    geometric_progression_of_divisor.inject(&:*) - number
  else
    1
  end
end

友愛数かどうかのテストとメソッドの仮定義

同様に友愛数かどうかのメソッドも仮定義してテストを通しておきます。

def test_amicable
  assert_equal true, amicable?(220, 284)
end
def amicable?(number, comparison)
  true
end

友愛数の判定メソッドを定義してテストを通す

友愛数かどうかの判定は問題文の下記を用いるだけです。
d(a) = b かつ d(b) = a (a ≠ b のとき)

テストは通ります。

def test_amicable
  assert_equal true, amicable?(220, 284)
  assert_equal false, amicable?(220, 255)
  assert_equal true, amicable?(220, d(220))
  assert_equal false, amicable?(5, d(5))
end
def amicable?(number, comparison)
  d(number) == comparison && d(comparison) == number && number != comparison
end

10000以下の友愛数を足し上げれば良いので下記の計算をして

answer = 0
(1..10_000).each do |i|
  answer += i if amicable?(i, d(i))
end
puts answer
#=> 31626

最終的な答えは 31626 と出すことが出来ました。

※問21ブランチのプルリクエスト

          
    

スポンサーリンク

  
Scroll Up