Модифицировать программу (практическая помощь)

[Begemot82]

Интервал $[25 \cdot 10^{15},26 \cdot 10^{15}]$ проверен. Квадраты не найдены.

[Nataly-Mak]

Begemot82
Спасибо.

Итак, до точки
28574813652605788
у нас всё полностью проверено.

[Begemot82]

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

Итак, до точки
28574813652605788
у нас всё полностью проверено.

А $ [26 \cdot 10^{15},27 \cdot 10^{15}]$ проверен?

[Nataly-Mak]

Об интервале [$27 \cdot 10^{15},28 \cdot 10^{15}$] сообщал Dmitriy40.
А о предыдущем... да, не знаю. Виновата, что-то пропустила. Возможно, об этом интервале и не было сообщений.

[Nataly-Mak]

О новой программке расскажу, может быть, кто-то заинтересуется, модифицирует её, чтобы побыстрее работала.

В программе ищем максимумы разностей в тройках последовательных простых чисел, разность вычисляется между третьим и первым числами в тройке. Это последовательности в OEIS A031132/A031133/A031134
Я рассказала об этой задачке Vovka17, он заинтересовался, сделал программку, "прикрутив" к ней генератор primesieve. Мы очень быстро по этой программе нашли несколько новых результатов.
Наш вклад в указанные последовательности OEIS

63 471911699385743:d=972
64 528459528877303:d=1014
65 543684371470039:d=1016
66 811782668946191:d=1032
67 1693182318747503:d=1152

Мы проверили до точки $196 \cdot 10^{13}$. Последняя, найденная нами, максимальная разность 1152.
Дальше пока остановили поиск. Но при желании можно продолжить.

Программка Vovka17 выглядит очень изящно (в окошечке) и работает достаточно быстро.


Это я сейчас решила продолжить (пока наступил сильнейший кризис в симметричных кортежах из последовательных простых чисел).
Написала программку для этого поиска на PARI/GP

{i=12;
forprime(n=83,199, p=nextprime(n+1); q=nextprime(p+1); if( q-n>i, i=q-n; print(i) ) )
}

Ну, этот примерчик, конечно, считается мгновенно тут считать нечего.
А вот если написать так:

{i=1152;
forprime(n=1960000000000000,1960001000000000, p=nextprime(n+1); q=nextprime(p+1); if( q-n>i, i=q-n; print(i) ) )
}

то программа о-ч-ч-ч-е-н-ь надолго задумывается.
У меня есть сильное подозрение, что оператор forprime работает очень медленно.
Поэтому пока отдаю предпочтение программе Vovka17.

Интересно: на основе данных из Википедии я составила прогнозы следующих максимальных разностей (причём прогнозы составлены до того, как была найдена разность 1152, и этот прогноз подтвердился):

1693182318746371: -20 [phone]
43841547845541059: -10 [phone]
55350776431903243: -92 [phone]
80873624627234849: -66 [phone]
218034721194214273: -54 [phone]
352521223451364323: -54 [phone]
401429925999153707: -30 [phone]
418032645936712127: -18 [phone]
804212830686677669: -120 [phone]

Прогнозы могут совпасть, а могут и не совпасть.

Приглашаю всех
1. модифицировать программу поиска с целью убыстрения;
2. принять участие в поиске.

[Dmitriy40]

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

Приглашаю всех

Поясните для всех в чём смысл этого поиска, кроме как найти и добавить новые члены в последовательности OEIS?

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

{i=12;
forprime(n=83,199, p=nextprime(n+1); q=nextprime(p+1); if( q-n>i, i=q-n; print(i) ) )
}

Данную программу можно ускорить минимум втрое если убрать двойной вызов nextprime внутри цикла, а сохранять два предыдущих простых числа в переменных. Готовый пример как это правильно сделать есть в A031133.

[Begemot82]

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

43841547845541059: -10 [phone]
55350776431903243: -92 [phone]

43841547845541059: 0 (1184) 1184 ( 18 ) 1202 
55350776431903243: 0 (1192) 1192 ( 236 ) 1428 

Для $55350776431903243$ сильный промах. Прогноз $1284$, но уже разность достигает $1428$ и понятно, что она может только увеличиться. Также $1428$ уже больше для 5 еще прогнозов.

(Оффтоп)

Цитата:

Прогнозы могут совпасть, а могут и не совпасть.

:lol1:

Какой же прогноз был для $1693182318746371$, что он так удачно подтвердился?
+
Разности около $1693182318746371$ удачно совпали, симметрия уже не отпустит.

[Dmitriy40]

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

У меня есть сильное подозрение, что оператор forprime работает очень медленно.

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

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

Опыт показывает, что чистая forprime для чисел порядка $10^{15}$ работает со скоростью примерно 2млн/с или 7млрд/ч. С primesieve сравните сами.

