Бесконечность простых чисел-близнецов

[vorvalm]

k=14 s=50 B={0 2 6 8 12 18 20 26 30 32 36 42 48 50}
k=14 s=50 B={0 2 8 14 18 20 24 30 32 38 42 44 48 50}

Проверил проходимость этих кортежей.
Первый представляет простые числа от 11 до 61.
Не проходит по модулю $p=7$
Существует в единственном экземпляре .
Второй не проходит даже по модулю $p=3$ и
не существует среди простых чисел

[Skipper]

vorvalm в сообщении #1402047 писал(а):

k=14 s=50 B={0 2 6 8 12 18 20 26 30 32 36 42 48 50}
k=14 s=50 B={0 2 8 14 18 20 24 30 32 38 42 44 48 50}

Проверил проходимость этих кортежей.
Первый представляет простые числа от 11 до 61.
Не проходит по модулю $p=7$
Существует в единственном экземпляре .

Что то не совпаадает. А я в файлике вижу, что первый не в единственном экземпляре, и после
кортежа начинающегося с $11$ ,
следует - кортеж начинающийся, с $21817283854511261$ . (сам не проверял, смотрю что в файле нагенерировали раньше. )

-- Пт июн 28, 2019 16:08:15 --

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

Например для указанного мной выше паттерна длиной 24 и диаметром 100 среди последовательных 200 миллиардов чисел возможны лишь 640 вариантов кортежа, их и надо проверить на простоту входящих в кортеж чисел. И проверив всего лишь $640\cdot24=15360$ чисел на простоту мы исключаем весь интервал в 200 миллиардов. А моя программа использует и ещё бОльшие интервалы, например для этого паттерна интервал проверки составил $615\cdot10^{15}$, в котором проверяется менее 100 миллионов кортежей. Программа активно пользуется AVX2 (кусок написан на асме) и проверяет в среднем больше миллиарда кортежей в секунду (4 ядра на 3.5ГГц), что для этого паттерна даёт более $3\cdot10^{22}$ чисел в час.

Ого, ну так это замечательно! Мы на пороге сенсационного открытия - надо перебрать дальше, до $10^{30}$ и больше, и доказать, что кортеж случается на больших числах. ( $24 $ простых числа на отрезке $100$ ) !
Там где простые числа редко появляются.

А вот, с малыми числами, где простые очень плотно расположены, данного случая не существует - по всем возможным кортежам ("правильным", определение давал выше - т.е. которые могут появляться более одного раза) .
Это согласитесь, изумительный случай!

Ну а если нету.. такого кортежа и на больших числах тоже, хотя он, как вы говорите "проходимый", то может быть,
мы опровергнем первую гипотезу Харди-Литтлвуда ?

PS Да, и хотелось бы понять, как .. для паттерна длиной 24 и диаметром 100 среди последовательных 200 миллиардов чисел возможны лишь 640 вариантов кортежа -
так я с такими знаниями тоже написал бы быстрые программы проверок, и может быть, запустил бы их на своём компьютере
хоть на месяц.

[Dmitriy40]

Skipper в сообщении #1402056 писал(а):

Да, и хотелось бы понять, как .. для паттерна длиной 24 и диаметром 100 среди последовательных 200 миллиардов чисел возможны лишь 640 вариантов кортежа

