Обоснование решения задачи №68 от UniLecs

comparison.hs

type Seq = String
type Solution = [Seq]

seed :: Solution
seed = ["44", "47", "74", "77"]

extendSeq :: Seq -> [Seq]
extendSeq base@(x:y:ys) =
    case (x, y) of
        ('4', '4') -> ['7':base]
        ('7', '7') -> ['4':base]
        (_,     _) -> ['4':base, '7':base]

extendSolution :: Solution -> Solution
extendSolution = concatMap extendSeq

solutionsList :: [Solution]
solutionsList = iterate extendSolution seed

showSolution :: Solution -> String
showSolution = unwords

showSolutions :: [Solution] -> String
showSolutions = unlines . map showSolution

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

fibs2 = map (*2) fibs

main = putStr . unlines . take 12 . map show . zip (drop 3 fibs2) . map length $ solutionsList

Вывод:

(4,4)
(6,6)
(10,10)
(16,16)
(26,26)
(42,42)
(68,68)
(110,110)
(178,178)
(288,288)
(466,466)
(754,754)

Таким образом, как минимум первые члены ряда описываются формулой A(n) = 2*F(n+1), где F(n) - n-ый член ряда Фибоначчи

Playground: https://repl.it/repls/WarpedDarkgreenIbisbill