5 число фибоначчи

Ответ от Ra[гуру]
1) Как уже выше говорилось, можно составить программу, которая это подсчитает. Во многих языках, к примеру python, tcl, lisp, встроенный целочисленный тип является "длинным". tcl процедура, вычисляющая число фибоначчи:
proc fib n {
set f0 0
set f1 1
while {$n > 0} {
incr n -1
set tmp [expr {$f0 + $f1}]
set f0 $f1
set f1 $tmp
}
return $f0
}
fib 2011
840735...очень длинное число из 420 цифр... 55589
Получается, что 5 не является делителем 2011-го числа фибоначчи, а остаток от деления будет равен 4.
2) Известно, что остатки от деления ряда чисел фибоначчи начиная со второго числа фибоначчи на некое натуральное число, есть периодическая последовательность. К примеру для числа 2 рядом остатков от деления будет 1 0 1 1 0 1 1 0 1, т. е. последовательность 1 0 1, период которой равен 3. Для числа 5 длина такой периодической последовательности будет равна 20.
20 чисел фибоначчи начиная со второго:
1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946
Последовательность остатков от деления на 5:
1 2 3 0 3 3 1 4 0 4 4 3 2 0 2 2 4 1 0 1
Остаток от деления 2011 на 20 равен 11, таким образом остаток от деления 2011-го числа фибоначчи на 5 будет 11-ым числом в последовательности остатков и будет равен 4.
Ответ: 4