Ну давайте разберём на конкретном примере, возьмём паттерн 0,2,6,8,12, моя программа утверждает что первое число в кортеже должно быть $2\pmod 3$, $1\pmod 5$, $3\, \text{или}\, 4\pmod 7$, т.е. при делении на 3 остаток может быть лишь 2, при делении на 5 лишь 1, а при делении на 7 остатки могут быть 3 или 4. Все остальные варианты остатка первого числа кортежа недопустимы. Запишем проверяемый кортеж как $p_0,p_1=p_0+2,p_2=p_0+6,p_3=p_0+8,p_4=p_0+12$ и проверим утверждение о недопустимости:
а) если $p_0 \bmod 3 = 1$, то $p_1=p_0+2=1+2 \pmod 3=0 \pmod 3$ - т.е. тогда второе число делится на 3 (впрочем и четвёртое тоже);
б) если $p_0 \bmod 5 = 2$, то $p_3=p_0+8=2+8 \pmod 5=0 \pmod 5$ - т.е. четвёртое число делится на 5;
в) если $p_0 \bmod 5 = 3$, то $p_1=p_0+2=3+2 \pmod 5=0 \pmod 5$ - т.е. второе число делится на 5 (и четвёртое тоже);
г) если $p_0 \bmod 5 = 4$, то $p_2=p_0+6=4+6 \pmod 5=0 \pmod 5$ - т.е. третье число делится на 5;
д) если $p_0 \bmod 7 = 1$, то $p_2=p_0+6=1+6 \pmod 7=0 \pmod 7$ - т.е. третье число делится на 7;
е) если $p_0 \bmod 7 = 2$, то $p_4=p_0+12=2+12 \pmod 7=0 \pmod 7$ - т.е. пятое число делится на 7;
ж) если $p_0 \bmod 7 = 5$, то $p_1=p_0+2=5+2 \pmod 7=0 \pmod 7$ - т.е. второе число делится на 7;
з) если $p_0 \bmod 7 = 6$, то $p_3=p_0+8=6+8 \pmod 7=0 \pmod 7$ - т.е. четвёртое число делится на 7.
Плюс можно проверить что для указанных выше допустимых остатков ни одно из 5-ти чисел ни на 3, ни на 5, ни на 7 не делится.

Теперь подсчитаем сколько же чисел мы оставили из всего диапазона $2\cdot3\cdot5\cdot7=210$ чисел: половина остаётся по модулю 2, потом от неё треть по модулю 3, потом одна пятая по модулю 5, и в финале две седьмых по модулю 7, итого $210(1/2)(1/3)(1/5)(2/7)=2$ - из любых последовательных 210 чисел проверять надо лишь два варианта кортежей. Чтобы самому руками не париться с китайской теоремой об остатках, пойдём в Wolfram и заставим париться его, он выдаст наши два варианта (для второго исправить тройку на четвёрку в задании) для остатка для первого числа кортежа: $11 \,\text{и}\, 101\pmod{210}$.
Итак, в любом интервале из 210 последовательных чисел выбираем лишь два, остаток от деления которых на 210 будет 11 или 101 и начиная с него проверяем на простоту лишь 5 чисел с заданными паттерном разностями. Я обычно начинаю с первого и последнего, это часто сразу отвергает кортеж.

Воспользуемся программой PARI/GP для проверки:

{
p=Set([0,2,6,8,12]);
start=round(1); stop=start+round(1e5);
pp=vecsum(p); n=#p;
v=vector(n,x,0);
print(start,"..",stop,":",p);
forprime(i=start, stop,
   v=concat(v[2..n], [i]);
   if((vecsum(v)==pp+n*v[1]),
      if(v-vector(n,x,v[1])==p, print("n=",n,", ",v[1],": ",p););
   );
);
}
1..100001:[0, 2, 6, 8, 12]
n=5, 5: [0, 2, 6, 8, 12]
n=5, 11: [0, 2, 6, 8, 12]
n=5, 101: [0, 2, 6, 8, 12]
n=5, 1481: [0, 2, 6, 8, 12]
n=5, 16061: [0, 2, 6, 8, 12]
n=5, 19421: [0, 2, 6, 8, 12]
n=5, 21011: [0, 2, 6, 8, 12]
n=5, 22271: [0, 2, 6, 8, 12]
n=5, 43781: [0, 2, 6, 8, 12]
n=5, 55331: [0, 2, 6, 8, 12]

