Симметричные кортежи из последовательных простых чисел

[Dmitriy40]

Begemot82 в сообщении #1059565 писал(а):

Nataly-Mak в сообщении #1059528 писал(а):

Это происходит от частого обращения к функции nextprime().

Вместо вызова nextprime() для второго кандидата в близнецы можно использовать более быструю функцию проверки на простоту ispseudoprime().

А ещё лучше вообще не вызывать ни nextprime ни ispseudoprime внутри цикла forprime и хранить всё в переменных. Сейчас в программе каждое число (не только простое!) проверяется на простоту аж 14 раз вместо одного раза!

-- 06.10.2015, 15:26 --

Между прочим, primesieve вполне себе умеет выдавать список близнецов очень-очень быстро - с ключом -p2.

[Nataly-Mak]

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

forprime(n=18409199,18450000, p=nextprime(n+1); if(p-n==2, print1(n,",") ) )

с выводом результатов в файл. Массив выводится мгновенно:

(Массив первых чисел пар-близнецов)

18409199,18409541,18409799,18409871,18409967,18410669,18411047,18411077,18411269,18411329,18411749,18411857,18
412151,18412517,18412631,18413027,18413111,18413651,18413741,18413807,18413819,18413849,18414089,18414509,1841
4659,18414677,18414827,18415169,18415181,18415511,18415931,18416159,18416471,18416579,18416687,18416969,184170
11,18417167,18417437,18417701,18418109,18418571,18418721,18419117,18419309,18419369,18419411,18420749,18420761
,18421607,18421631,18421721,18421889,18422291,18422861,18423131,18423311,18423551,18423929,18424067,18424487,1
8424559,18424709,18424739,18424871,18425021,18425387,18425861,18426017,18426251,18426311,18426761,18426899,184
26971,18427679,18427931,18428141,18428621,18429011,18429251,18429347,18429419,18429491,18429767,18429977,18430
079,18430121,18430229,18430541,18430649,18430757,18431051,18431249,18431297,18431339,18431351,18431627,1843204
7,18432611,18432647,18433619,18433859,18433949,18433979,18434021,18434081,18434357,18434639,18434699,18435017,
18435101,18435749,18435827,18435881,18435941,18435959,18436001,18436529,18436679,18436799,18437567,18437717,18
437759,18438107,18438191,18438359,18438881,18438941,18439007,18439229,18439277,18439319,18439607,18439829,1843
9961,18440159,18440297,18440327,18440831,18440921,18440951,18441089,18441149,18441167,18441671,18441959,184423
37,18442967,18443207,18443237,18443441,18443567,18443609,18443837,18444059,18444467,18444617,18444731,18444887
,18445001,18445079,18445487,18446201,18446249,18446567,18447419,18447467,18447617,18447629,18448271,18448301,1
8448931,18449411,18449531,

Думаю, что такой массив нашлёпать для PARI/GP не проблема до какого угодно большого простого числа.
Теперь надо сделать программку поиска симметричных кортежей длины 9. Лучше, конечно, всё это делать в одной программе, но у меня пока нет мыслей, как это организовать.

-- Вт окт 06, 2015 21:16:29 --

"Хвост" предыдущего массива покажу:

18407771, 18408107, 18408287, 18408371, 18408419, 18408581, 18408749, 18408989, 18409199

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

[Nataly-Mak]

Nataly-Mak в сообщении #1059528 писал(а):

Итак, 17-ый член последовательности A035795 найден.
Дальше запустила поиск.

Хех... заглянула сейчас в последовательность A035795, а там уже 17-ый член нарисован
maxal
конечно, это вас благодарить надо
Я не стала пока делать правку последовательности в надежде найти ещё пару-тройку решений.
Но пока глухо, проверила до 749000000000. Продолжаю крутить программу. Проверяю интервалами по 3 млрд. Очень медленно работает программа.
Мне думается, что программа whitefox, если её модифицировать под этот поиск, работала бы гораздо быстрее.
Более эффективную программу написать, увы, не умею. Ну, пусть работает та, какую написала.

[Nataly-Mak]

Запустила две копии программки на поиск 18-го члена последовательности A035795.
Загрузка процессора - 100%, использование памяти - 38%. Да, очень экономно PARI/GP использует память.

[Dmitriy40]

Nataly-Mak в сообщении #1060085 писал(а):

Загрузка процессора - 100%, использование памяти - 38%. Да, очень экономно PARI/GP использует память.

Вы издеваетесь что ли? Для нахождения 18-го члена A035795 за глаза достаточно 5МБ памяти, что составляет менее 0.3% вашей памяти.

