Кортежи из простых чисел

[Cantata]

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

USPEH! Naydeno 100 kortegey za 342 sekund.
Vsego provereno: 437321607

Возможно код ещё можно отшлифовать, а результаты уже впечатляют.
Вот сам код:

\\ ==========================================
\\ КОЛЕСО (WHEEL) МЕТОД - ПОИСК 100 CPAP-6
\\ ==========================================

WHEEL_SIZE = 30030;
allowed_mod11 = [2, 5, 7, 8, 10];
allowed_mod13 = [2, 3, 4, 7, 8, 11, 12];

generate_wheel_offsets() = {
    my(offsets = []);
    for(r = 1, WHEEL_SIZE,
        if(gcd(r, 30) == 1 && r % 7 == 2 && 
           setsearch(allowed_mod11, r % 11) > 0 && 
           setsearch(allowed_mod13, r % 13) > 0,
            offsets = concat(offsets, r);
        );
    );
    return(offsets);
};

search_100_CPAP_6_WHEEL(start_val) = {
    my(offsets = generate_wheel_offsets());
    print("Razmer kolesa: ", WHEEL_SIZE, " | Dopustimyh smescheniy: ", #offsets);
    print("Tsel: Nayti 100 CPAP-6\n");
    
    my(base = start_val - (start_val % WHEEL_SIZE));
    my(found = 0);
    my(count = 0);
    my(t_start = getwalltime());
    my(results = []);
    
    print("ZAPUSK...");
    
    while(found < 100,
        for(j = 1, #offsets,
            my(p = base + offsets[j]);
            if(p < start_val, next);
            
            count++;
            
            if(ispseudoprime(p) && ispseudoprime(p+30) && ispseudoprime(p+60) && 
               ispseudoprime(p+90) && ispseudoprime(p+120) && ispseudoprime(p+150),
                
                if(nextprime(p+1) == p+30 && nextprime(p+31) == p+60 && 
                   nextprime(p+61) == p+90 && nextprime(p+91) == p+120 && 
                   nextprime(p+121) == p+150,
                    
                    found++;
                    results = concat(results, p);
                    my(time_sec = (getwalltime() - t_start) / 1000.0);
                    print("NAYDEN #", found, ": p = ", p, " (vremya: ", time_sec, " sek)");
                );
            );
        );
        base += WHEEL_SIZE;
        
        if(count % 500000 == 0,
            my(time_sec = (getwalltime() - t_start) / 1000.0);
            my(speed = count / time_sec);
            print("  ...provereno: ", count, " (skorost: ~", round(speed), "/sek, naydeno: ", found, ")");
        );
    );
    
    my(total_time = (getwalltime() - t_start) / 1000.0);
    print("\nUSPEH! Naydeno 100 kortegey za ", round(total_time), " sekund.");
    print("Vsego provereno: ", count);
    print("\nPolniy spisok 100 chisel:");
    for(i = 1, 100, print(i, ": ", results[i]));
    
    return(results);
};

\\ ЗАПУСК
search_100_CPAP_6_WHEEL(121174811);

[Yadryara]

По-моему зря Вы на свой комп грешите. Я попробовал этот код в интерпретаторе, у меня эта сотня заметно дольше искалась:

NAYDEN #97: p = 45194847791 (vremya: 382.30800000000000000000000000000000000 sek)
NAYDEN #98: p = 45321778427 (vremya: 383.37300000000000000000000000000000000 sek)
NAYDEN #99: p = 46006843591 (vremya: 389.22500000000000000000000000000000000 sek)
NAYDEN #100: p = 47023892827 (vremya: 397.87700000000000000000000000000000000 sek)

USPEH! Naydeno 100 kortegey za 398 sekund.
Vsego provereno: 437321607

[Cantata]

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

По-моему зря Вы на свой комп грешите. Я попробовал этот код в интерпретаторе, у меня эта сотня заметно дольше искалась:

Спасибо, что проверили код!
У меня предыдущий код выполнялся с разницей по времени в 2-3 раза. Поэтому были вопросы к производительности
и я пока их не решила. Возможно всё дело в том коде с кучей циклов, не знаю.
Этот код несколько раз запускала, он более стабильные результаты по времени показывал, но тоже скачет немного.

У нас с вами разница получилась всего 398-342=56 секунд.
Мне кажется, что это в пределах погрешности. Не сказать, что это заметно дольше.

[Yadryara]

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

У нас с вами разница получилась всего 398-342=56 секунд.
Мне кажется, что это в пределах погрешности.

Не-не-не. Это не стат. погрешность. Если запускать на пустом компе и в один поток, то, например у меня, результаты обычно очень надёжные, хорошо воспроизводимые. Если общее время 398, то так и будет $\pm$ 1-2 секунды.

Если сильно охладить его, например, отнести в подвал, то может секунд на 5 быстрее будет.

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

[Cantata]

Вероятно получилось немного ускорить процесс. Шагаем по оси 14k:

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


Вот что получила: найдено 100 кортежей за 298 секунд.

Gotovo! Naydeno 100 za 298 sekund.
Vsego provereno: 437321607

Сам код:

search_100_CPAP_6_14K_FAST_TIMED(start_val) = {
    \\ 1. Предрасчёт смещений для p на основе оси 14k
    my(WHEEL_K = 2145);
    my(allowed_k3 = [1, 2]);
    my(allowed_k5 = [1, 2, 3, 4]);
    my(allowed_k11 = [0, 1, 2, 9, 10]);
    my(allowed_k13 = [0, 1, 4, 5, 8, 9, 12]);
    
    my(p_offsets = []);
    for(r = 1, WHEEL_K,
        if(setsearch(allowed_k3, r % 3) > 0 && 
           setsearch(allowed_k5, r % 5) > 0 && 
           setsearch(allowed_k11, r % 11) > 0 && 
           setsearch(allowed_k13, r % 13) > 0,
            my(off = (14 * r - 75) % 30030);
            if(off <= 0, off += 30030);
            p_offsets = concat(p_offsets, off);
        );
    );
    p_offsets = vecsort(p_offsets);
    
    print("Predraschet zavershen. Naydeno ", #p_offsets, " dopustimyh smescheniy.");
    print("ZAPUSK...\n");
    
    \\ 2. Быстрый цикл
    my(WHEEL_P = 30030);
    my(base = start_val - (start_val % WHEEL_P));
    my(found = 0);
    my(count = 0);
    my(t_start = getwalltime());
    my(results = []);
    
    while(found < 100,
        for(j = 1, #p_offsets,
            my(p = base + p_offsets[j]);
            if(p < start_val, next);
            count++;
            
            if(ispseudoprime(p) && ispseudoprime(p+30) && ispseudoprime(p+60) && 
               ispseudoprime(p+90) && ispseudoprime(p+120) && ispseudoprime(p+150),
                if(nextprime(p+1) == p+30 && nextprime(p+31) == p+60 && 
                   nextprime(p+61) == p+90 && nextprime(p+91) == p+120 && 
                   nextprime(p+121) == p+150,
                    found++;
                    results = concat(results, p);
                    \\  ВЫВОД С ВРЕМЕНЕМ: номер, число и время
                    my(time_sec = (getwalltime() - t_start) / 1000.0);
                    print(found, ": ", p, " (vremya: ", time_sec, " sek)");
                );
            );
        );
        base += WHEEL_P;
    );
    
    my(total_time = (getwalltime() - t_start) / 1000.0);
    print("\nGotovo! Naydeno ", found, " za ", round(total_time), " sekund.");
    print("Vsego provereno: ", count);
    return(results);
};

\\ ЗАПУСК
search_100_CPAP_6_14K_FAST_TIMED(121174811);

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

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

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

У нас с вами разница получилась всего 398-342=56 секунд.
Мне кажется, что это в пределах погрешности.

Не-не-не. Это не стат. погрешность. Если запускать на пустом компе и в один поток, то, например у меня, результаты обычно очень надёжные, хорошо воспроизводимые. Если общее время 398, то так и будет $\pm$ 1-2 секунды.

Если сильно охладить его, например, отнести в подвал, то может секунд на 5 быстрее будет.

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

Поняла, ваш стабильные результаты дает, удобно.
С моим еще не всё понятно. Я запуталась при установки Пари на компьютер, несколько раз удаляла, устанавливала,
мало опыта) возможно из-за этого есть странности в работе программы.
По характеристикам попозже посмотрю, скажу в личке, хорошо? В целом ничего сверхъестественного в нем нет.

[Yadryara]

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

По характеристикам попозже посмотрю, скажу в личке, хорошо?

Занятно Тут народ хвастается вовсю: у меня 32 потока — а у меня 56 ... А вы наоборот.

В личке сообщать... Я в железе-то всё равно мало понимаю. Ещё наличие AVX2 имеет значение, но что это такое, я толком не знаю. А Дмитрий, кажись, знает.

[Cantata]

Yadryara
Вот в настройках посмотрела: 8 ядер 12 логических процессоров - вы это хотели узнать?
Раз уж карты раскрываем, скажите, сколько у вас потоков?
Если бы мне это еще о чем-то говорило :)