Проверим остатки найденных чисел на 210: $1481=11\pmod{210}$, $16061=101\pmod{210}$, $19421=101\pmod{210}$, $21011=11\pmod{210}$, $22271=11\pmod{210}$, $43781=101\pmod{210}$, $55331=101\pmod{210}$. Плюс проверим почему отбросились например кортежи 221:0,2,6,8,12 (5 чисел начиная с $221=11\pmod{210}$) и 311:0,2,6,8,12: дык 221 делится на 11 и 13, т.е. уже оно не простое; 311, 313, 317 простые, но 319 не простое, делится на 11 и 29.
Как видим всё совпадает, за исключением самого первого решения начиная с числа 5 - это да, артефакт, в начале числового ряда встречаются уникальные кортежи, не подпадающие под формулу остатков, их надо проверять отдельно, но это возможно лишь до модуля (210), дальше всё чётко.

(Оффтоп)

Разумеется в программе используется большее количество простых, например для этого паттерна добавление проверок по модулю 11 увеличивает диапазон в 11 раз, а количество допустимых кортежей растёт лишь в 6 раз, т.е. добавление ещё одного простого числа ускоряет проверку почти вдвое. Для того паттерна выше диаметром 100 программа использует проверку на все первые простые по 47 включительно, что и даёт интервал 615 квадриллионов ($2\cdot3\cdot5\cdot7\cdot11\cdot13\cdot17\cdot19\cdot23\cdot29\cdot31\cdot37\cdot41\cdot43\cdot47\approx615\cdot10^{15}$), но разных остатков для первого числа в кортеже допустимо лишь чуть меньше 96 миллионов, ускорение проверки примерно в 6 миллионов раз (все 24 числа кортежа проверять на простоту не нужно, для отбрасывания кортежа обычно хватает одного-двух). Ещё два-три порядка ускорения даёт использование ассемблера и AVX2. Памяти при этом хапнула 1.5ГБ, причём вся она постоянно читается, что иногда и ограничивает скорость.

[vorvalm]

Skipper в сообщении #1402056 писал(а):

Что то не совпаадает. А я в файлике вижу, что первый не в единственном экземпляре, и после
кортежа начинающегося с $11$ ,

Извиняюсь. Повторно проверил и действительно первый кортеж проходит по всем модулям

[wrest]

(Dmitry40, китайская теорема об остатках в PARI/GP)

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

Чтобы самому руками не париться с китайской теоремой об остатках, пойдём в Wolfram и заставим париться его
,

Хозяйке на заметку:
? lift(chinese([Mod(1,2),Mod(2,3),Mod(1,5),Mod(3,7)]))
%1 = 101

[Dmitriy40]

(Оффтоп)

wrest
Спасибо, я помню что в PARI/GP оно есть, но не помнил точного названия и формата вызова, запускать gp_refcard.pdf и искать было лень, а вольфрам есть близко в закладках браузера именно с готовой формулой.

[vicvolf]

Новая интересная статья на данную тему https://arxiv.org/abs/1908.08613

[Skipper]

при условии истинности обобщенной гипотезы Эллиота — Халберстама, существует бесконечно много пар последовательных простых чисел, отличающихся не более чем на 6.

Но доказать это пока не может никто? А уж гипотеза о том что бесконесно много простых чисел-близнецов значит, ещё труднее, её на данный момент непонятно как доказывать и вообще в какую сторону думать..

Но вот что интересно. Есть ли какие то, так сказать, косвенные данные, которые свидетельствуют о том, что численность простых чисел-близнецов - бесконечна (или наоборот, конечна) ?
Ну к примеру, что нибудь такое "если численность простых чисел близнецов конечна, то неверна была бы ОГР", или тому подобное. Есть гипотезы, в которые большинство математиков верят и без доказательства, или точнее, допускают бОльшую вероятность одного из вариантов. А тут чему верить? Если более вероятно что численность простых-чисел близнецов все таки вероятнее, бесконечна, то на каком основании ?

[vicvolf]

Skipper в сообщении #1424006 писал(а):

[i]Но вот что интересно. Есть ли какие то, так сказать, косвенные данные, которые свидетельствуют о том, что численность простых чисел-близнецов - бесконечна (или наоборот, конечна) ?

Первая гипотеза Харди -Литтлвуда http://mathworld.wolfram.com/k-TupleConjecture.html подтверждается с большой точностью. Из нее в частности следует бесконечность простых близнецов.

