Решение задачи №68 от UniLecs

two_digits.hs

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

fibs2 = map (*2) fibs

solution n = fibs2 !! n

main = print $ solution 8 
  -- > 68

Доказательство формулы:
Назовём последовательность из 4 и 7 фиксированной длины, в которой ни одна цифра не повторяется подряд более, чем два раза, валидной. Валидную последовательность, начинающуюся с 4, назовём 4-валидной (понятие 7-валидной вводится по аналогии). Найдём число 4-валидных последовательностей длины n. Для небольших n это число V4(n) можно найти полным перебором:

V4(1) = 1 (4)
V4(2) = 2 (44, 47)
V4(3) = 3 (447, 474, 477)

Теперь допустим, что нам известно V4(n), и мы хотим найти V4(n+1). Для этого возьмём все 4-валидные последовательности длины n и будем приписывать цифру в конце. Вне зависимости от конкретного содержания всегда можно из 4-валидной последовательности получить 4-валидную последовательность длиной на единицу больше, если приписать цифру, отличную от цифры на конце. Когда же можно приписать цифру, совпадающую с конечной? Очевидно, когда две последние цифры различны. Число 4-валидных последовательностей длины n, две последние цифры которой различны, равно V4(n-1), т. к. такую последовательность можно получить из любой 4-валидной последовательности длины n-1, просто приписав цифру, отличную от конечной. Т. о.,
V4(n+1) = V4(n) + V4(n-1),
то есть с точностью до индексов совпадает с последовательностью чисел Фибоначчи. V4(n) = F(n+1), где F(n) - n-ое число Фибоначчи (F(1) = 1, F(2) = 1).
Теперь рассмотрим преобразование f: 4 -> 7, 7 -> 4. Если к каждой цифре 4-валидной последовательности применить f, получим 7-валидную последовательность, и наоборот. Т. к. это преобразование, очевидно, взаимно однозначное, получаем, что V4(i) = V7(i), а т. к. сумма количеств 4-валидных и 7-валидных последовательностей заданной длины равно количеству валидных последовательностей заданной длины, получаем, что для длины n их число задаётся формулой 2*V4(n) = 2*F(n+1), что и требовалось доказать.

Функция fibs возвращает бесконечный список чисел Фибоначчи. Функция fibs2 возвращает бесконечный список удвоенных чисел Фибоначчи. Оператор индексации !! возвращает n+1 элемент списка (т. к. индекс начинается с нуля).