А вы не смотрели новый код по оси 14k? Он у вас быстрее выполнился чем предыдущий?

[Yadryara]

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

8 ядер 12 логических процессоров - вы это хотели узнать?

Вроде это. Я, кстати, не в курсе: 12 логических процессоров это и есть 12 потоков?

Ну, про свой комп я уже неоднократно говорил. Проц у меня AMD Ryzen 5, 3.70 GHz. x64. 6 ядер, 12 потоков. AVX2 вроде есть.

Номинальное количество потоков можно посмотреть в многопоточной версии PARI. А можно и через знаменитую программу primesieve. У меня скачана сравнительно недавняя версия:

primesieve 12.13
February 05, 2026
Kim Walisch, <[e-mail]>

Это написано в файле "README.txt". Вот как мой комп ищет все простые до триллиона:

C:\PrimeSieve>primesieve 1e12
Sieve size = 256 KiB
Threads = 12
100%
Seconds: 28.035
Primes: 37607912018

Видите, программа задействовала все 12 потоков (Threads). Попробуйте, заодно ещё раз скорость сможем сравнить.

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

А вы не смотрели новый код по оси 14k? Он у вас быстрее выполнился чем предыдущий?

Нет, подольше:

98: 45321778427 (vremya: 386.06600000000000000000000000000000000 sek)
99: 46006843591 (vremya: 391.91900000000000000000000000000000000 sek)
100: 47023892827 (vremya: 400.61100000000000000000000000000000000 sek)