[Nataly-Mak]

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

67 1693182318747503:d=1152[/code]
Мы проверили до точки $196 \cdot 10^{13}$. Последняя, найденная нами, максимальная разность 1152.

Пока проверила очень мало, изредка кручу эту программку. Дошла до 2025524998311781.
Разностей больше последнего максимума 1152 пока не было.

-- Вт окт 13, 2015 23:33:44 --

А теперь опять о модификации программы whitefox.
Постановка задачи

берём массив первых чисел в парах простых чисел-близнецов, например:

. . . . . . . . 
199994369
199995179
199995239
199995611
199996241
199996757
199997339
199997387
199997417
199997867
199998479
199998749
199999277
199999307
199999607
199999901
200000081
200000237
200000831
200000987
200001929
200002079
200002487
200003057
200003339
200003591
200003801
. . . . . . . . 

Конечно, брать его надо с самого начала натурального ряда, здесь приведён пример куска массива.
Теперь рассматриваем наборы по 9 чисел массива, следующих подряд, и ищем симметричные наборы (кортежи).
Дальше надо будет из этих симметричных кортежей пытаться составить магический квадрат 3-го порядка.

Такая вот простая задача никак не решается. Задача очень давно опубликована в головоломке на сайте primepuzzles.net
Сейчас снова занялась этой задачей. Мне помогли написать программку на PARI/GP.
Ну, нашла я по этой программке один симметричный кортеж длины 9:

54793185527: 0, 132, 462, 642, 1032, 1422, 1602, 1932, 2064

Магический квадрат 3-го порядка из чисел этого кортежа, конечно, не составился.

Дальше запускаю программу на проверку интервала длиной всего 410 млрд. Программа работает уже 10 часов и ещё не закончила проверку. Это безобразно долго!
Вот текст программы:

checktuple(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))
}
changetuple(v,p) = vector(9, i, if(i<9, v[i+1], p));
tuple = [89999996927, 89999997377, 89999997629, 89999997707, 89999997749, 89999997797, 89999998799, 89999999069, 89999999357];
forprime(p = nextprime(tuple[9]+1),5*10^11, if(ispseudoprime(p+2), tuple = changetuple(tuple,p); if(checktuple(tuple), print(tuple); break)));
print(tuple)

Либо программа написана из рук вон плохо, либо PARI/GP не годится для подобного рода задач.

Что делала бы программа whitefox?
Элементарно: с помощью генератора primesieve программа генерирует в интервале длины 2 млрд все простые-близнецы (да даже просто все простые числа!), быстренько проверяет сформированный массив на наличие в нём нужных кортежей длины 9; снова генерирует и снова проверяет.
Скорость в этой программе будет около 800 млрд/час.

[Dmitriy40]

Цитата:

Ну а в такой формулировке быстрее всего будет получать готовые twin primes от primesieve и разбирать её текстовый выход.

Кстати, вполне вероятно что так оно будет работать даже быстрее, чем в составе единой однопоточной программы: сама primesieve и программа-обработчик её текстового выхлопа могут работать на разных ядрах одновременно, а не последовательно (как в случае с модификацией программы whitefox). Во избежание критики мол домыслы, именно так оно у меня и работает, общая скорость ограничивается скоростью primesieve, а не связки из обеих программ. И если для получения простых чисел тормозит скорость пересылки текстовых данных, то для близнецов и более сложных структур скорость пересылки ниже во много раз и замедления не оказывает.
Так что не вижу особого смысла в очередной модификации программы whitefox - написать обработку текста на любом удобном языке программирования проще модификации программы на С++, а работать может даже быстрее.

[Nataly-Mak]

Продолжаю проверять по этой программке, так как ничего другого (лучшего) у меня пока нет.
Нашла ещё один симметричный кортеж длины 9:

403147629431: 0, 126, 420, 750, 768, 786, 1116, 1410, 1536

Или кортеж длины 18:

403147629431: 0, 2, 126, 128, 420, 422, 750, 752, 768, 770, 786, 788, 1116, 1118, 1410, 1412, 1536, 1538

Магический квадрат 3-го порядка не составился.
Сейчас проверяю небольшими порциями - по 5 млрд. Так программка хорошо справляется.
Тише едешь - дальше будешь

[Dmitriy40]

Nataly-Mak
Кажется пропустили ещё два паттерна:
354584248349: 0 132 372 678 900 1122 1428 1668 1800
388743941039: 0 42 240 282 450 618 660 858 900

[Nataly-Mak]

Ещё один симметричный кортеж нашёлся:

463060598321: 0, 390, 906, 1116, 1218, 1320, 1530, 2046, 2436
463060598321: 0, 2, 390, 392, 906, 908, 1116, 1118, 1218, 1220, 1320, 1322, 1530, 1532, 2046, 2048, 2436, 2438

