Project Euler with Ruby on WSL [Problem 14]

問題13くらいみんな簡単だといいのに

いやそうでもないか

問題

Longest Collatz sequence

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

(n is even)

(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?

NOTE: Once the chain starts the terms are allowed to go above one million.

私訳

最長のコラッツ数列

n が偶数なら n/2, n が奇数なら 3n+1 を次の項とする数列を、コラッツ数列と呼ぶ。 適当な数 k から始めたとき 1 に到達するまでの数列の長さをチェーン長と呼ぶことにする。 例えば 13 ならチェーン長は 10 (=1も数える)。

100万未満の数から始めたとき、チェーン長が最長の数はどれか？

解答方針

チェーン長を格納する配列 chain_len = [] を用意し、 chain_len[n] に n から始めたときのチェーン長を格納する。 すると、適当な数 k から始めたとき、 chain_len に記録されている範囲に来たら、そこから先の数は数えなくてよい。

あとは chain_len の max を探す。