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

[wrest]

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

Грубо говоря, шанс наугад взятого $160$-значного числа оказаться простым близнецом
$\approx\frac{1}{160^2}\approx 0,00004$

Примерно в 5-6 раз меньше :) Логарифм же натуральный надо, а не десятичный.

[Cantata]

Dmitriy40
Благодарю Вас за помощь!
На самом деле без ваших объяснений я бы не смогла разобраться!

Так бы и разглядывала диагональ в треугольном расположении чисел, где от 11 сразу много пар чисел простых близнецов идут, и не знала бы как к ним подойти)

[Yadryara]

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

У меня обычный домашний компьютер, который не потянет такие вычисления.

У меня вроде тоже обычный комп. Однако мировые рекорды устанавливать удавалось.

А нет ли желания поискать цепочки посложнее чем близнецы?

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

Я даже Pari GP всё считаю онлайн :)

Интересно почему. Коротенькие проги в интерпретаторе gp обычно очень легко считаются. Вставил код, да нажал на "Enter".

Или Вы пока PARI/gp себе не установили?

[Cantata]

Yadryara в сообщении #1723486 писал(а):

Однако мировые рекорды устанавливать удавалось.

Поздравляю!

Yadryara в сообщении #1723486 писал(а):

А нет ли желания поискать цепочки посложнее чем близнецы?

К кортежам? Вот эта задача с n звездочками. Сейчас точно не готова - недавно тему о кортежах читала и поняла, что у меня пока нет идей.

Yadryara в сообщении #1723486 писал(а):

Или Вы пока PARI/gp себе не установили?

Да, так и есть)

[Rak so dna]

wrest в сообщении #1723479 писал(а):

Примерно в 5-6 раз меньше :) Логарифм же натуральный надо, а не десятичный.

Я делал оценку по порядку величины (там ведь ещё множитель вроде был какой-то). Сейчас пересчитал по первой гипотезе Харди-Литтлвуда: $\approx 0,000009781$

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

Как видите для 300000 последовательных $k$ после $7\cdot10^{80}$ выдаёт сотню простых близнецов.

Ну, выходит что ТС нашла способ получения простых близнецов примерно в $30$ раз эффективнее обычного угадывания (если эти расчёты подтвердятся и на других выборках). Неужели и для бОльших $k$ преимущество сохранится?

[Cantata]

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

Ну, выходит что ТС нашла способ получения простых близнецов примерно в $30$ раз эффективнее обычного угадывания

Сейчас посмотрела, оказывается результаты даны для формулы лидера, которую нашел tolstopuz.
Она по праву называется лидером!

Моя формула скромнее дает результаты:

? {
ss = 10^5;
step = 10^5;
n = 0;
for(kk = 1, 3*10^5,
    k = kk + 7*10^80;
    x = 33*k^2 + 23595*k;
    if(ispseudoprime(x-1) && ispseudoprime(x+1), n++);
    if(kk == ss,
        print(kk, ":", n);
        ss += step;
    )
);
}
100000:25
200000:49
300000:86

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

Dmitriy40
Код изумительный! Такие числа посчитал у меня онлайн меньше чем за минуту!

[wrest]

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

Ну, выходит что ТС нашла способ получения простых близнецов примерно в $30$ раз эффективнее обычного угадывания

Ну так даже $30n \pm 1$ даёт это преимущество, ну а бОльшие праймориалы - ещё больше.

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

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

Неужели и для бОльших $k$ преимущество сохранится?

Решето же, отсеивает сразу для всех k

[Cantata]

Оказывается эффективность зависит от локальной модулярной структуры интервала.
Выбор лучшей формулы может определяться конкретным диапазоном поиска.

Вот моя формула на другом интервале:

? {
    ss = 10^5;
    step = 10^5;
    n = 0;
    for(kk = 1, 3*10^5,
        k = kk + 3*10^80;
        x = 33*k^2 + 23595*k;
        if(ispseudoprime(x-1) && ispseudoprime(x+1), n++);
        if(kk == ss,
            print(kk, ":", n);
            ss += step;
        )
    );
}
100000:32
200000:58
300000:106

[Rak so dna]

wrest в сообщении #1723493 писал(а):

Ну так даже $30n \pm 1$ даёт это преимущество

Не даёт. Проверил $5$ случайных диапазонов длинной $100000$ на числах порядка $10^{160}$, везде получилось в $3$-$4$ раза хуже.

[wrest]

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

везде получилось в $3$-$4$ раза хуже.

Хуже чем что?

[Yadryara]

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

Сейчас точно не готова - недавно тему о кортежах читала и поняла, что у меня пока нет идей.

На всякий случай. О кортежах речь идёт не только в тех темах, где в названии есть слово "кортеж", но и например в той, где есть слово "мечта"...

[Cantata]

Yadryara в сообщении #1723497 писал(а):

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

Сейчас точно не готова - недавно тему о кортежах читала и поняла, что у меня пока нет идей.

