# My Weblog

## SPOJ 515. Collatz

SPOJ 515. Collatz is bit archaic in expression. Its 3 * n + 1 problem . $f(1) = N$ and $f(K) = ( 0.5 + 2.5 * ( f(K-1) \bmod 2)) * f(K-1) + (f(K-1) \bmod 2)$ if K>1. If $f(k-1)$ is odd then given expression $f(K) = 3 * f(K-1) + 1$ and if $f(k-1)$ is even then $f(K) = \frac {f(k-1)}{2}$. Accepted Haskell code.

import Data.List
import Data.Maybe
import qualified Data.ByteString.Lazy.Char8 as BS

{--
collatz :: Integer -> Integer
collatz n = head . filter (\t -> helpCollatz t == 1 ) $[ 1.. ] where helpCollatz 1 = n helpCollatz k = l where t = helpCollatz ( k - 1 ) l = if odd t then 3 * t + 1 else div t 2 --} solve :: Integer -> Integer solve n = succ . fromIntegral . fromJust . findIndex ( \t -> t == 1 ) . scanl ( \ x y -> if odd x then 3 * x + 1 else div x 2 ) n$ [ 2..]

main = BS.interact \$ BS.unlines. map ( BS.pack.show . solve . readInt ) . BS.lines


August 8, 2011 -