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

[Decorator]

Спасибо что объяснили мне некоторые моменты. Если возникнут у меня вопросы, можно я к Вам обращусь? Спасибо за беседу...

[Руст]

Контрпримером является n=17*19.

[Decorator]

Вы ошибаетесь - при n=323. формула выдает 1. а должно быть - n-1, то есть 322

Добавлено спустя 3 минуты 22 секунды:

я имел ввиду - для признания простоты числа результатом должно было стать n-1 = 322, а в данном случае получается - 1. Вы наверное забыли, что результат 1 - подтверждение простоты чисел заканчивающихся на 1 и 9

[worm2]

У Вас получился замечательный тест!



К сожалению, как Руст и подозревал, он не является точным.
Но без компьютера это, действительно, проверить совершенно невозможно.
Среди чисел, не превосходящих 50000, всего 11 составных, которые этот тест определяет как простые:

4181=37*113
5777=53*109
6479=11*19*31
6721=11*13*47
10877=73*149
13201=43*307
15251=101*151
27071=11*23*107
34561=17*19*107
44099=11*19*211
47519=19*41*61

[Decorator]

Каюсь, мужики, лажа вышла. Но у меня не все еще потеряно. Есть одна думка прям щас ее реализую. Только получится у теста 2 условия. Так пойдет?

[worm2]

Только бы не пришёл maxal и не испортил всё, сказав, что это давно известно

[Someone]

В этом списке нет чисел, оканчивающихся на $3$. Наименьшее такое число есть $113573=137\cdot 829$.

[Decorator]

Признаю свое фиаско. Похоже, я проиграл эту битву
Поторопился, погорячился... Буду работать над ошибками

Добавлено спустя 6 минут 27 секунд:

Someone писал(а):

В этом списке нет чисел, оканчивающихся на . Наименьшее такое число есть .

И правда...

Вообще я случайно этот тест придумал. Работал над визуализацией Фибоначчи-подобных рядов. Вот визуально это и увидел (на картинке). А вообще, скажу Вам, потрясающие результаты получаются. В числовых рядах скрыты целые картины. Человечки, кресты, рыбы, символы, знаки. Как будто нарочно кто-то все это в числа внедрил Могу картинки выложить на страничку.

[Руст]

Уже имеются доказанные полиномиальной сложности тесты проверки на простоту. Сложность порядка (ln(n))^{12}. При справедливости гипотезы Римана есть тесты сложностью порядка (ln(n))^4. А линейный по сложности тест, годный для всех нечётных чисел, вряд ли существует.

[ИСН]

Decorator писал(а):

В числовых рядах скрыты целые картины.

Типа таких?

[Decorator]

И типа таких и совсем другие. А эти как получены?

[worm2]

Decorator писал(а):

Признаю свое фиаско. Похоже, я проиграл эту битву
Поторопился, погорячился... Буду работать над ошибками

Не расстраивайтесь. Всё равно Ваш тест очень хороший. По крайней мере, как мне кажется, среди таких же простых по форме тестов Ваш --- самый лучший.

[ИСН]

Так и получены: числа Фибоначчи по модулю n, $F_i$ по одной оси, $F_{i+1}$ по другой. Из них красивый фон для страницы можно сделать. Какая-никакая польза.
А сабжевый факт (вернее, его близкое следствие) мне представляется аналогом малой теоремы Ферма, но - кривым аналогом, с особой ролью пятёрки.

[worm2]

Вот здесь рассматривается что-то похожее.
Берут последовательность $L_1 = 1$, $L_2 = 3$, $L_n = L_{n-1} + L_{n-2}$. И в качестве теста на простоту $n$ рассматривают условие $L_n \equiv 1\pmod{n}$.

[Руст]

worm2 писал(а):

Не расстраивайтесь. Всё равно Ваш тест очень хороший. По крайней мере, как мне кажется, среди таких же простых по форме тестов Ваш --- самый лучший.

На счёт самый лучший - вы явно погорячились.
Ещё контрпримеров может быть больше 11 даже для n<50000. Я привёл только достаточное (а не необходимое) условие того, что n - контрпример.
Вообще этот тест аналогичен вычислению числа точек на некоторой эллиптической кривой над Z/pZ.