「Collatz予想」（角谷予想，3x+1問題）についての問題ですか。初耳です。Pythonで参加したいと思います。

Lightweight Language Ring : キミならどう書く 2.0 – ROUND 2 –

となり， f(n) の呼出は8回である．これをステップ数と呼ぶことにする．
ここで f(n) が 1 になるまでのステップ数を g(n) とする．つまり，g(3) = 8 である．
このとき

h(n) = k, 1 ≦ k ≦ n ∧ g(k) = max (g(1),g(2),…,g(n))

について h(100) を求めよ．

ちなみに最大ステップ数が二つ以上ある場合はkはいくつにすればいいんですかね？今回はとりあえず、最大ステップ数を持つすべてのｋを表示してます。

与えられた数値のステップ数を求めるgetstep関数を作って、それを1から100のリストにmap関数して、得られたリストの最大値を求めて、その値を持つインデックスを表示とします。

collatz.py

def getstep(x, list=None):
if list is None:
list = []
if x == 1:
list.append(x)
return len(list)
else:
if x % 2 == 0:
list.append(x)
return getstep(x / 2, list)
else:
list.append(x)
return getstep(x * 3 + 1, list)
def collatz(num):
steplist = map(getstep,range(1,num + 1))
maxstep = max(steplist)
for i in range(0,num):
if steplist[i] == maxstep:
print i + 1,

実行結果。

>>> collatz(100)
97

という訳で、正解は97だと思います。ちなみにこのアルゴリズムだと、100000くらいを求めようとするともう10秒以上かかってしまいました。まだまだ改良が必要です。

>>> collatz(100)
97
>>> collatz(1000)
871
>>> collatz(10000)
6171
>>> collatz(100000)
77031