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

[Nataly-Mak]

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

maxal в сообщении #1035802 писал(а):

При желании можно зафиксировать конкретные значения разностей (например, соответствующие минимальной длине 60) и просеивать простые числа... Jarek, скорее всего, так и делал.

Как действовали Jarek и Jens K Andersen можно посмотреть здесь
http://www.primepuzzles.net/conjectures/conj_042.htm

Здесь maxal говорит как раз о поиске кортежа по заданному паттерну.

И далее моя ссылка на головоломку, в которой была найдена первая в истории КПППЧ длины 16, давшая пандиагональный квадрат 4-го порядка из последовательных простых чисел.

Никак не могу вникнуть в суть этой головоломки.
Но дальше сценарий очевиден. Jarek гениально находит паттерн, а Jens K Andersen по этому паттерну находит реальный кортеж. Всё чётко.
Jens K Andersen сначала не рассчитывал на быстрый успех поиска реального кортежа по найденному Jarek паттерну. Вот что он писал:

Цитата:

The smallest admissible a's and b's is a1,a2,a3,b1,b2,b3 = 6,10,16,18,60,78 [as argued by J. W.]. The 16 wanted primes are then p + 0, 6, 10, 16, 18, 24, 28, 34, 60, 66, 70, 76, 78, 84, 88, 94. This is quite feasible. The estimate may be a GHz month for my program. I don't want to run it for long but if others do then mail me.
p=86987701136250973 is only missing p+70 and p+84. Both are semiprimes.

Как я понимаю, он оценивал время поиска по его программе примерно месяц. Он даже нашёл приближение к решению с двумя дырками: $p+70$ и $p+84$.
А потом повезло

Цитата:

p=320572022166380833 is the smallest solution. It has verified rank=2.
I arbitrarily chose to make a 9-hour search ending at 1600000*31# = 320896784208000000. The chance was small but p was 99.9% into the search space. Lucky!

Интересен вопрос: а КПППЧ, найденная maxal и давшая первый в истории минимальный пандиагональный квадрат 4-го порядка из последовательных простых чисел, является решением этой головоломки

[Nataly-Mak]

DanilovV в сообщении #1040749 писал(а):

... с фрактальной симметрией.

Поискала в русской Википедии статью "Фрактальная симметрия", не нашла.
В английской кое-что есть.
Картинка понравилась в статье (A Julia set has scale symmetry)

Да, фрактальная симметрия в 16-tuples явление весьма интересное и, наверное, мало изученное.
Удивляет огромное количество КПППЧ длины 16, их много тысяч! Это только реальных КПППЧ, не говоря о всех теоретически возможных паттернах.

DanilovV
вы нашли хотя бы один паттерн с фрактальной симметрией?

[Nataly-Mak]

DanilovV в сообщении #1040749 писал(а):

Может среди КПППЧ длиной 16 еще большая симметрия?
Возьмем четыре четных разности $ a,b,c,d $ и из них составим такую последовательность

a b a c a b a d a b a c a b a

с фрактальной симметрией. Можно на основе её составить паттерн

0 a a+b a+b+a a+b+a+c ...

Не совсем поняла, что это за последовательность:

a b a c a b a d a b a c a b a

(кстати, по-моему, в ней одного члена не хватает - последнего)
и как на её основе дальше составляется паттерн.

Но рассмотрела паттерн Jarek, он вроде составляется по этой схеме при следующих чётных разностях:

$a=6, b=4, c=2, d=26$

Как по-вашему: этот паттерн обладает фрактальной симметрией?
Паттерн Jarek напомню:

{0, 6, 10, 16, 18, 24, 28, 34, 60, 66, 70, 76, 78, 84, 88, 94}

[DanilovV]

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

Но рассмотрела паттерн Jarek, он вроде составляется по этой схеме при следующих чётных разностях:
$a=6, b=4, c=2, d=26$

Совершенно верно

6 4 6 2 6 4 6 26 6 4 6 2 6 4 6

[Nataly-Mak]

Ага, теперь я поняла, что за последовательность

6 4 6 2 6 4 6 26 6 4 6 2 6 4 6

Возникла гипотеза, что любая КПППЧ длины 16, дающая пандиагональный квадрат 4-го порядка, обладает такой же фрактальной симметрией.

Беру первую попавшуюся КПППЧ, из которой построен пандиагональный квадрат:

11796223202765101: 0 22 36 58 90 112 126 148 210 232 246 268 300 322 336 358

Точно!

$a=22, b=14, c=32, d=62$