На всякий случай. О кортежах речь идёт не только в тех темах, где в названии есть слово "кортеж", но и например в той, где есть слово "мечта"...

Вы о теме про пентадекатлон? Я про неё и говорила, что у меня нет идей как эффективнее находить кортежи, а искать бесконечным перебором мне просто не интересно.

[Cantata]

Здравствуйте!

С помощью Дипсика нашла ещё одну достаточно эффективную формулу:

f(n) = 57n^{2} + 133095n \pm 1

Результат при n = 1 \dots 10^{7}: 389 203 пары простых-близнецов.

Плотность около 3.89%, что примерно в 35 раз выше теоретической (0.11%).

Код для проверки (PARI/GP):

n=0; for(k=1,10^7, x=57*k^2+133095*k; if(ispseudoprime(x-1)&&ispseudoprime(x+1), n++)); print(n)

Напомню какие результаты были получены для предыдущих формул:
3n^{2} + 13005n \pm 1 → 397 025 пар
33n^{2} + 23595n \pm 1 → 393 421 пар

Проведя некоторые вычисления, Дипсик предположил,
что все три формулы эмпирически подчиняются балансу D в квадрате.
А любое отклонение от баланса ведет к деградации резонанса и снижению плотности простых чисел до средних теоретических значений.

v_{D}(a) + v_{D}(b) = 2,
где D — дискриминант поля \mathbb{Q}(\sqrt{D}) с числом классов 1,
а v_{D}(x) — показатель степени D в разложении x.

Насколько это предположение ошибочно или тривиально?

Для приведённых формул:
3n^{2} + 13005n \pm 1: D=17, v_{D}(a)=0, v_{D}(b)=2
33n^{2} + 23595n \pm 1: D=11, v_{D}(a)=0, v_{D}(b)=2
57n^{2} + 133095n \pm 1: D=5, v_{D}(a)=0, v_{D}(b)=1

В найденной формуле квадрат 5^{2} отсутствует,
но число 467, входящее в разложение, является квадратичным вычетом по модулю 11 и 17
оно (распадается в полях \mathbb{Q}(\sqrt{11}) и \mathbb{Q}(\sqrt{17})),
что частично компенсирует отсутствие 5^{2}? Или это слишком смелое предположение?

[Cantata]

Новая формула: $132k^2 + 132 \cdot 6485k \pm 1$, находит для 10млн k уже 436080 пар простых близнецов.

Очень интересно, возможно ли, что есть такие формулы которые находят 10-15% или ещё больше?
Какой должен быть предел?

[wrest]

Вот программка для оценки плотности близнецов порождаемых квадратным двучленом по сравнению с плотностью случайных близнецов

(Оффтоп)

TwinPrimeRatio(A, N = 500) = {
    my(a, b, c, p, nu, C = 1/2, f1, f2, x, g, deg);
    
    deg = poldegree(A);
    if(deg > 2, error("Степень больше 2"));
    
    /* Приводим к стандартному виду a*x^2 + b*x + c */
    if(deg == 0,
        a = 0; b = 0; c = polcoef(A, 0)
    ,
        if(deg == 1,
            a = 0; b = polcoef(A, 1); c = polcoef(A, 0)
        ,
            /* deg == 2 */
            a = polcoef(A, 2); b = polcoef(A, 1); c = polcoef(A, 0)
        )
    );
    
    /* Если a=0 и b=0 — константа */
    if(a == 0 && b == 0,
        print("Константа же?");
        return(0)
    );
    
    /* Находим НОД коэффициентов */
    g = gcd([a, b, c]);

    /* Произведение по нечётным простым */
    forprime(p = 3, N,
        nu = 0;
        for(x = 0, p-1,
            f1 = (a*x^2 + b*x + c - 1) % p;
            f2 = (a*x^2 + b*x + c + 1) % p;
            if(f1 == 0 || f2 == 0, nu++)
        );
        /* Если ВСЕ x дают корень — плотность 0 */
        if(nu == p, 
            print("Оба деляься на ", p, " -> нет простых близнецов");
            return(0)
        );
        C *= (1 - nu/p) / (1 - 1/p)^2;
    );
    
    return(2*C/0.660161815846869573927812110014); /* делим на константу близнецов */
};

Запускаем так:

? TwinPrimeRatio(k)
time = 4 ms.
1.0039694281485984136204101546538058864
? TwinPrimeRatio(33*k^2 + 23595*k)
time = 3 ms. 
15.128152363244823989336267422923689949 
? TwinPrimeRatio(33*k^2 + 7425*k)
time = 5 ms. 
13.647879713286780814195455932519572508 
? TwinPrimeRatio(6*k) time = 5 ms. 
3.0119082844457952408612304639614176591 
? TwinPrimeRatio(132*k^2+132*6485*k) 
time = 3 ms.
16.812752479884540653350269363058782163
?

Я запутался в множителе, для ясности считаем что многочлен f(k)=k даёт плотность близнецов без поправок (единичную).