Gotovo! Naydeno 100 za 401 sekund.
Vsego provereno: 437321607

Второй запуск:

98: 45321778427 (vremya: 386.13300000000000000000000000000000000 sek)
99: 46006843591 (vremya: 391.95500000000000000000000000000000000 sek)
100: 47023892827 (vremya: 400.63400000000000000000000000000000000 sek)

Gotovo! Naydeno 100 za 401 sekund.
Vsego provereno: 437321607

Видите, какая воспроизводимость: за более чем 6 минут счёта различие меньше одной десятой секунды. Это между двумя запусками одного и того же кода. Если угодно, одной и той же функции.

[Yadryara]

По самому коду пока замечаний немного. Я, признаться, уже подзабыл как эти кортежи из простых ищутся.

Очевидное: зачем такое огромное количество нулей при выводе времени?? И тоже уже не очень помню как быстро переделать. Ну вот, переделал пока так.

Было:

print(found, ": ", p, " (vremya: ", time_sec, " sek)");

Стало:

print1(found, ": ", p);
printf(" (vremya: %.3f", time_sec);
print(" sek)");

Теперь пишет вот так:

1: 121174811 (vremya: 0.000 sek)
2: 1128318991 (vremya: 8.324 sek)
3: 2201579179 (vremya: 18.281 sek)

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

А чего тут вспоминать и читать мануал. ИИ же есть. Прямо у гугловского ИИ спросил:

А как вот такой вывод сделать покороче, одной командой?

print1(found, ": ", p);
printf(" (vremya: %.3f", time_sec);
print(" sek)");

А вот как:

printf("%Ps: %Ps (vremya: %.3f sek)\n", found, p, time_sec);

[Yadryara]

А вот ещё цветной вариант. Номер и начльное число кортежа печатает зелёным, время — жёлтым:

printf("\e[32m%Ps: %Ps\e[0m (vremya: \e[33m%.3f\e[0m sek)\n", found, p, time_sec);

Но этот вариант в цвете работает у меня только в Убунте.

О! И считает в Убунте заметно быстрее, хотя запускал по-прежнему в интерпретаторе:

98: 45321778427 (vremya: 344.393 sek)
99: 46006843591 (vremya: 349.555 sek)
100: 47023892827 (vremya: 357.246 sek)

Gotovo! Naydeno 100 za 357 sekund.
Vsego provereno: 437321607

