Существуют ли формулы проверки числа на простоту?

[Decorator]

Я маленько по другому все делаю. Вот рисуночки на страничке:

http://primality-proving.narod.ru/risunki.htm

[worm2]

Хотел усилить тест, скрестив его с Кармайклом. Но, к моему удивлению, среди чисел, "псевдопростых по Decorator" (можно, я их так буду называть?), меньших миллиона, 4 одновременно являются числами Кармайкла (252601=41*61*101, 399001=31*61*211, 512461=31*61*271, 852841=11*31*41*61). И это при том, что чисел Кармайкла, меньших миллиона, всего 43, а чисел, "псевдопростых по Decorator" --- 93. Это явно неспроста.
Чую, резвиться нам здесь ровно до того момента, как придёт maxal и всё разложит по полочкам.

[Someone]

Decorator писал(а):

Вообще я случайно этот тест придумал.

Видимо, это какой-то вариант критерия Лукаша - Лемера. Ссылки на первоисточник не знаю, но тест описан у Д.Кнута, в упражнении 4.5.4-15. В ответе к упражнению есть и пример, как раз с числами Фибоначчи.

Д.Кнут. Искусство программирования для ЭВМ. Том 2. Получисленные алгоритмы. "Мир", Москва, 1977.

[Decorator]

Не могли бы Вы посмотреть Excel файл, на который ниже я дам ссылку? Там собственно визуальная часть моих "исследований" представлена. Может быть у Вас получится найти в этом новый математический смысл?

http://primality-proving.narod.ru/chisla.xls

Для каждого простого числа n я выстроил в Excel последовательность, где: a1 = 1, a2 = 1, a3 = (a1+a2)-(MOD(a1+a2)/n)*n и так далее…
Оказалось, что распределение чисел в таких рядах циклично и особенно интересно для простых чисел оканчивающихся на 3 и 7.
Цикл равняется (n+1)*2. В каждом цикле 2 симметричных полуцикла. Исходя из этого можно рисовать интересные картинки.
Еще интересно, что есть уникальные простые числа, у которых длина цикла меньше чем (n+1)*2. Таких чисел очень мало. Вот эти числа в диапазоне 1000: 47, 107, 307, 347, 557, 677, 797, 967, 977. 113, 233, 263, 353, 563, 743, 953.

[ИСН]

Пизанские периоды, однако.
http://mathworld.wolfram.com/PisanoPeriod.html
Что значит "цикл равняется..."? Период его равняется 2(p+1)? Так это не так: для многих простых период гораздо меньше, во много раз. Скажем, p=233 - период сколько?

[Руст]

ИСН писал(а):

Пизанские периоды, однако.
http://mathworld.wolfram.com/PisanoPeriod.html
Что значит "цикл равняется..."? Период его равняется 2(p+1)? Так это не так: для многих простых период гораздо меньше, во много раз. Скажем, p=233 - период сколько?

Забавно. Согласно этой ссылке в wolfram не знают, что период вычисляется как НОК периодов по делителям числа n, являющиеся степенями простых чисел. И форма для периодов таких степеней.

[ИСН]

Покажите мне, где это знают (в смысле, факт-то очевидный, но вот где про это написано)?
И чуть менее банальный факт, что ноль на периоде встречается либо 1, либо 2, либо 4 раза - тот же самый вопрос. (Это я где-то видел написанным, думал - у Вольфрама, ан нет.)

[Руст]

Факты очевидные. $(p+\frac p5 )|n\to p|F_n$. Однако, когда 5 не квадратичный вычет F_p даёт остаток -1 при делении на p, соответственно по модулю p числа Фибоначчи полностью повторяются только через 2(p+1). Хотя для делимости вышеуказанная формула работает. Существуют ли простые числа типа Вивериха, когда F(p+(p/5)) делится сразу на квадрат р не знаю.

[maxal]

Руст писал(а):

Факты очевидные. $(p+\frac p5 )|n\to p|F_n$.

Должно быть: $(p-\left(\frac p5\right) )|n\to p|F_n$.

Руст писал(а):

Существуют ли простые числа типа Вивериха, когда F(p+(p/5)) делится сразу на квадрат р не знаю.

Соответственно, должно быть F(p-(p/5)). Меньше 10^6 таких простых нет.

[maxal]

Руст писал(а):

Однако, когда 5 не квадратичный вычет F_p даёт остаток -1 при делении на p, соответственно по модулю p числа Фибоначчи полностью повторяются только через 2(p+1).

Это утверждение неверно. Например, по модулю $p=47$ период чисел Фибоначчи равен 32, а не $2(p+1)=96$. Хотя, конечно, 32 является делителем 96.

[maxal]

maxal писал(а):

Руст писал(а):

Существуют ли простые числа типа Вивериха, когда F(p+(p/5)) делится сразу на квадрат р не знаю.

Соответственно, должно быть F(p-(p/5)). Меньше 10^6 таких простых нет.

Такие простые носят имя Уолла-Сана-Сана (Wall-Sun-Sun) по фамилиям трех человек (двое из которых - братья-близнецы), впервые описавших такие простые применительно к ВТФ. Существование простых Уолла-Сана-Сана на данный момент является открытой проблемой. Известно только, что минимальное такое простое (если существует) обязано быть больше $10^{14}.$
Несуществование простых Уолла-Сана-Сана эквивалентно тому, что для каждого простого числа $p$ существует число Фибоначчи делящееся на $p$, но не делящееся на $p^2$.

[Руст]

Проверка на простоту числа нечётного числа n в поле $Q[\sqrt D]$, где D берётся из условия $(\frac{D}{n})=-1$, оказывается удивительно эффективной. Найти контрпример - составное n, прошедшего всего один тест на простоту, становится очень сложной. Так как об этом уже немного обсуждали в олимпиадном разделе, я напишу об этом тесте там.

[sk1994]

Да, есть. К примеру можно написать программу (в Паскале, например). Сначала проверяется число на четность, если нечетное, то делится по очереди на 3, 5, 7, 11 и т.д., так чтобы d^2<=n, где d - делитель, а n - исходное. Тогда, если n - составное, то n |mod d| = 0, иначе n - простое.

[Nataly-Mak]

Ну, программ для генерирования простых чисел уже написано немало.
Реализованы и решето Эратосфена, и решето Сундарама, и решето Аткина.

Чтобы проверить число $n$ на простоту по предложенному вами способу, надо знать все простые делители $d$ такие, что d^2<=n.

У меня есть очень простенькая программка, в которой реализовано решето Сундарама. Программка приведена в Википедии (в обсуждении статьи "Решето Сундарама"; у меня несколько другой вариант реализации, нежели предложенный в статье):
http://ru.wikipedia.org/wiki/%D0%9E%D0% ... 0%BC%D0%B0
В этой программе не надо знать простые делители. Кроме того, она очень удобна тем, что генерирует числа в заданном интервале, а не только с начала натурального ряда. Я сама часто пользуюсь этой программой генерации простых чисел. Для не очень больших чисел она вполне годится. Недавно мне понадобились простые числа от 16000 до 200000. Довольно быстро сгенерировала.

[Nataly-Mak]

А вот у меня такая задачка о простых числах:
требуется найти семь арифметических прогрессий длины 7 (то есть из 7 членов) с одинаковой разностью таких, что их первые члены тоже образуют арифметическую прогрессию.

Пример арифметической прогрессии из простых чисел длины 7: 7 + 150n, n = 0, 1, ..., 6.

Имеет ли решение эта задача?