コラッツ・角谷の問題 in Haskell DouKaku?

任意の数nを与えたときに
・nが偶数ならば2で割る　(n=n/2)
・nが奇数ならば3倍して1を足す （n = 3*n+1)
を繰り返すと、いづれは1になる。というものがあります。

数値計算の上ではかなりの数まで成り立つことが知られています。
（すべての数について成り立つかは不明）
参考リンク先参照

ある任意の数nがコラッツ・角谷の問題で1になるまでのステップ数をf(n)とします。
1～2^20までの数でf(n)を求めて、f(n)が最大になるときのnとf(n)を表示してください。

たとえばn=9だと次のような数列をたどって、19ステップで1になります。
9->28->14->7->22->11->34->17->52->26->13->40->20->10->5->16->8->4->2->1
つまりf(9)=19です。

また、最大を求めた際の実行時間と環境を書いてください。

see: コラッツの問題の成り立つ範囲

実行結果:
n=837799, f(n)=524

実行時間:
$ time ./a.out
(524,837799)

real    3m28.485s
user    3m27.893s
sys     0m0.368s

実行環境:
CPU: celeron 1.2GHz
MEM: 256MB

module Main where

import Data.Map

main = print $ findMax $ fromList [(collatz n, n) | n <- [1..2^20]]

collatz n
    | n == 1 = 0
    | even n = 1 + collatz (n `div` 2)
    | otherwise = 1 + collatz (n * 3 + 1)

{-# OPTIONS_GHC -fglasgow-exts -fbang-patterns #-}

{-
$ uname -sr
Linux 2.6.23-gentoo-r3
$ uname -p
Intel(R) Pentium(R) M processor 1.70GHz
$ ghc --version
The Glorious Glasgow Haskell Compilation System, version 6.8.2
$ ghc -O2 collatz.hs
$ time ./a.out
(524,837799)
./a.out  6.80s user 0.13s system 90% cpu 7.639 total
-}

import Data.Array
import Data.List

nMax :: Num a=>a
nMax = 2^20

-- (m,k) = collatzStep n のとき、
-- nをステップ数kで[1..nMax]内のmに帰着できる。
collatzStep :: Integer->(Int,Int)
collatzStep n
    | n' <= nMax = (fromIntegral n',1)
    | otherwise = let (m,!k) = collatzStep n' in (m,k+1)
    where n' = if even n then n `div` 2 else 3*n+1

collatzStep' :: Int->(Int,(Int,Int))
collatzStep' n = (m,(n,k))
    where (m,!k) = collatzStep (toInteger n)

-- collatzStep で得られる帰着関係を反転してグラフにする。
-- colltz 角谷の予想が正しければ1を根とした木になっている。
collatzTree :: Array Int [(Int,Int)]
collatzTree = accumArray (flip (:)) [] (1,nMax) (map collatzStep' [2..nMax])

-- DFSで高さを調べる。
deepest :: Array Int [(Int,Int)]->Int->(Int,Int)
deepest ar m = maximum.((0,m):) $ [(k+k',n')|(n,k)<-ar!m,let (!k',n')=deepest ar n]

main :: IO ()
main = putStrLn.show $ deepest collatzTree 1

DouKaku?

コラッツ・角谷の問題

Posted feedbacks - Haskell

Index

Feed

Other

Link

Pathtraq