[Nataly-Mak]

maxal
мало что понимая в вашей программке

{ v=vector(12,i,prime(i)); 
print(v);
forprime(p=v[12]+1,100, 
v = vector(12,i, if(i<14,v[i+1], p));
print(v);
); }

я её всё-таки уломала (долго уламывала ), она у меня заработала:

{ v=vector(14,i,prime(i)); 
print(v);
forprime(p=v[14]+772999990000,776000000000, 
v = vector(14,i, if(i<14,v[i+1], p));
if(v[2]-v[1]==2, if(v[4]-v[3]==2, if(v[6]-v[5]==2, if(v[8]-v[7]==2, if(v[10]-v[9]==2, if(v[12]-v[11]==2, if(v[14]-v[13]==2, print(v)); ); ); ); ); ); );  )
}

Да, скорость выполнения увеличилась почти на 70%.
Теперь продолжу поиск по новой программе. Пока 18-ый член последовательности A035795 не найден.

Вы писали в лекциях, что при работе с простыми числами хорошо вычислить их заранее. Я попробовала это сделать, вычислила заранее простые числа до $10^{12}$. Однако на скорости работы программы это никак на сказалось. Надеялась, что оператор forprime будет пошустрее работать.

[Nataly-Mak]

Ура!
Вот она - ещё одна великолепная семёрка близнецов:

[793957831409, 793957831411, 793957831439, 793957831441, 793957831487, 793957831489, 793957831559, 793957831561, 793957831571, 793957831573, 793957831607, 793957831609, 793957831631, 793957831633]

Это 18-ая. Ещё бы парочку найти и можно переходить к восьмёркам близнецов.

[Dmitriy40]

Ещё 11ч назад было:

Begemot82 в сообщении #1060018 писал(а):

Новинки для A035795

18 793957831409
19 808316366171

И только что (уже 20-й член):

Begemot82 в сообщении #1060310 писал(а):

Еще семерочка выскочила.

[Nataly-Mak]

А вот и 19-ая великолепная семёрка

[808316366171, 808316366173, 808316366189, 808316366191, 808316366201, 808316366203, 808316366267, 808316366269, 808316366279, 808316366281, 808316366327, 808316366329, 808316366357, 808316366359]

Близко была к 18-ой, так же, как и 17-ая к 16-ой.
Так, ещё 20-ую семёрку найду и хватит. Семёрки мне ничего не дают. Попробую искать восьмёрочки. Но там, наверное, трудно искать.

-- Ср окт 07, 2015 21:58:07 --

Пока две программки ищут 20-ую семёрочку, тестирую программку поиска восьмёрок близнецов на известной первой восьмёрке:

{ v=vector(16,i,prime(i)); 
print(v);
forprime(p=v[16]+1107819732000,1107819733300, 
v = vector(16,i, if(i<16,v[i+1], p));
if(v[2]-v[1]==2, if(v[4]-v[3]==2, if(v[6]-v[5]==2, if(v[8]-v[7]==2, if(v[10]-v[9]==2, if(v[12]-v[11]==2, if(v[14]-v[13]==2, if(v[16]-v[15]==2, print(v)); ); ); ); ); ); ); );  )
}

Выполняю программку:

? \r A45.txt
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53]
[1107819732821, 1107819732823, 1107819732911, 1107819732913, 1107819732917, 1107819732919, 1107819732947, 1107819732949, 1107819732959, 1107819732961, 1107819732977, 1107819732979, 1107819733037, 1107819733039, 1107819733061, 1107819733063]

Проверка в Wolfram Alpha:

