Факторизация чисел Фибоначчи
Факторизация чисел Фибоначчи
Давайте теперь рассмотрим несколько иной пример. Попытаемся факторизовать числа такой последовательности, которая не может рассматриваться как некоторое тривиальное изменение последовательности аn с целым основанием а. В качестве такой последовательности можем выбрать, например, последовательность Фибоначчи. Напомним, что последовательность Фибоначчи рекуррентно определяется так:
F1 = F2 = 1, Fn+2 = Fn+1 +Fn.
Если Fn — простое, то либо n = 4, либо n — простое. Теперь построим таблицу факторизации чисел Фибоначчи.
Для этого напишем программу, в которой предусмотрим вывод не только разложения числа Фибоначчи, но и самого числа.
Do[Print[n,":",Fibonacci[n]], ":",
FactorInteger[Fibonacci[n]]],{n,270}]
Данная таблица недаром содержит числа Фибоначчи Р„ для п вплоть до 300. Дело в том, что до 1963 года (а это совсем недавно с точки зрения многотысячелетней истории теории чисел) было известно, что числа ФибоначчиFn являются простыми для n = 3, 4, 5, 7, 11, 13, 17, 23, 29, 43, 47. Упорные же поиски других простых чисел Фибоначчи в то время никаких результатов не дали. Так что с этой точки зрения наша таблица содержит несколько совсем нетривиальных открытий!
