primes = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]

-- number of ways to combine the primes not exceeding x, excluding 1

count :: [Int] -> Int -> Integer

count (p:ps) x = go x

    where go x

              | x >= p  = 1 + go (div x p) + count ps x

              | otherwise = 0

count [] _ = 0

main = print $ (1+) $ count primes (10^9)

{- For debugging

count' :: [Int] -> Int -> [Int]

count' (p:ps) x = go p x

    where go prod x

              | x >= p  = [prod] ++ go (prod*p) (div x p) ++ (map ((`div` p) . (*prod)) $ count' ps x)

              | otherwise = []

count' [] _ = []

-}

import Prelude hiding ((!!))

import Data.List (genericIndex)

(!!) = genericIndex

fib :: Integer -> Integer

fib = (100 *) . (map fib' [0..] !!)

    where fib' = fst . fib2

          fib2 0 = (1, 1)

          fib2 1 = (1, 2)

          fib2 n

              | even n    = (a*a + b*b, c*c - a*a)

              | otherwise = (c*c - a*a, b*b + c*c)

              where (a,b) = fib2 (n `div` 2 - 1)

                    c     = a + b

-- Given a number x, locate which fib will be at least x.

locate x = let go i

                   | fib i >= x = i

                   | otherwise = go (i+1)

           in

             go 0

a = "1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679"

b = "8214808651328230664709384460955058223172535940812848111745028410270193852110555964462294895493038196"

get :: Integer -> Integer

get x = read [go x $ locate x]

    where go x 0 = a !! (x-1)

          go x 1 = b !! (x-1)

          -- Find the xth number in the yth fib

          go x y

              | u >= x = go x (y-2)

              | otherwise = go (x-u) (y-1)

              where u = fib (y-2)

main = print $ sum $ zipWith (*) xs ys

    where g n = (127 + 19*n) * 7^n

          xs = map get $ map g [0..17]

          ys = 1:(map (*10) ys)

We're asked to calculate the position of the cursor after 10¹² steps in D_{50, so we don't have to compute the whole string. The problem is equivalent to calculate the position of the cursor after 10¹² steps in D40. Still, the problem is not simplified much.}

After looking up wikipedia, I found that I overlooked a very important fact: Y(n) is the reverse of X(n) with L and R swapped.

At first I simply used foldl' from Data.List that uses seq to force evaluation. Turns out that it's still too lazy: it builds up too many thunks that eats my memory away. Why? Because (a,b,c) is already in WHNF, so seq is not going to evaluate a, b, or c. It's a shame that ghc -O2 didn't do the strictness analysis deeply enough. Although deepSeq fixes our memory problem, the program is still very inefficient: it computes the positions sequentially.

To be able to interrupt the program and pick up the progress later, I wrote the following ugly imperative program:

Finally, after about 10 days, the computer worked out the answer. With the correct answer, I can now find out more efficient algorithms at the discussion board. Turns out that I overlooked yet another important fact: at nth iteration, a duplicate of the graph at (n-1)th stage is rotated anti-clockwise by 90 degrees with the center of rotation at the end point of the (n-1)th graph. This observation reduces O(n) to O(log n). One user even posted the solution at the Wikipedia page. I find that Ruby program pretty easy to follow, once I understood the theory. Here's a solution by BrianHuffman, using slightly different properties: