Эвристический метод нахождения некоторых простых близнецов

[Cantata]

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

Cantata в сообщении #1723260 писал(а):

Посмотрите, пожалуйста, такую формулу:

$33k^2+7425k\pm1: 365531$ - новый лидер.

Неожиданно! Спасибо, что посмотрели!

Посчитала соотношение между обеими формулами

k = 50\,000 - 100\,000 → +7.23\%
k = 1\,000\,000 → +8.36\%
k = 10\,000\,000 → +10.20\%

-- 26.04.2026, 21:23 --

Видим, что формула с 33 при росте k всё больше обгоняет первую формулу, если я правильно посчитала.

[Cantata]

В результате перебора вариантов для поиска новых формул, мы с Дипсик нашли следующие варианты, где,
по-видимому, ключевую роль играет гладкость коэффициентов.

Для $k\le 100,000$ найдено следующее количество простых близнецов:

63k(k+4225)\pm 1 : 5457
63k(k+2025)\pm 1 : 4413
63k(k+1225)\pm 1 : 4307
105k(k+3969)\pm 1 : 4173
66k(k+961)\pm 1 : 4013
93k(k+1225)\pm 1 : 3903

[Dmitriy40]

Все они весьма далеки от лидеров на первых 10млн $k$:
$63k^2+266175k\pm1: 289135$
$63k^2+127575k\pm1: 239414$
$63k^2+77175k\pm1: 231868$
$105k^2+416745k\pm1: 227634$
$66k^2+63426k\pm1: 216624$
$93k^2+113925k\pm1: 210362$

Как можно посчитать самостоятельно: идёте на сайт PARI/GP online, в нижнее текстовое поле вводите текст программы
n=0; for(k=1,10^5, x=63*k^2+266175*k; if(ispseudoprime(x-1) && ispseudoprime(x+1), n++); ); n
нажимаете ниже кнопку Evaluate with PARI и ждёте несколько секунд, сверяете результат 5457 со своим, он совпадает, меняете предел с 10^5 на 10^7 и снова жмёте кнопку и ждёте гораздо дольше (минуту-две), видите результат 289135. Повторяете для любых желаемых формул.

[Cantata]

Dmitriy40
Круто! Спасибо!

[tolstopuz]

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

$33k^2+7425k\pm1: 365531$ - новый лидер.

$3k^2+13005k\pm1: 397025$
(купил себе Ryzen 9 9950X, надо же его чем-то занять...)

[Cantata]

tolstopuz в сообщении #1723305 писал(а):

$3k^2+13005k\pm1: 397025$
(купил себе Ryzen 9 9950X, надо же его чем-то занять...)

Поздравляю!

У меня уже гипотеза появилась, связанная с расположением чисел в треугольной пирамиде.
Как раз думала, что 17 или 19 покажут лучший результат, чем 11.
Только пока не понимаю как комбинировать числа для максимальной эффективности формул.

[Dmitriy40]

tolstopuz

(Оффтоп)

tolstopuz в сообщении #1723305 писал(а):

(купил себе Ryzen 9 9950X, надо же его чем-то занять...)

Найдите такое примерно 27-значное простое $a$, чтобы все 20 чисел $a\cdot13\#\cdot2^{0\ldots9}\pm1$ ($13\#=30030$) были простыми. А то с 2008г, когда нашли 18 таких чисел, никакого продвижения. Но это архисложно. И возможно потребуются годы счёта даже на Вашем мощном процессоре.

[Cantata]

Дипсик помог определить, что единственные числа, удовлетворяющие

$$ \begin{cases} 8n + r = 6k - 1, \\ k - n = 1, \\ r \in \{1,3,5,7\}, \\ n,k \in \mathbb{Z}_{\ge 0} \end{cases} $$

это $p \in \{5,\ 11,\ 17\}$.

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

А может я тороплюсь с выводами?

[Cantata]

Внезапно улучшила свой результат, теперь вот такая формула:

$33k(k+715) \pm 1$ на $10^7$: $393\,421$ пара.

-- добавлено через 30 секунд --

Дипсик творит чудеса.

[tolstopuz]

Cantata в сообщении #1723362 писал(а):

$33k(k+715) \pm 1$ на $10^7$: $393\,421$ пара.

Я на нее тоже натыкался. И хотя я делал не совсем полный перебор, похоже, что при $a\le100$ и $b\le50000$ среди $ak^2+bk\pm1$ больше ничего достойного нет.

[Cantata]

tolstopuz в сообщении #1723374 писал(а):

Я на нее тоже натыкался. И хотя я делал не совсем полный перебор, похоже, что при $a\le100$ и $b\le50000$ среди $ak^2+bk\pm1$ больше ничего достойного нет.

Вполне возможно, что действительно больше ничего эффективного нет.
Но мы с Дипсиком подошли довольно хаотично к поиску, из-за чего накануне пропустили Вашу формулу-лидера, поэтому утверждать не берусь.
Я тут подумала, что моя формула это некоторая комбинация маленьких простых чисел до 13.
Напоминает анекдот про Неуловимого Джо - а почему он неуловимый, а потому, что его никто не ловит.
Вот и в моем случае, похоже, просто никто не искал такой вариант формулы, иначе давно бы уже нашли.

[Cantata]

Проверила на Pari GP несколько формул.
Предварительные результаты: указаны пары простых близнецов в разных диапазонах.

$$ \begin{array}{|l|r|r|} \hline \text{Формула} & \text{1--10 млн } k & \text{1--100 млн } k \\ \hline 3k^2 + 13005k \pm 1 & 397\,025 & 3\,005\,849 \\ 33k^2 + 23595k \pm 1 & 393\,421 & 3\,033\,194 \\ 33k^2 + 7425 \pm 1 & 365\,531 & 2\,816\,440 \\ 12k^2 + 2700k \pm 1 & 331\,719 & 2\,538\,416 \\ 18k^2 + 120 \pm 1 & 325\,151 & 2\,497\,291 \\ 18k^2 + 2430k \pm 1 & 319\,623 & 2\,458\,791 \\ 18k^2 + 3900k \pm 1 & 318\,735 & 2\,453\,187 \\ 30k^2 + 4650k \pm 1 & 317\,566 & 2\,451\,590 \\ \hline \end{array} $$

-- добавлено через 3 минуты --

И получилось проверить ещё несколько на большем диапазоне, но Pari GP вылетает и не получается всё посмотреть.

В таблице указаны пары простых близнецов в разных диапазонах:

$$ \begin{array}{|l|r|r|} \hline \text{Формула} & \text{1--150 млн } k & \text{1--200 млн } k \\ \hline 3k^2 + 13005k \pm 1 & 4\,308\,825 & 5\,567\,559 \\ 33k^2 + 23595k \pm 1 & 4\,362\,846 & 5\,645\,517 \\ \hline \end{array} $$

-- добавлено через 47 секунд --

Код использовала, написанный Дипсик:

{
    \\ Формула: 3k^2 + 13005k ± 1
    \\ Вычисляем количество простых чисел и пар близнецов
    \\ Диапазоны: 10M, 20M, 30M, 40M, 50M

    forstep(N = 10000000, 50000000, 10000000,
        prime_count = 0;
        twin_count = 0;

        for(k = 1, N,
            x = 3 * k^2 + 13005 * k;  \\ ИЗМЕНЁННАЯ ФОРМУЛА

            is_x_minus_1_prime = isprime(x - 1);  \\ Проверяем один раз, сохраняем результат
            is_x_plus_1_prime = isprime(x + 1);   \\ Проверяем один раз, сохраняем результат

            \\ Подсчёт простых чисел (каждое простое учитывается отдельно)
            if(is_x_minus_1_prime, prime_count++);
            if(is_x_plus_1_prime, prime_count++);

            \\ Подсчёт пар близнецов (оба числа простые)
            if(is_x_minus_1_prime && is_x_plus_1_prime,
                twin_count++
            );
        );

        print("=== k от 1 до ", N, " ===");
        print("Количество простых чисел: ", prime_count);
        print("Количество пар близнецов: ", twin_count);

        \\ Защита от деления на ноль
        if(prime_count > 0,
            ratio = twin_count * 100.0 / prime_count;
            print("Доля близнецов среди простых: ", ratio, "%");
        ,
            print("Доля близнецов среди простых: 0% (простых чисел не найдено)");
        );
        print("");
    );
}

[Rak so dna]

Cantata все эти ковыряния $k$ в окрестностях нуля не очень интересны. Проверьте окрестность какого-нибудь, скажем, $80$-ти значного числа $k$. Грубо говоря, шанс наугад взятого $160$-значного числа оказаться простым близнецом
$\approx\frac{1}{160^2}\approx 0,00004$
Поэтому, если ваша формула для $25000$ взятых наугад $80$-ти значных $k$ выдаст хотя бы с десяток
простых близнецов, то, возможно, что-то в ней и есть, а так...

[Cantata]

Rak so dna
Спасибо за участие в теме!
У меня обычный домашний компьютер, который не потянет такие вычисления.
Я даже Pari GP всё считаю онлайн :)

Стало интересно сравнить с универсальной формулой.
Хотя, конечно, не правильно сравнивать линейную последовательность с квадратичной.

При таком количестве k получены результаты:

$$ \begin{array}{|l|r|r|} \hline \text{Формула} & \text{Простых чисел} & \text{Пар близнецов} \\ \hline 6k \pm 1 & 31\,324\,702 & 2\,166\,300 \\ 3k^2 + 13005k \pm 1 & 34\,703\,634 & 3\,005\,849 \\ 33k^2 + 23595k \pm 1 & 34\,818\,060 & 3\,033\,194 \\ \hline \end{array} $$

-- добавлено через 3 минуты --

Чат-бот Алиса предполагает, что:

весьма вероятно, что формулы уже близки к пределу эффективности для квадратичных форм;
текущие лидеры уже достигают 8,4–8,7 процентов доли близнецов;
темп падения доли замедляется, указывая на стабилизацию;
теоретический максимум для квадратичных форм оценивается в 8,6–8,9 % на 100 млн, что всего на 0,2–0,5 п. п. выше текущих результатов.

Значит есть более эффективная формула

[Dmitriy40]

Cantata в сообщении #1723452 писал(а):

Код использовала, написанный Дипсик:

Этот код не очень быстр по трём причинам:
1. считается ещё и количество простых чисел, чего Вам совершенно не нужно (и это можно делать по другому и быстрее), т.е. второй раз вызывать isprime для второго числа в паре нужно намного реже чем для первого;
2. ispsrime лучше везде заменить на ispseudoprime, как и было у меня в коде, вторая быстрее, тем более для больших чисел (более 20 цифр);
3. для каждого N счёт начинается с начала, хотя большой кусок начальных k уже был посчитан для предыдущего N (например для N=50млн будут снова считаться k=1..40млн, которые уже были посчитаны для N=40млн, и так далее), в итоге вместо одного раза до 50млн будет посчитано 50+40+30+20+10=150млн, в 3 раза больше.
В итоге такой код работает в 3-4 раза медленнее показанного выше моего.
Если Вам зачем-то надо числа с шагом в 10млн, то лучше сделать так (показываю для шага 1млн, это быстрее):

? ss=step=10^6;\\С каким шагом выдавать результат
? n=0; for(k=1,10e6 /* докуда считать */, x=3*k^2+13005*k; if(ispseudoprime(x-1) && ispseudoprime(x+1), n++); if(k==ss, print(ss,": ",n); ss+=step; ););
1000000: 54495
2000000: 98439
3000000: 139950
4000000: 179486
5000000: 217453
6000000: 254539
7000000: 290807
8000000: 326602
9000000: 362102
10000000: 397025
time = 10,858 ms.

Cantata в сообщении #1723464 писал(а):

У меня обычный домашний компьютер, который не потянет такие вычисления.
Я даже Pari GP всё считаю онлайн :)

Потянет, PARI нормально работает с числами в миллионы цифр. Но разумеется медленно/долго. Пример:

? ss=step=10^5;
? n=0; for(kk=1,3*10^5, k=kk+7*10^80; x=3*k^2+13005*k; if(ispseudoprime(x-1) && ispseudoprime(x+1), n++); if(kk==ss, print(kk,": ",n); ss+=step; ););
100000: 36
200000: 67
300000: 101
time = 26,724 ms.

Заметьте, здесь считалось в 33 раза меньше и более чем вдвое дольше. Плата за большие числа.

Rak so dna в сообщении #1723463 писал(а):

Поэтому, если ваша формула для $25000$ взятых наугад $80$-ти значных $k$ выдаст хотя бы с десяток
простых близнецов, то, возможно, что-то в ней и есть, а так...

Как видите для 300000 последовательных $k$ после $7\cdot10^{80}$ выдаёт сотню простых близнецов.
Что лишь немногим больше чем $6k\pm1$ с 75 простыми близнецами для тех же $k$. Или 5 простыми близнецами для формулы $6k^2\pm1$ (чтобы уйти тоже в 160-значные числа). Или 21 простыми близнецами для формулы $6k\pm1$ с $k=7\cdot10^{160}+1\ldots300000$.
Как минимум 5-кратное преимущество налицо.