[Skipper]

vicvolf в сообщении #1424091 писал(а):

Первая гипотеза Харди -Литтлвуда http://mathworld.wolfram.com/k-TupleConjecture.html подтверждается с большой точностью.

А как её "подтверждают" ? Если по русски, а то по английски очень напряжно что то читать.

[vicvolf]

Skipper в сообщении #1424196 писал(а):

А как её "подтверждают" ?

А Вы подсчитайте количество простых близнецов по формуле указанной в ссылке для $x=10^7-10^{12}$ и сопоставьте с реальным значением количества близнецов на данных интервалах.

[Dmitriy40]

vicvolf в сообщении #1424301 писал(а):

А Вы подсчитайте количество простых близнецов по формуле указанной в ссылке для $x=10^7-10^{12}$

Я подсчитал:
$10^1: 2$
$10^2: 8$
$10^3: 35$
$10^4: 205$
$10^5: 1224$
$10^6: 8169$
$10^7: 58980$
$10^8: 440312$
$10^9: 3424506$
$10^{10}: 27412679$
$10^{11}: 224376048$
$10^{12}: 1870585220$
А дальше есть в A007508.

[vicvolf]

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

Я подсчитал:
$10^1: 2$
$10^2: 8$
$10^3: 35$
$10^4: 205$
$10^5: 1224$
$10^6: 8169$
$10^7: 58980$
$10^8: 440312$
$10^9: 3424506$
$10^{10}: 27412679$
$10^{11}: 224376048$
$10^{12}: 1870585220$
А дальше есть в A007508.

Спасибо за большую точность вычислений. Это конечно с округлением до целых. Интересно сколько знаков после запятой вы брали при вычислениях в постоянной $C_2$ и интеграле?

Количество простых близнецов на интервале от $2$ до $x$ в первой гипотеза Харди-Литтлвуда определяется по формуле:

$\pi_2(x) =C_2 \int_2^x {\frac {dt} {\log^2(t)}}$, (1)

где $C_2$ - постоянная. При $x \to \infty$ интеграл (1) расходится и отсюда следует бесконечность простых близнецов.

Интересно, что для обоснования данной гипотезы авторами была использована вероятностная модель и получена такая высокая точность.

Вот еще интересная ссылка на данную тему http://mathworld.wolfram.com/PrimeConstellation.html

[Dmitriy40]

vicvolf в сообщении #1424678 писал(а):

Спасибо за большую точность вычислений. Это конечно с округлением до целых. Интересно сколько знаков после запятой вы брали при вычислениях в постоянной $C_2$ и интеграле?

Вы не поняли или я плохо пояснил, это точные значения количества близнецов. Не по формулам, а прямым подсчётом. Соответственно никаких округлений нет. И сравнивать свои выкладки (интеграла или ещё какие) надо именно с этими цифрами.

[vicvolf]

vicvolf в сообщении #1424678 писал(а):

Количество простых близнецов на интервале от $2$ до $x$ в первой гипотеза Харди-Литтлвуда определяется по формуле:

$\pi_2(x) =C_2 \int_2^x {\frac {dt} {\log^2(t)}}$, (1)

где $C_2$ - постоянная. При $x \to \infty$ интеграл (1) расходится и отсюда следует бесконечность простых близнецов.

Интересно, что для обоснования данной гипотезы авторами была использована вероятностная модель и получена такая высокая точность.

Вот еще интересная ссылка на данную тему http://mathworld.wolfram.com/PrimeConstellation.html

В данной ссылке, подсчитанное по формуле (1) количество простых близнецов для $x=10^5-10^8$ совпадает с реальным количеством простых близнецов.

Это связано с тем, что начиная с $x=10^5$ ошибка в вычислениях по данной формуле не превосходит ошибку округления до целого числа.

vicvolf в сообщении #1417050 писал(а):

Новая интересная статья на данную тему https://arxiv.org/abs/1908.08613

Данная статья, как раз посвящена использованию вероятностной модели гипотезы Харди-Литтлвуда к определению наибольшего расстояния между простыми числами.