22 14 22 32 22 14 22 62 22 14 22 32 22 14 22

Здорово!

Так, может быть, верна и более сильная гипотеза: пандиагональный квадрат 4-го порядка из элементов КПППЧ можно построить тогда и только тогда, когда КПППЧ обладает такой фрактальной симметрией

-- Пн июл 27, 2015 17:32:47 --

Гипотезы обе неверны.

[Begemot82]

В своих диапазонах нашел для

 23653934725904299: 0 12 22 34 48 60 70 82 90 102 112 124 138 150 160 172

разности $a=12, b=10, c=14, d=8$

  12  10  12  14  12  10  12  8  12  10  12  14  12  10  12

Осталось проверить на минимальность
Добавлено:
так это квадрат!

[Nataly-Mak]

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

Осталось проверить на минимальность

Не поняла. На минимальность чего проверить? Диаметр явно не минимальный. И КПППЧ длины 16 тоже не минимальная.
Это же найденный вами пандиагональный квадрат:

23653934725904299: 0 12 22 34 48 60 70 82 90 102 112 124 138 150 160 172
0  160  60  124
82  102  22  138
112  48  172  12
150  34  90  70

$S=94615738903617540$

-- Пн июл 27, 2015 19:05:09 --

Ага, добавили Так этот квадрат уже давно вами выложен.
А какую минимальность вы собирались проверить?

[Begemot82]

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

А какую минимальность вы собирались проверить?

Что число 23653934725904299 минимальное с такими свойствами

[Nataly-Mak]

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

В своих диапазонах нашел для

 23653934725904299: 0 12 22 34 48 60 70 82 90 102 112 124 138 150 160 172

разности $a=12, b=10, c=14, d=8$

  12  10  12  14  12  10  12  8  12  10  12  14  12  10  12

Так, стоп!
А эта КПППЧ не решает эту головоломку
Я что-то никак не пойму суть этой головоломки.

А, наверное, нет. Ведь найденное там решение имеет диаметр 94. Видимо, там как раз требуется минимальный диаметр.

[Dmitriy40]

Написал программу поиска КПППЧ по заданному шаблону, правда пока исходные данные надо задавать руками в тексте программы. Искать короткие КПППЧ смысла нет, они слишком часто встречаются, вот поискать что-то редкое можно попробовать, чем и занялся. Выбрал один из паттернов КПППЧ длиной 26 и задал поиск во всём диапазоне 0-9е18. Список возможных начальных чисел формируется меньше часа, но он выходит огроменным, почти 8ГБ или 970млн штук (но 75% из них исключаются быстрой проверкой на первые 1000 простых чисел), проверка их всех на простоту всех 26-ти входящих чисел займёт по прикидкам около полугода (в одном потоке) даже с использованием primesieve. И это одного достаточно редкого паттерна. И без всякой гарантии что он вообще встретится. Учитывая что первыми попадаются паттерны вовсе не с минимальным диаметром (которые как раз более редкие), то искать другие паттерны будет ещё медленнее. Да, конкретно этот паттерн намного быстрее полной проверки диапазона, но полгода на один паттерн ...

Искать сразу несколько паттернов будет медленнее практически линейно (за некоторыми исключительными случаями), т.к. паттерны неплохо перемешаны на интервалах чисел и увеличение их количества уменьшает среднюю дистанцию между соседними вероятными точками вхождения паттернов, что приводит к линейному росту времени общей проверки (время проверки каждого вероятного вхождения практически стабильно). С другой стороны, паттерны расположены относительно далеко друг от друга и объединить их в общий проверяемый интервал не получается - или это приводит к объединению всех интервалов и возврату к непрерывной проверке всей числовой оси.
Искать 10 разных паттернов одной программой или 10-ю программами разницы почти нет, требования к памяти для чисел до 1е17 терпимы, для 9е18 конечно больше, до 600МБ на задачу.

По цифрам.
Для чисел около 2е16 одиночный запуск primesieve требует около 0.1с, моя программа тратит примерно 0.06с на проверку одного вхождения паттерна, думаю интегрировав primesieve в программу можно добиться времени порядка 0.03с на вхождение. 0.06с * 250млн / 86400 = 170 суток (на один поток). Но время проверки растёт с увеличением чисел, около 1е18 primesieve требует уже 0.7с (моя 0.4с на одно вхождение паттерна), так что оценка в пару сотен суток работы одного потока близка к реальности. Для одного единственного паттерна, без всякой надежды его нахождения - столько времени жалко.