Интересная начинает выявляться особенность: нужные кортежи имеют очень большие диаметры.
Получается, что близнецы редко бывают расположены достаточно плотно.
Посмотрела чуть-чуть на КПППЧ длины 18, имеющиеся у меня в архиве. С ходу увидела только несколько КПППЧ с 4 парами близнецов, например:

873860248704797: 0 2 12 72 120 132 134 170 182 252 264 300 302 314 362 422 432 434

С 5 парами пока не высмотрела, визуально трудно высмотреть.
Ну, в общем, тенденция ясная: шансы на 9 близнецов есть только у КПППЧ с большими диаметрами.

Завтра продолжу проверку.

[Nataly-Mak]

Посмотрела в головоломке наборы из 9 пар близнецов подряд (между ними нет других простых чисел):

170669145704411: 0, 2, 90, 92, 96, 98, 180, 182, 228, 230, 258, 260, 336, 338, 396, 398, 408, 410
1980326398382819: 0, 2, 48, 50, 60, 62, 168, 170, 180, 182, 198, 200, 240, 242, 342, 344, 552, 554
4518517172328671: 0, 2, 78, 80, 108, 110, 120, 122, 150, 152, 198, 200, 210, 212, 246, 248, 336, 338

Вот такая компактность 9 пар близнецов (без лишних простых чисел между ними) очень редко встречается.
Хорошие кортежи из последоваетльных простых чисел, но... не симметричные. Значит, для нашей задачи не годятся.
Интересно, какой теоретический минимальный диаметр у такого рода кортежей? Здесь пока имеем наименьший диаметр 338.
Вообще для не симметричных кортежей длины 18 из последовательных простых чисел минимальный диаметр равен 70.

В головоломке есть ещё наборы из 10 и 11 пар подряд. Надо их рассмотреть, в них ведь тоже есть наборы по 9 пар близнецов.

-- Пт окт 16, 2015 07:38:18 --

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

3324648277099157: 0, 2, 54, 56, 72, 74, 84, 86, 150, 152, 162, 164, 180, 182, 240, 242, 264, 266
3324648277099211: 0, 2, 18, 20, 30, 32, 96, 98, 108, 110, 126, 128, 186, 188, 210, 212, 240, 242

Уже поменьше есть диаметр - 242.

-- Пт окт 16, 2015 07:55:59 --

И ещё несколько аналогичных кортежей, полученных из десяточек:

31910610414019031: 0, 2, 36, 38, 60, 62, 156, 158, 186, 188, 198, 200, 210, 212, 270, 272, 378, 380
31910610414019067: 0, 2, 24, 26, 120, 122, 150, 152, 162, 164, 174, 176, 234, 236, 342, 344, 390, 392
9224121946845515441: 0, 2, 96, 98, 186, 188, 198, 200, 216, 218, 270, 272, 336, 338, 378, 380, 408, 410
9224121946845515537: 0, 2, 90, 92, 102, 104, 120, 122, 174, 176, 240, 242, 282, 284, 312, 314, 324, 326
9226245365154613667: 0, 2, 84, 86, 132, 134, 144, 146, 174, 176, 180, 182, 282, 284, 312, 314, 354, 356
9226245365154613751: 0, 2, 48, 50, 60, 62, 90, 92, 96, 98, 198, 200, 228, 230, 270, 272, 348, 350

Интересные экземпляры. Жалко, что все не симметричные.

Сейчас ещё рассмотрю единственный набор из 11 пар близнецов, приведённый в головоломке.

-- Пт окт 16, 2015 08:08:56 --

Вот последние три кортежа (из 11-ки):

789795449254776509: 0, 2, 18, 20, 42, 44, 72, 74, 108, 110, 138, 140, 240, 242, 252, 254, 270, 272
789795449254776527: 0, 2, 24, 26, 54, 56, 90, 92, 120, 122, 222, 224, 234, 236, 252, 254, 300, 302
789795449254776551: 0, 2, 30, 32, 66, 68, 96, 98, 198, 200, 210, 212, 228, 230, 276, 278, 318, 320

Пока наименьший диаметр 242.

[Begemot82]

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

Интересно, какой теоретический минимальный диаметр у такого рода кортежей? Здесь пока имеем наименьший диаметр 338.

Минимальный диаметр последовательных 9 пар близнецов 104. Два паттерна из четырех

[-31,-29, -19,-17, -13,-11, 11, 13, 17,19, 29,31, 41,43, 59,61, 71,73]
[-43,-41, -31,-29, -19,-17,-13,-11, -1, 1, 11,13, 17,19, 41,43, 59,61]

Квадраты не образуются.