?

Log in

No account? Create an account

Просто числовое - Общество дровосеков Бердичева по изучению Мишны

Jan. 19th, 2012

10:59 am - Просто числовое

Previous Entry Share Next Entry

Сегодня На днях я узнал о существовании последовательности, которая строится очень простым образом:
P(n) = P(n-2)+P(n-3) - эдакая тормозная последовательность Фибоначчи - и если ее начать с чисел
3, 0, 2, нумеруя элементы, начиная с нуля, то если P(n) не делится на n, то число n обязательно составное.
Начинается она так: 3, 0, 2, 3, 2, 5, 5, 7, 10, 12, 17, 22, 29, 39, 51, 68, 90, 119 (выделены элементы, кратные простым числам)

К сожалению, мироздание не может обойтись без шуток, и обратное не верно: хотя практически все n, для которых P(n) кратно n - простые, попадаются и "ошибки природы".

Их всего 2 в первом миллионе (271441 и 904631), и 17 в первом миллиарде. Но какая же досада!

Comments:

[User Picture]
From:ny_quant
Date:January 20th, 2012 04:27 am (UTC)
(Link)
Удивительно. Не хуже скатерти Улама.
(Reply) (Thread)
[User Picture]
From:janatem
Date:January 20th, 2012 08:49 am (UTC)
(Link)
Нельзя ли этот факт применить на практике? Например, для проверки на непростоту. Я пытаюсь оценить сложность такой проверки (будет ли она проще наивной факторизации) — для нахождения P(n) достаточно уметь вычислять экспоненту и логарифм с заданной точностью (чтобы потом, округлив до целого, получить ответ).
(Reply) (Thread)
[User Picture]
From:spamsink
Date:January 20th, 2012 03:13 pm (UTC)
(Link)
Это тоже получается вероятностная проверка, но гораздо более дорогая, чем с помощью малой теоремы Ферма.
(Reply) (Parent) (Thread)
[User Picture]
From:e_ponikarov
Date:January 20th, 2012 02:51 pm (UTC)
(Link)
Я в какой-то книге натыкался на идеологически близкий факт.
http://e-ponikarov.livejournal.com/13314.html
(Reply) (Thread)
[User Picture]
From:spamsink
Date:January 20th, 2012 03:12 pm (UTC)
(Link)
Красиво. И в этом случае тоже бывают псевдопростые числа?
(Reply) (Parent) (Thread)
[User Picture]
From:e_ponikarov
Date:January 20th, 2012 03:49 pm (UTC)
(Link)
Если меня не подводит память, в книге было упомянуто выражение "в точности", то есть это должно быть ровно множество простых чисел.
(Reply) (Parent) (Thread)