Select[Range[0,300],PrimeQ[1107819732821+#]&]
{0, 2, 90, 92, 96, 98, 126, 128, 138, 140, 156, 158, 216, 218, 240, 242, 266, 282}

Всё правильно. Можно ехать дальше. Вот только как оно здесь ехать будет, пока не знаю.
Ну, и конечно, интересуют симметричные кортежи, потому что из них могут составиться пандиагональные квадраты 4-го порядка.

[Begemot82]

До $ 10^{14}$ симметричные восьмерки из близнецов не встречаются.

[Nataly-Mak]

Это решение Dmitriy40, оно есть и у Jarek:

1960984050584219159: 0 2 30 32 42 44 48 50 72 74 78 80 90 92 120 122

Тестирую это решение:

{ v=vector(16,i,prime(i)); 
print(v);
forprime(p=v[16]+1960984050584000000,1960984050584230000, 
v = vector(16,i, if(i<16,v[i+1], p));
if(v[2]-v[1]==2, if(v[4]-v[3]==2, if(v[6]-v[5]==2, if(v[8]-v[7]==2, if(v[10]-v[9]==2, if(v[12]-v[11]==2, if(v[14]-v[13]==2, if(v[16]-v[15]==2, print(v)); ); ); ); ); ); ); );  )
}

Программка мгновенно выдаёт:

[1960984050584219159, 1960984050584219161, 1960984050584219189, 1960984050584219191, 1960984050584219201, 1960984050584219203, 1960984050584219207, 1960984050584219209, 1960984050584219231, 1960984050584219233, 1960984050584219237, 1960984050584219239, 1960984050584219249, 1960984050584219251, 1960984050584219279, 1960984050584219281]

Вот они - восемь пар близнецов подряд и ... КПППЧ (симметричный кортеж из последовательных простых чисел), дающая пандиагональный квадрат 4-го порядка
По значению первого элемента кортежа p это не минимальная КПППЧ такого рода; у Jarek есть с меньшим значением.
Значит, и квадрат, составленный из его КПППЧ, имеет меньшую магическую константу. У Jarek есть и другие подобные решения.

Эх, если бы так быстро находились решения в больших интервалах. Глядишь, и квадратики нашлись бы

[Dmitriy40]

Nataly-Mak в сообщении #1060400 писал(а):

По значению первого элемента кортежа p это не минимальная КПППЧ такого рода; у Jarek есть с меньшим значением.
Значит, и квадрат, составленный из его КПППЧ, имеет меньшую магическую константу.

За свои слова принято отвечать - приведите решение с КПППЧ по данному паттерну с меньшим начальным числом? Я вот уверен что это именно минимальная КПППЧ.

[Nataly-Mak]

Ну вот, 20-ая семёрочка нашлась:

[881191407827, 881191407829, 881191407839, 881191407841, 881191407851, 881191407853, 881191407911, 881191407913, 881191407977, 881191407979, 881191408157, 881191408159, 881191408169, 881191408171]

Планы у меня изменились. Зачем перескакивать на поиск восьмёрок близнецов? Без семёрочки и восьмёрочки не будет
Решила продолжить поиск семёрок; до первой известной восьмёрки не так далеко осталось. Заодно и ещё одна независимая проверка первой восьмёрки будет (хотя, конечно, уже проверили и перепроверили не раз). Зато семёрочки не пропустятся, все будут по порядку. А восьмёрочки никуда не денутся: где будет восьмёрочка, там будет два набора по 7 пар близнецов подряд - дуплетом
Торопиться мне некуда, потихонечку буду искать.

a(18) - a(20) ввести что ли в последовательность A035795?
Может, потом, когда побольше найдётся решений, чтобы несколько раз не редактировать последовательность, лишняя работа редакторам.

[Nataly-Mak]

a(21) - a(22) были рядом с a(20), нашлись довольно быстро.
Ищу a(23). Этот член, наверное, будет далеко
Сейчас проверяется интервал [911000000000,917000000000].
Приближаюсь к $10^{12}$, а там и первая восьмёрочка недалеко.
a(21)

[891108993767, 891108993769, 891108993779, 891108993781, 891108993791, 891108993793, 891108993809, 891108993811, 891108993881, 891108993883, 891108993917, 891108993919, 891108993959, 891108993961]

a(22)

[896804723201, 896804723203, 896804723207, 896804723209, 896804723237, 896804723239, 896804723279, 896804723281, 896804723291, 896804723293, 896804723327, 896804723329, 896804723369, 896804723371]

[Nataly-Mak]

Дошла до $10^{12}$.
Сейчас проверяются эти два интервала (работают две копии программы):
[988999990000,995000000000] и [994999990000,1001000000000].
Проверяю интервалами по 6 млрд (раньше по 3 млрд проверяла, но слишком часто приходилось менять интервалы; можно, конечно, задать сразу интервал миллиардов 50-100 и ждать целый день, что найдётся; но мне удобнее проверять небольшими интервалами, потому что электричество часто отключают, и вся проверка большого итервала полетит псу под хвост).
На проверку одного такого интервала требуется час с хвостиком. При такой скорости первую восьмёрку (1107819732821) я должна получить где-то часов через 9-10.
Новая семёрка – a(23) – пока не найдена, если я ничего не пропустила, переходя от интервала к интервалу.

-- Пт окт 09, 2015 08:51:47 --

Тем временем продолжаю думать над задачей составления магического квадрата 3-го порядка из первых чисел последовательных пар простых чисел-близнецов.
Напомню: эта моя простенькая программка

{k=0;
forprime(n=18409199,18450000, p=nextprime(n+1); if(p-n==2, print1(n,","); k=k+1 ) );
print(k) 
}

формирует массив из первых чисел пар близнецов.

(Результат работы программы)

? \r A45.txt
18409199,18409541,18409799,18409871,18409967,18410669,18411047,18411077,18411269,18411
329,18411749,18411857,18412151,18412517,18412631,18413027,18413111,18413651,18413741,1
8413807,18413819,18413849,18414089,18414509,18414659,18414677,18414827,18415169,184151
81,18415511,18415931,18416159,18416471,18416579,18416687,18416969,18417011,18417167,18
417437,18417701,18418109,18418571,18418721,18419117,18419309,18419369,18419411,1842074
9,18420761,18421607,18421631,18421721,18421889,18422291,18422861,18423131,18423311,184
23551,18423929,18424067,18424487,18424559,18424709,18424739,18424871,18425021,18425387
,18425861,18426017,18426251,18426311,18426761,18426899,18426971,18427679,18427931,1842
8141,18428621,18429011,18429251,18429347,18429419,18429491,18429767,18429977,18430079,
18430121,18430229,18430541,18430649,18430757,18431051,18431249,18431297,18431339,18431
351,18431627,18432047,18432611,18432647,18433619,18433859,18433949,18433979,18434021,1
8434081,18434357,18434639,18434699,18435017,18435101,18435749,18435827,18435881,184359
41,18435959,18436001,18436529,18436679,18436799,18437567,18437717,18437759,18438107,18
438191,18438359,18438881,18438941,18439007,18439229,18439277,18439319,18439607,1843982
9,18439961,18440159,18440297,18440327,18440831,18440921,18440951,18441089,18441149,184
41167,18441671,18441959,18442337,18442967,18443207,18443237,18443441,18443567,18443609
,18443837,18444059,18444467,18444617,18444731,18444887,18445001,18445079,18445487,1844
6201,18446249,18446567,18447419,18447467,18447617,18447629,18448271,18448301,18448931,
18449411,18449531,174

Заставила программку посчитать количество чисел в массиве, она посчитала - их здесь 174.
Теперь я могу взять этот массив и в Бейсике проверить, есть ли в нём симметричные кортежи длины 9. Программка в Бейсике выглядит так:

FOR I=1 TO N-8
Z=2*P(I+4)
IF P(I)+P(I+8)=Z THEN IF P(I+1)+P(I+7)=Z THEN IF P(I+2)+P(I+6)=Z THEN IF P(I+3)+P(I+5)=Z THEN PRINT #1,P(I);
NEXT I

(N - количество чисел в массиве, в данном примере $N=174$)
Всё проще пареной репы.

Мне очень хотелось бы узнать, как всё это делать в одной программе на PARI/GP.
Обратилась с просьбой помочь к одному форумчанину, он прислал такую программу:

timer = 1; /* включаем таймер */

/* функция check проверяет вектор v длины 9 на симметричность */
check(v) = {
my(S = 2*v[5]);
if((v[1]+v[9] == S) && (v[2]+v[8] == S) && (v[3]+v[7] == S) && (v[4]+v[6] == S), return(1), return(0))
}

N = 0;
Primes = vector(10000000);
forprime(p = 1, 10^9, if(ispseudoprime(p+2), N++; Primes[N] = p; if(N == 10000000, break)));
print("N = ", N, ", last prime = ", Primes[N]);
for(i = 1, N-8, v = Primes[i..i+8]; if(check(v), print(v)))

Алгоритм тот же: сначала формируется массив первых чисел в парах простых-близнецов, а потом в этом массиве ищем симметричные кортежи длины 9.
Я проверила эту программку, для указанного в программе интервала она работает хорошо.
Но! Попробовала чуть увеличить интервал, дальше мне ведь надо проверять. И всё! Программе банально не хватает памяти. Увеличила размер памяти до 512 Мб, всё равно не хватает.
Следовательно, алгоритм этот плохой. Или же надо формировать не весь сразу массив, а по частям.
Недаром whitefox в своей программе с использованием генератора primesieve проверял интервалами длины 2 млрд. И даже для записи простых чисел в таком небольшом интервале генератор требовал около 500 Мб памяти.

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

Ах да, конечно, можно в предложенной программе на PARI/GP тоже проверять, скажем, интервалами длины 1 млрд. Но... не выполнять же программу $10^n$ раз подряд
Надо, чтобы эта проверка такими маленькими порциями была автоматической, как в программе whitefox.
Вот как это сделать
Это, наверное, знает maxal.
Может быть, подскажет