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