Numbers, exponents and cycles
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.
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
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
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]
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 :)