Для данного паттерна КПППЧ длиной 26 получалось примерно одно вероятное вхождение на 3млрд чисел. Это очень хороший результат (число достаточно велико чтобы имело смысл запускать проверку), почему собственно этот паттерн и был выбран. Для одного из редких паттернов для КПППЧ длиной 17 одно вхождение будет примерно на 4млн - и смысл проверять лишь точки возможных вхождений паттерна исчезает.

Для сравнения, о primesieve, запуск проверки одного вхождения занимает 0.1с, за это же время можно полностью проверить интервал длиной более 70млн. Т.е. проверка вхождений паттернов невыгодна для интервалов между вхождениями любого из паттернов менее сотни миллионов.


Так что я разочаровался в поиске КПППЧ по паттернам.
Он имеет смысл лишь для достаточно редких КПППЧ, а они явно где-то далеко по величине своих чисел, найти их до 9е18 малореально, а затраты на такой поиск достаточно велики (годы работы одного потока выполнения).

[Nataly-Mak]

Вопреки поговорке, чем дальше в лес - тем меньше дров



Зато чуть-чуть увеличилась скорость.
Нашла уже 915 КПППЧ длины 16 и ни одного квадрата.
Есть несколько 18-ок и 20-ок, 22-ок и 24-ок нет.

После двух квадратов, найденных Begemot82, наверное, надолго мы без квадратов.
А ice00 делает программное обеспечение для конкурса. Может быть, конкурс кого-нибудь заинтересует. Робкая такая надежда.

[Dmitriy40]

Проверил интересную вещь: оказывается из КПППЧ длиной 16 и диаметрами 74, 76, 86, 88, 92 квадрат не собирается! Т.е. для диаметров до 100 возможны только квадраты с диаметрами 82 (один вариант, не найден), 94 (два варианта, найден один), 98 (один вариант, не найден), 100 (один вариант, не найден). Во как, однако.
Для диаметров до 200 (включительно) возможны всего 373 разных паттерна КПППЧ.
При этом для диаметров 82, 98, 100, 104, 116, 124, 130, 168 - лишь по одному варианту паттерна.
Интересно будет поискать квадрат из КПППЧ диаметром 82 ... Будет абсолютный рекорд компакности квадрата.

[Begemot82]

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

Интересно будет поискать квадрат из КПППЧ диаметром 82 ... Будет абсолютный рекорд компакности квадрата

Интересно будет посмотреть на паттерн

[Nataly-Mak]

Скормила своей программе поиска ассоциативных квадратов Стенли 4-го порядка (из которых получаются потом пандиагональные квадраты) этот набор:

0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 50 52 54 56 58 60 62 64 66 68 70 72 74 76 78 80 82

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

(Оффтоп)

0  2  8  10 
 4  6  12  14 
 68  70  76  78 
 72  74  80  82 

 0  2  10  12 
 4  6  14  16 
 66  68  76  78 
 70  72  80  82 
 
 0  2  12  14 
 4  6  16  18 
 64  66  76  78 
 68  70  80  82 

 0  2  14  16 
 4  6  18  20 
 62  64  76  78 
 66  68  80  82 

 0  2  16  18 
 4  6  20  22 
 60  62  76  78 
 64  66  80  82 

 0  2  18  20 
 4  6  22  24 
 58  60  76  78 
 62  64  80  82 

 0  2  20  22 
 4  6  24  26 
 56  58  76  78 
 60  62  80  82 
 
 0  2  22  24 
 4  6  26  28 
 54  56  76  78 
 58  60  80  82 

 0  2  24  26 
 4  6  28  30 
 52  54  76  78 
 56  58  80  82 
 
 0  2  26  28 
 4  6  30  32 
 50  52  76  78 
 54  56  80  82

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

Ранжирование элементов квадрата можно вставить в программу построения квадратов, которая у вас есть.
Потом берёте каждый готовый паттерн и проверяете его в том сервисе.

-- Вт июл 28, 2015 17:52:35 --

Кстати, подскажите, пожалуйста, команду сортировки массива в Power Basic.
Элементы квадрата - это массив $A(i)$, ($i=1,2,3,...,16$).
Вот этот массив надо ранжировать. Кажется, есть такая команда (?)
У меня вообще-то есть программка для ранжирования массивов. Можно и эту программку вставить в программу, тоже годится как вариант.

[Begemot82]

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

Кажется, есть такая команда (?)

ARRAY SORT A()
$ 0, 2, 4, 6$ не катит по модулю 3