【Project EulerにRubyで挑戦シリーズ】問14:Longest Collatz sequence

スポンサーリンク

今回の問題

Longest Collatz sequence

The following iterative sequence is defined for the set of positive integers:

n → n/2 (n is even)
n → 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

Which starting number, under one million, produces the longest chain?

正の整数に以下の式で繰り返し生成する数列を定義する.

n → n/2 (n が偶数)
n → 3n + 1 (n が奇数)

13からはじめるとこの数列は以下のようになる.

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
13から1まで10個の項になる. この数列はどのような数字からはじめても最終的には 1 になると考えられているが, まだそのことは証明されていない(コラッツ問題)

さて, 100万未満の数字の中でどの数字からはじめれば最長の数列を生成するか.

書いた内容

def collatz_sequence(number:, count:)
  if number == 1
    count += 1
  elsif number.even?
    collatz_sequence(number: number / 2, count: count += 1)
  else
    collatz_sequence(number: 3 * number + 1, count: count += 1)
  end
end

result_hash = { longest_chain_count: 0, answer: 0 }
(1..1000000).each do |number|
  calculation = collatz_sequence(number: number, count: 0)
  if result_hash[:longest_chain_count] < calculation
    result_hash[:longest_chain_count] = calculation
    result_hash[:answer] = number
  end
end

puts result_hash

コラッツ数列が1に収束するまでの数列長を返すcollatz_sequenceメソッドを定義しました。

あとは1から100万までの整数を順番にコラッツ数列の最初の値として利用します。

数列長が最大になるときの整数値がハッシュに残るようにeachを回しました。

※Project Eulerのリポジトリ

          
    

スポンサーリンク

  
Scroll Up