Numbers, exponents and cycles

by Mithrandir

Suppose we have a number N_0. We apply the following procedure to N_0 in order to obtain a new number N_1: we take N_0‘s digits and raise them alternatively to 2 and 4, summing the results. Thus, N_0=2435 will become N_1=2^4+4^2+3^4+5^2=138. We don’t stop here. Instead, we apply the same procedure to N_1 obtaining N_2=1^2+3^4+8^2=146.

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:

final

as can be seen, the length of the iterative process is very low. Timing the execution speed, our algorithm is in O(n). 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 :)

About these ads