My Weblog

Blog about programming and math

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..]

readInt :: BS.ByteString -> Integer
readInt = fst . fromJust . BS.readInteger

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

August 8, 2011 - Posted by | Programming | , , ,

3 Comments »

  1. Remarkably well written piece

    Comment by Scene | October 17, 2011 | Reply

  2. please help me to write this code in c++…..
    my problem is to handle the large input given in test cases

    Comment by Prashant Gupta | January 4, 2012 | Reply

  3. @Prashant For c++ you will have to write your own big integer library. Store the numbers in char array or string and implement division by 2 and multiplication 3. Also with some efforts , you can try this problem in python which has inbuilt support for big numbers and simple enough to learn with elegant syntax.

    Comment by tiwari_mukesh | January 4, 2012 | Reply


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: