### Numbers, exponents and cycles

#### by Mithrandir

Suppose we have a number . We apply the following procedure to in order to obtain a new number : we take ‘s digits and raise them alternatively to 2 and 4, summing the results. Thus, will become . We don’t stop here. Instead, we apply the same procedure to obtaining .

Of course, and someone can prove it, this procedure will quickly lead either to a number already seen or to 1. For now, we are only interested in the number of iterations required for this.

We will plot the answer using gnuplot and will use command line arguments to get the maximum value. Thus, we will have to make an import.

`import System.Environment(getArgs)`

To simplify function signatures we will give an alias to our type:

`type Number = [Int]`

Basically, our number will be treated as a list of digits, the head of the list being the least significant digit of the number. The conversion between Int and Number should be simple:

`int2Number :: Int -> Number`

int2Number x = if x < 10 then [x] else (x `mod` 10) : (int2Number $ x `div` 10)

Now, for the interesting part: applying our procedure to the Number in order to obtain another. Using function composition, combining cycle, zip, map and sum, the answer is only one line long:

`function42 :: Number -> Number`

function42 = int2Number.sum.(map (\(e,v)->v^e)).(zip (cycle [2,4]))

Now, the cycle’s length part. Basically, we will need a function takeUntil but this doesn’t exist for now. Yet, we can change the signature to something more general and use until. Again, we will compose different functions in order to obtain the result:

`getCycleLength :: Int -> Int`

getCycleLength n = l - 2

where

l = length $ until test iterate [int2Number n]

test l = (head l) `elem` (tail l)

iterate l = (function42 (head l)):l

Now, we only need to get the results back to stdout in a manner which can be piped to gnuplot to obtain the plot. Only two IO functions are needed:

`printList :: (Show a) => [a] -> IO ()`

printList [] = return ()

printList (x:xs) = do

putStrLn $ show x

printList xs

main = do

args <- getArgs

let n = read $ head args

putStrLn "set term png"

putStrLn "plot '-' axes x1y1 smooth csplines with lines 1"

printList $ map getCycleLength [1..n]

putStrLn "e"

Getting the final results in a nice plot is very simple. Just compile the code and pipe it to gnuplot (this is why in the main function we wrote those strings).

`mihai@keldon:~/Desktop/hs/tmp$ ghc test.hs -o test`

mihai@keldon:~/Desktop/hs/tmp$ ./test 1000000 | gnuplot > final.png

Here’s the result:

as can be seen, the length of the iterative process is very low. Timing the execution speed, our algorithm is in . Looking at the memory footprint, we shockingly observe that it is constant (in fact, this is due to laziness :P)

Next puzzle will be solved in 16 days :)

A few handy library functions you might not know. (import List)

zipWith:

function42 = int2Number.sum.(zipWith (flip (^)) (cycle [2,4]))

iterate:

I’m not really sure it’s really appropriate here, but since you named one of your functions iterate, I’m guessing you don’t know the library function of the same name. Also pattern-matching is better idiom than head and tail in test.

getCycleLength n = l – 1

where

l = length $ takeWhile (not.test) $ map reverse

$ tail $ inits $ iterate function42 $ int2Number n

test (x:xs) = x `elem` xs

sequence:

printList = sequence . (map (putStrLn.show))

I forgot zipWith but I knew that there is a iterate function.

However, it was my mistake to use head and tail (in fact, it is a rewrite).

And sequence I didn’t know.

Thanks.

> Basically, we will need a function takeUntil but this doesnâ€™t exist for now.

Isn’t that ‘takeWhile’ with a ‘not’ inside one of its arguments?

Not really if negating the test is more complex that the original (checking if two elements are the same versus checking if all elements are different)

I guess

Teah, I am wrong. I must sleep more often :)

You might also be interested in this classic Haskell idiom

(using the usual ‘iterate’, not the one you defined):

int2Number = map (`mod` 10) . takeWhile (> 0) . iterate (`div` 10)

An even shorter suggestion for printlist would be to use

printlist = mapM_ print

mapM_ performs the action on each element in the list and throws the result away; print is putStrLn.show! (Greg’s version using sequence keeps the result)

Thanks for the replies. This series on small haskell puzzles is intented to make me learn this language :) Thanks for the input.