2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1 ... 10, 11, 12, 13, 14, 15, 16 ... 18  След.
 
 Re: Симметричные кортежи из последовательных простых чисел
Сообщение06.10.2015, 15:22 
Заслуженный участник


20/08/14
8879
Россия, Москва
Begemot82 в сообщении #1059565 писал(а):
Nataly-Mak в сообщении #1059528 писал(а):
Это происходит от частого обращения к функции nextprime().
Вместо вызова nextprime() для второго кандидата в близнецы можно использовать более быструю функцию проверки на простоту ispseudoprime().
А ещё лучше вообще не вызывать ни nextprime ни ispseudoprime внутри цикла forprime и хранить всё в переменных. Сейчас в программе каждое число (не только простое!) проверяется на простоту аж 14 раз вместо одного раза!

-- 06.10.2015, 15:26 --

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

 Профиль  
                  
 
 Re: Симметричные кортежи из последовательных простых чисел
Сообщение06.10.2015, 20:05 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Задача получения массива, состоящего из первых чисел пар простых чисел-близнецов действительно простая.
Выполняю программку
Код:
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

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

 Профиль  
                  
 
 Re: Симметричные кортежи из последовательных простых чисел
Сообщение07.10.2015, 08:28 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Nataly-Mak в сообщении #1059528 писал(а):
Итак, 17-ый член последовательности A035795 найден.
Дальше запустила поиск.

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

 Профиль  
                  
 
 Re: Симметричные кортежи из последовательных простых чисел
Сообщение07.10.2015, 10:24 
Заблокирован
Аватара пользователя


22/03/08

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

 Профиль  
                  
 
 Re: Симметричные кортежи из последовательных простых чисел
Сообщение07.10.2015, 15:13 
Заслуженный участник


20/08/14
8879
Россия, Москва
Nataly-Mak в сообщении #1060085 писал(а):
Загрузка процессора - 100%, использование памяти - 38%. Да, очень экономно PARI/GP использует память.

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

 Профиль  
                  
 
 Re: Симметричные кортежи из последовательных простых чисел
Сообщение07.10.2015, 16:51 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
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);
); }

я её всё-таки уломала (долго уламывала :D ), она у меня заработала:
Код:
{ 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 будет пошустрее работать.

 Профиль  
                  
 
 Re: Симметричные кортежи из последовательных простых чисел
Сообщение07.10.2015, 18:53 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Ура!
Вот она - ещё одна великолепная семёрка близнецов:
Код:
[793957831409, 793957831411, 793957831439, 793957831441, 793957831487, 793957831489, 793957831559, 793957831561, 793957831571, 793957831573, 793957831607, 793957831609, 793957831631, 793957831633]

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

 Профиль  
                  
 
 Re: Симметричные кортежи из последовательных простых чисел
Сообщение07.10.2015, 20:09 
Заслуженный участник


20/08/14
8879
Россия, Москва
Ещё 11ч назад было:
Begemot82 в сообщении #1060018 писал(а):
Новинки для A035795
Код:
18 793957831409
19 808316366171
И только что (уже 20-й член):
Begemot82 в сообщении #1060310 писал(а):
Еще семерочка выскочила.

 Профиль  
                  
 
 Re: Симметричные кортежи из последовательных простых чисел
Сообщение07.10.2015, 20:25 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
А вот и 19-ая великолепная семёрка :roll:
Код:
[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-го порядка.

 Профиль  
                  
 
 Re: Симметричные кортежи из последовательных простых чисел
Сообщение08.10.2015, 02:45 


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

 Профиль  
                  
 
 Re: Симметричные кортежи из последовательных простых чисел
Сообщение08.10.2015, 05:40 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Это решение 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-го порядка :roll:
По значению первого элемента кортежа p это не минимальная КПППЧ такого рода; у Jarek есть с меньшим значением.
Значит, и квадрат, составленный из его КПППЧ, имеет меньшую магическую константу. У Jarek есть и другие подобные решения.

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

 Профиль  
                  
 
 Re: Симметричные кортежи из последовательных простых чисел
Сообщение08.10.2015, 06:40 
Заслуженный участник


20/08/14
8879
Россия, Москва
Nataly-Mak в сообщении #1060400 писал(а):
По значению первого элемента кортежа p это не минимальная КПППЧ такого рода; у Jarek есть с меньшим значением.
Значит, и квадрат, составленный из его КПППЧ, имеет меньшую магическую константу.
За свои слова принято отвечать - приведите решение с КПППЧ по данному паттерну с меньшим начальным числом? Я вот уверен что это именно минимальная КПППЧ.

 Профиль  
                  
 
 Re: Симметричные кортежи из последовательных простых чисел
Сообщение08.10.2015, 11:34 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Ну вот, 20-ая семёрочка нашлась:
Код:
[881191407827, 881191407829, 881191407839, 881191407841, 881191407851, 881191407853, 881191407911, 881191407913, 881191407977, 881191407979, 881191408157, 881191408159, 881191408169, 881191408171]

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

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

 Профиль  
                  
 
 Re: Симметричные кортежи из последовательных простых чисел
Сообщение08.10.2015, 14:16 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
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]

 Профиль  
                  
 
 Re: Симметричные кортежи из последовательных простых чисел
Сообщение09.10.2015, 07:29 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Дошла до $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.
Может быть, подскажет :wink:

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 257 ]  На страницу Пред.  1 ... 10, 11, 12, 13, 14, 15, 16 ... 18  След.

Модераторы: maxal, Toucan, PAV, Karan, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group