А теперь запустил и через компилятор:

98: 45321778427 (vremya: 201.489 sek)
99: 46006843591 (vremya: 204.531 sek)
100: 47023892827 (vremya: 209.060 sek)

Gotovo! Naydeno 100 za 209 sekund.
Vsego provereno: 437321607

3min, 29,063 ms

Как видим, ещё быстрее, причём намного.

[Yadryara]

Ну вот мы тут с Гуглом довели до 22 секунд:

98: 45321778427 (vremya: 14.561 sek)
99: 46006843591 (vremya: 14.775 sek)
100: 47023892827 (vremya: 15.072 sek)

Gotovo! Multithreading variant nashel 100 elementov za 15 sekund.

21,625 ms

Запуск на 6 физических ядрах:

export GP_NB_THREADS=6
gp2c-run -g Rab_5.gp

"Ядра — чистый изумруд"

Прога:

(PARI)

/*
GP;default(parisizemax, 2^30);
GP;init_Rab_5();
*/

search_100_CPAP_6_14K_PARALLEL(start_val) = {
    my(WHEEL_K = 692295);
    my(WHEEL_P = 9699690);
    
    my(ok3 = vector(3, i, 0));
    my(ok5 = vector(5, i, 0));
    my(ok11 = vector(11, i, 0));
    my(ok13 = vector(13, i, 0));
    
    ok3[1+1] = 1; ok3[2+1] = 1;
    ok5[1+1] = 1; ok5[2+1] = 1; ok5[3+1] = 1; ok5[4+1] = 1;
    ok11[0+1] = 1; ok11[1+1] = 1; ok11[2+1] = 1; ok11[9+1] = 1; ok11[10+1] = 1;
    ok13[0+1] = 1; ok13[1+1] = 1; ok13[4+1] = 1; ok13[5+1] = 1; ok13[8+1] = 1; ok13[9+1] = 1; ok13[12+1] = 1;
   
    my(p_offsets = []);
    for(r = 1, WHEEL_K,
        my(m3 = r % 3 + 1);
        my(m5 = r % 5 + 1);
        my(m11 = r % 11 + 1);
        my(m13 = r % 13 + 1);
        
        if(ok3[m3] && ok5[m5] && ok11[m11] && ok13[m13],
            my(p_cand = 14 * r - 75);
            my(bad = 0);
            forstep(i = 0, 150, 30,
                my(v = p_cand + i);
                if(v % 17 == 0 || v % 19 == 0, bad = 1; break)
            );
            if(!bad,
                my(off = p_cand % WHEEL_P);
                if(off <= 0, off += WHEEL_P);
                p_offsets = concat(p_offsets, off);
            );
        );
    );
    
    p_offsets = vecsort(p_offsets, , 8);
    my(len = #p_offsets);
   
    print("Predraschet zavershen. Smescheniy: ", len);
    print("ZAPUSK MULTITHREADING (BATCH MODE)...\n");
   
    my(base_start = start_val - (start_val % WHEEL_P));
    my(t_start = getwalltime());
    
    my(found = 0);
    my(results = []);
    
    \\ Задаем шаг окна (размер пачки задач для 6 потоков).
    \\ 24 блока — оптимально, чтобы все 6 ядер были загружены и не простаивали.
    my(batch_size = 24); 
    my(current_b_start = 0);
    
    while(found < 100,
        \\ Запускаем параллельный расчет для текущего окна блоков
        parfor(b_idx = current_b_start, current_b_start + batch_size - 1,
            my(base = base_start + b_idx * WHEEL_P);
            my(local_res = []);
            
            for(j = 1, len,
                my(p = base + p_offsets[j]);
                if(p < start_val, next);
               
                if(ispseudoprime(p) && ispseudoprime(p+30) && ispseudoprime(p+60) &&
                   ispseudoprime(p+90) && ispseudoprime(p+120) && ispseudoprime(p+150),
                    if(nextprime(p+1) == p+30 && nextprime(p+31) == p+60 &&
                       nextprime(p+61) == p+90 && nextprime(p+91) == p+120 &&
                       nextprime(p+121) == p+150,
                        local_res = concat(local_res, p);
                    );
                );
            );
            local_res;
            
        , res_block,
            \\ Сбор результатов главного потока
            if(#res_block > 0,
                for(k = 1, #res_block,
                    found++;
                    results = concat(results, res_block[k]);
                    my(time_sec = (getwalltime() - t_start) / 1000.0);
                    printf("\e[1;32m%Ps: %Ps\e[0m (vremya: \e[33m%.3f\e[0m sek)\n", found, res_block[k], time_sec);
                );
            );
        );
        
        \\ Сдвигаем окно блоков вперед для следующей итерации
        current_b_start += batch_size;
    );
   
    my(total_time = (getwalltime() - t_start) / 1000.0);
    results = vecsort(results);
    
    print("\nGotovo! Multithreading variant nashel ", #results, " elementov za ", round(total_time), " sekund.");
    return(results);
};

{
t0 = getwalltime();
print;

search_100_CPAP_6_14K_PARALLEL(121174811);

print;
print(strtime(getwalltime() - t0));
print;
}
quit;

[Cantata]

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

Вроде это. Я, кстати, не в курсе: 12 логических процессоров это и есть 12 потоков?

Как я поняла - да, это они и есть.

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

Видите, программа задействовала все 12 потоков (Threads). Попробуйте, заодно ещё раз скорость сможем сравнить.

Вижу как работает программа, а сравнивать не вижу смысла) извините.

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

По самому коду пока замечаний немного. Я, признаться, уже подзабыл как эти кортежи из простых ищутся.

Очевидное: зачем такое огромное количество нулей при выводе времени?? И тоже уже не очень помню как быстро переделать. Ну вот, переделал пока так.

Спасибо. :)

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

