Повышенная частота простых чисел

[Побережный Александр]

Интересное наблюдение!
В последовательности чисел $n^2+n-1$ наблюдается повышенная частота простых чисел.
Причем, если $n$ заканчивается на $2$ и $7$, то получаются заведомо составные числа.

[wrest]

Побережный Александр в сообщении #1424621 писал(а):

Причем, если $n$ заканчивается на $2$ и $7$, то получаются заведомо составные числа.

Так ведь они все, внезапно, делятся на $5$

[venco]

Побережный Александр в сообщении #1424621 писал(а):

В последовательности чисел $n^2+n-1$ наблюдается повышенная частота простых чисел.

Эти числа никогда не делятся ни на 2, ни на 3.
И вообще, делителями могут быть только простые с квадратичным вычетом 5: $\{5,11,19,29,31,...\}$.

[victor.l]

используйте эквивалентную форму $n^2+5n+5$ чтобы от пятерок избавится.

[Утундрий]

victor.l в сообщении #1424674 писал(а):

используйте эквивалентную форму $n^2+5n+5$ чтобы от пятерок избавитЬся.

$n=5$

[Побережный Александр]

Множество чисел, которые не делятся на 2 и на 3 можно записать формулой
$\frac{(6n-3+(-1)^n)}{2}$, где n принимает натуральные значения.
Я сравнил количество простых, появляющихся при пробегании n от 1 до 115 в обоих случаях.
По формуле $n^2+n-1$ сгенерируется 58 простых чисел.
По формуле $\frac{(6n-3+(-1)^n)}{2}$ сгенерируется 69 простых чисел. Это максимально возможное число.
Как себя ведут эти последовательности для больших n ничего сказать не могу.

[Andrey A]

Побережный Александр в сообщении #1425115 писал(а):

Как себя ведут эти последовательности для больших n ничего сказать не могу.

Если $f_a=a^2+a-1$ делится на простое $p$, то для всех $n=a+kp$ $f_n$ также делится на $p$. Простые могут быть вида $10k\pm 1$ и $5$. Грубо говоря, половина всех простых (вида $10k\pm 3$) не могут быть делителями $f_n$, однако упорядочить номера простых $f_n$ не легче, чем упорядочить номера простых в натуральном ряду.

[Dmitriy40]

Побережный Александр в сообщении #1425115 писал(а):

Множество чисел, которые не делятся на 2 и на 3 можно записать формулой
$\frac{(6n-3+(-1)^n)}{2}$, где n принимает натуральные значения.
Я сравнил количество простых, появляющихся при пробегании n от 1 до 115 в обоих случаях.
По формуле $n^2+n-1$ сгенерируется 58 простых чисел.
По формуле $\frac{(6n-3+(-1)^n)}{2}$ сгенерируется 69 простых чисел.

У меня меньше в обоих случаях (заодно покажу для $n=1..10^6$):

? s=0;for(n=1,115,if(isprime(n^2+n-1),s++));print(s)
53
? s=0;for(n=1,115,if(isprime((6*n-3+(-1)^n)/2),s++));print(s)
66
? s=0;for(n=1,10^6,if(isprime(n^2+n-1),s++));print(s)
139484
? s=0;for(n=1,10^6,if(isprime((6*n-3+(-1)^n)/2),s++));print(s)
216814

Вы взяли полное количество простых (ещё и 1 видимо посчитали простым), но ваша формула не выдаёт чисел 2 и 3, потому и меньше.

-- 11.11.2019, 01:59 --

Побережный Александр в сообщении #1425115 писал(а):

Это максимально возможное число.

Это собственно тоже неверно. Да, выдать количество простых больше чем оно реально есть конечно невозможно, но ведь формула $n^2+n-1$ для $n=1..115$ выдаёт числа в интервале $1..13339$, в котором есть 1585 простых. Так что среди первых 115 значений некоей формулы точно простых может быть и все 115 (для $n^2+n-1$ это конечно не так, но в принципе-то можно попытаться перенумеровать хоть все простые в некотором диапазоне).
Так что результат 53 из 115 не такой уж и большой.

Например формулы $6n-1$ и $30n-1$ для $n=1..115$ дают по 64 простых, уже больше вашей с квадратом.
А формула из вики $4n^2-2n+41$ для $n=1..115$ даёт 87 простых.
Полином Эйлера $n^2+n+41$ для $n=1..115$ даёт и вовсе 98 простых!

[Побережный Александр]

Dmitriy40 в сообщении #1425155 писал(а):

А формула из вики $4n^2-2n+41$ для $n=1..115$ даёт 87 простых.
Полином Эйлера $n^2+n+41$ для $n=1..115$ даёт и вовсе 98 простых!

Уважаемый Dmitriy40, можно ли просчитать, как ведут себя полином Эйлера и формула из вики, когда $n$ пробегает значения до $10^6$. Чтобы сравнить с предыдущими вычислениями.

[Dmitriy40]

Побережный Александр
Легко:

? s=0;for(n=1,10^6,if(isprime(n^2+n+41),s++));print(s)
261080
? s=0;for(n=1,10^6,if(isprime(4*n^2-2*n+41),s++));print(s)
247349

[Побережный Александр]

Dmitriy40 в сообщении #1425637 писал(а):

Побережный Александр
Легко:

? s=0;for(n=1,10^6,if(isprime(n^2+n+41),s++));print(s)
261080
? s=0;for(n=1,10^6,if(isprime(4*n^2-2*n+41),s++));print(s)
247349

Dmitriy40, спасибо за поддержку в вычислениях!
Как я понимаю, появление простых чисел в полиномах сравнимы, если учесть то, что в моем трехчлене каждое пятое число выдает заведомо составное число, делящееся на пять.

[Dmitriy40]

Ну как сравнимы, Ваша формула выдаёт вдвое меньше простых (13.9% против 26.1%), а в остальном да, можно сказать что сравнимы, учитывая что обе они выдали меньше 0.0007% от всех 37.6 млрд простых в диапазоне до $10^{12}$.
Но частота да, повышена, аж целых 13.9% вместо 3.8% при полностью случайном выборе миллиона чисел из диапазона $10^{12}$ (хотя уже исключение чётных и кратных 3 даёт частоту практически равную вашей, 11.3%, а исключив ещё и кратные 5 получим частоту 14.1%).
Так что для меня смысл всей темы разве что в удивительной простоте формулы, "выкидывающей" (в смысле равенства вероятностей при случайном выборе попасть на простое) из всех чисел кратные 2, 3 и 5. Более никакого смысла не замечаю.