А теперь запустил и через компилятор:

Впечатляет! Я тоже через компилятор запускала, результаты вы видели. Так что вопрос по сравнению скорости решен)

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

Ну вот мы тут с Гуглом довели до 22 секунд:

Ого какая скорость на нескольких ядрах! Может тогда я покажу вам программу для поиска СРАР-7 с шагом 210, посмотрите ее?

[Dmitriy40]

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

Я, кстати, не в курсе: 12 логических процессоров это и есть 12 потоков?

Да.

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

А вот как:

printf("%Ps: %Ps (vremya: %.3f sek)\n", found, p, time_sec);

И это не совсем правильно, ведь выводятся числа, а не строки, потому вместо %Ps надо просто %d, хотя превращение числа в строку и работает.

[Yadryara]

Cantata, я пока считаю что ваш комп быстрее моего. Так что в сравнении скоростей смысл вижу.

Так у вас Винда или Линукс? Или как у меня: Винда + WSL ?

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

Может тогда я покажу вам программу для поиска СРАР-7 с шагом 210, посмотрите ее?

Да, но давайте для начала найдём хотя бы СРАР-3 с гэпами в 210. У меня пока не получилось.

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

Dmitriy40, понял, спасибо.

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

Хотя вблизи квадриллиона нашёл:

Pre-calculating 30M wheel + tables for 31,37,41,43... Please wait.
  *** init_CPAP3_quadrillion: Warning: increasing stack size to 16000000.
  *** init_CPAP3_quadrillion: Warning: increasing stack size to 32000000.
  *** init_CPAP3_quadrillion: Warning: increasing stack size to 64000000.
Wheel ready! Perfect offsets remaining: 1486350
Плотность кандидатов повышена. На тесты простоты пойдет на ~14% меньше чисел.
ZAPUSK ULTRA-SPEED MULTITHREADING (START AT 1 QUADRILLION)...
  *** init_CPAP3_quadrillion: Warning: increasing stack size to 128000000.
  *** anon_0: Warning: increasing stack size to 16000000.
  *** anon_0: Warning: increasing stack size to 32000000.
  *** anon_0: Warning: increasing stack size to 64000000.
Provereno do: 1000005743956707
=======================================================
ISTORICHESKOE OTKRYTIE! NAIDENA PERVAYA TROYKA CPAP-3 (210):
p      = [1000009647394271]

[Cantata]

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

Да, но давайте для начала найдём хотя бы СРАР-3 с гэпами в 210.

Я только этот код пока использую. Но он не все находит:

for(i=1, 100000000, p=10^19+13+i*210; if(ispseudoprime(p) && ispseudoprime(p+210) && ispseudoprime(p+420), cl=1; forstep(x=p+2, p+418, 2, if(x!=p+210 && ispseudoprime(x), cl=0; break())); if(cl, print(p))));