2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 12, 13, 14, 15, 16
 
 Re: Антимагические квадраты
Сообщение11.04.2014, 09:51 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Nataly-Mak в сообщении #847890 писал(а):
Зря, стало быть, я сменила начальную точку в проверке?

Вернулась к той точке, на которой прервала. Проверяю опять всё подряд. На данный момент проверено до 10 510 999 343 406 (то есть от начала проверки чуть больше 3 триллионов). Программа whitefox работает. Ловлю удачу :D

 Профиль  
                  
 
 Re: Антимагические квадраты
Сообщение12.04.2014, 06:50 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Решила изменить тактику.
Уже проверены интервалы:

7499999900000 - 11612999098199 (от начальной точки maxal, немножко с откатом назад)

19787844669502 - 20841844431437 (от начальной точки Jens K Andersen)

А сегодня решила начать с 120 триллионов, то есть резко увеличила начальную точку.
Напомню, финиш - 320572022166380833.

"Мой финиш - горизонт..." (c)

Эх, вот как нужен тут проект распределённых вычислений :idea:

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


22/03/08

7154
Саратов
Производительность моего компьютера такая: за 1 час 14 минут проверены все простые в интервале длиной в 100 миллиардов натуральных чисел.
Программа whitefox сделана так, что проверяет интервалы по 2 миллиарда натуральных чисел (с небольшим наложением на стыке интервалов).

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


22/03/08

7154
Саратов
Квадраты Стенли у меня несколько отодвинуты в связи с конкурсом.

А между тем, Carlos Rivera опубликовал вторую часть головоломки - ассоциативные квадраты Стенли из последовательных простых чисел
http://www.primepuzzles.net/puzzles/puzz_736.htm

Теперь решаем задачу официально :D
Отправляем решения на сайт http://www.primepuzzles.net

 Профиль  
                  
 
 Re: Антимагические квадраты
Сообщение14.06.2014, 00:10 
Заслуженный участник
Аватара пользователя


09/02/09
2086
Минск, Беларусь
Nataly-Mak в сообщении #842539 писал(а):
Итого в интервале [2, 200 000 000] 11078937 простых чисел.

Кстати, простые числа в указанном интервале программой svb генерируются за несколько секунд. Проверяется одна такая порция по моей программе 3-5 секунд.
Намного быстрее программа primesieve: http://primesieve.org/

На моём 4-летнем компе её старая версия 3.8 находит простые примерно вот с такой скоростью:
http://www.primefan.ru/stuff/pict/benchmark.gif

Она умеет также печатать список найденных простых.

Yadryara в сообщении #842556 писал(а):
Альфа удобна для вычисления $\pi(x)$ для сравнительно небольших $x$ — примерно до триллиона ($10^{12}$). Дальше не справляется.
Если стоит задача не найти все простые вплоть до заданной нетривиальной границы, а лишь посчитать их число $\pi(x)$, то неплохим вариантом является программа fastpix, написанная в 2001 году математиком по имени Xavier Gourdon. Вот инструкция к её использованию:
https://groups.yahoo.com/neo/groups/pri ... ages/23387

Для очень больших значений $x$ функция $\pi(x)$ быстрее рассчитывается аналитическими методами:
http://www.math.uni-bonn.de/people/jbue ... icPiX.html
Однако программ, реализующих эти методы, в открытом доступе пока не наблюдалось.

 Профиль  
                  
 
 Re: Антимагические квадраты
Сообщение31.07.2014, 17:30 
Модератор
Аватара пользователя


11/01/06
5660
Для полноты картины вот антимагический квадрат Стенли 4x4 составленный из минимальных последовательных простых чисел, полученный из этого пандиагонального магического квадрата:
Код:
[170693941183817 170693941183859 170693941183907 170693941183949]
[170693941183847 170693941183889 170693941183937 170693941183979]
[170693941183861 170693941183903 170693941183951 170693941183993]
[170693941183891 170693941183933 170693941183981 170693941184023]

Этот квадрат составлен из 16 последовательных простых чисел, начиная с 170693941183817 (см. A245721). Если его вычесть из остальных, то квадрат приобретает вид:
Код:
[ 0  42  90 132]
[30  72 120 162]
[44  86 134 176]
[74 116 164 206]

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


19/12/10
1546
maxal в сообщении #892112 писал(а):
Код:
[ 0 42 90 132]
[30 72 120 162]
[44 86 134 176]
[74 116 164 206]


Nataly-Mak в сообщении #891897 писал(а):
Код:
0 30 44 74
42 72 86 116
90 120 134 164
132 162 176 206


Два варианта одного и того же квадрата.
Его "каноническая форма" следующая:
Код:
[ 0 30 42 72]
[44 74 86 116]
[90 120 132 162]
[134 164 176 206]

Условие "каноничности" : $a_{12}<a_{13}<a_{21}<a_{31}$

 Профиль  
                  
 
 Re: Антимагические квадраты
Сообщение31.07.2014, 20:02 
Заслуженный участник
Аватара пользователя


09/02/09
2086
Минск, Беларусь
Droog_Andrey в сообщении #875189 писал(а):
Если стоит задача не найти все простые вплоть до заданной нетривиальной границы, а лишь посчитать их число $\pi(x)$, то неплохим вариантом является программа fastpix, написанная в 2001 году математиком по имени Xavier Gourdon. Вот инструкция к её использованию:
https://groups.yahoo.com/neo/groups/pri ... ages/23387
Недавно появилась более быстрая реализация от автора пакета primesieve:
https://github.com/kimwalisch/primecount

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


22/03/08

7154
Саратов
О поиске ассоциативного квадрата Стенли 9-го порядка из различных простых чисел
(по просьбе rockclimber)

rockclimber
Ср авг 20, 2014 писал:
Цитата:
Моя новая версия программы наконец-то заработала, и даже нашла второй квадрат 7-го порядка. А пока программа работала, я сделал кое-какие расчеты, результаты которых повергли меня в некоторое уныние. Я взял числа 3, 5 и 7 (порядки квадратов), выписал в экселе в столбик. В соседний столбик выписал минимальные центральные числа соответствующих квадратов (59, 701 и 25903). В следующем столбце посчитал логарифим центрального числа, в следующем - логарифм логарифма. Посчитал коэффициент корреляции - для столбца "логарифм логарифма" он оказался равен 0,9997. То есть получается, что минимальное центральное число квадрата пропорционально е в степени е в степени порядка квадрата, для квадрата девятого порядка тогда надо искать минимальный вариант где-то в районе 4 000 000, а для одиннадцатого - 7 700 000 000. Для одного простого числа около 200 000 перебор вариантов у меня занимает сейчас 12 минут, и это время тоже будет расти наверняка экспоненциально. Вы знаете еще какие-нибудь способы кардинально сократить время? Я применил все перечисленные вами и придуманные мной самим хитрости для уменьшения времени обработки, но объем работы по-прежнему огромный. Может, есть, например, способы проверять не все простые числа в качестве центральных, а некоторые пропускать?

А вот и отличное приближение к решению, в котором всего одно не простое число (оно помечено звёздочкой):

Код:
111053 114203 158747 181253 250703 320153 342659 387203 390353
336113 339263 383807 406313 475763 545213 567719 612263 615413
432413 435563 480107 502613 572063 641513 664019 708563 711713
797063 800213 844757 867263 936713 1006163 1028669 1073213 1076363*
1119473 1122623 1167167 1189673 1259123 1328573 1351079 1395623 1398773
1441883 1445033 1489577 1512083 1581533 1650983 1673489 1718033 1721183
1806533 1809683 1854227 1876733 1946183 2015633 2038139 2082683 2085833
1902833 1905983 1950527 1973033 2042483 2111933 2134439 2178983 2182133
2127893 2131043 2175587 2198093 2267543 2336993 2359499 2404043 2407193

Автор этого решения Progger. Решение было выложено автором на форуме ПЕН.

Progger
Вс мар 08, 2015 писал:
Цитата:
Пока продолжаю поиск квадрата Стенли 9-го порядка из различных простых чисел. Проверил до $3.66 \cdot 10^6$ ...

Progger
прошу прощения за маленькую цитату с важной информацией из вашего ЛС.
Вы продолжаете поиск?

 Профиль  
                  
 
 Re: Антимагические квадраты
Сообщение01.04.2015, 17:32 
Заслуженный участник


06/07/11
5627
кран.набрать.грамота
Nataly-Mak в сообщении #998945 писал(а):
О поиске ассоциативного квадрата Стенли 9-го порядка из различных простых чисел
Однако! Я и забыл уже про эти расчеты :mrgreen:
А Progger, тем временем, вплотную приблизился к расчетной точке! Интригующий момент!

 Профиль  
                  
 
 Re: Антимагические квадраты
Сообщение02.04.2015, 18:01 


27/08/14
206
Последнее проверенное число на данный момент - 4024357, полного квадрата пока не найдено. Есть 2 квадрата в которых только 1 элемент не является простым числом:
Код:
111053 114203 158747 181253 250703 320153 342659 387203 390353
336113 339263 383807 406313 475763 545213 567719 612263 615413
432413 435563 480107 502613 572063 641513 664019 708563 711713
797063 800213 844757 867263 936713 1006163 1028669 1073213 1076363*
1119473 1122623 1167167 1189673 1259123 1328573 1351079 1395623 1398773
1441883 1445033 1489577 1512083 1581533 1650983 1673489 1718033 1721183
1806533 1809683 1854227 1876733 1946183 2015633 2038139 2082683 2085833
1902833 1905983 1950527 1973033 2042483 2111933 2134439 2178983 2182133
2127893 2131043 2175587 2198093 2267543 2336993 2359499 2404043 2407193
Код:
1022849 1168169 1366829 1743569 2540339 3337109 3713849 3912509 4057829
1318781 1464101 1662761 2039501 2836271 3633041 4009781 4208441 4353761
1497719 1643039 1841699 2218439 3015209 3811979 4188719 4387379 4532699
1626239 1771559 1970219 2346959 3143729 3940499 4317239 4515899 4661219*
1652459 1797779 1996439 2373179 3169949 3966719 4343459 4542119 4687439
1678679 1823999 2022659 2399399 3196169 3992939 4369679 4568339 4713659
1807199 1952519 2151179 2527919 3324689 4121459 4498199 4696859 4842179
1986137 2131457 2330117 2706857 3503627 4300397 4677137 4875797 5021117
2282069 2427389 2626049 3002789 3799559 4596329 4973069 5171729 5317049

На самом деле их скорее всего больше, просто программа не предназначена для поиска неполных квадратов - они являются побочным продуктом и используются для статистики :-) .
Что интересно, в обоих случаях элементы, не являющиеся простыми числами, раскладываются на два простых числа:
$1076363 = 389 \cdot 2767$
$4661219 = 151 \cdot 30869$,
а их пары являются простыми числами.
Ну и немного статистики:
\begin{tabular}{|l|l|}
\hline
35 & 6707 \\ \hline
36 & 1664 \\ \hline
37 & 141  \\ \hline
38 & 17   \\ \hline
39 & 2    \\ \hline
\end{tabular}
Тут в первом столбце - количество простых чисел в квадрате (ищется 40 чисел), второй - количество таких квадратов.
В следующей таблице приведено распределение количества неполных квадратов по интервалам. Не знаю как это можно использовать :-) .

(большая таблица)

\begin{tabular}{|l|l|l|l|l|l|l|}
\hline
Начало & Конец & 39 & 38 & 37 & 36 & 35 \\ \hline
0       & 100000  & 0 & 0 & 0  & 0   & 0   \\ \hline
100000  & 200000  & 0 & 0 & 0  & 0   & 0   \\ \hline
200000  & 300000  & 0 & 0 & 0  & 0   & 1   \\ \hline
300000  & 400000  & 0 & 0 & 0  & 0   & 0   \\ \hline
400000  & 500000  & 0 & 0 & 0  & 0   & 1   \\ \hline
500000  & 600000  & 0 & 0 & 0  & 1   & 3   \\ \hline
600000  & 700000  & 0 & 0 & 0  & 0   & 3   \\ \hline
700000  & 800000  & 0 & 0 & 0  & 1   & 5   \\ \hline
800000  & 900000  & 0 & 0 & 0  & 2   & 7   \\ \hline
900000  & 1000000 & 0 & 0 & 0  & 3   & 6   \\ \hline
1000000 & 1100000 & 0 & 0 & 0  & 1   & 6   \\ \hline
1100000 & 1200000 & 0 & 0 & 0  & 1   & 24  \\ \hline
1200000 & 1300000 & 1 & 0 & 2  & 8   & 17  \\ \hline
1300000 & 1400000 & 0 & 0 & 2  & 8   & 36  \\ \hline
1400000 & 1500000 & 0 & 0 & 0  & 4   & 31  \\ \hline
1500000 & 1600000 & 0 & 0 & 0  & 8   & 40  \\ \hline
1600000 & 1700000 & 0 & 0 & 0  & 16  & 43  \\ \hline
1700000 & 1800000 & 0 & 1 & 3  & 7   & 45  \\ \hline
1800000 & 1900000 & 0 & 0 & 1  & 18  & 82  \\ \hline
1900000 & 2000000 & 0 & 0 & 1  & 21  & 84  \\ \hline
2000000 & 2100000 & 0 & 0 & 0  & 27  & 94  \\ \hline
2100000 & 2200000 & 0 & 0 & 4  & 27  & 98  \\ \hline
2200000 & 2300000 & 0 & 0 & 3  & 28  & 119 \\ \hline
2300000 & 2400000 & 0 & 0 & 3  & 31  & 146 \\ \hline
2400000 & 2500000 & 0 & 1 & 3  & 40  & 176 \\ \hline
2500000 & 2600000 & 0 & 2 & 4  & 42  & 158 \\ \hline
2600000 & 2700000 & 0 & 1 & 6  & 48  & 206 \\ \hline
2700000 & 2800000 & 0 & 0 & 6  & 56  & 217 \\ \hline
2800000 & 2900000 & 0 & 1 & 7  & 85  & 252 \\ \hline
2900000 & 3000000 & 0 & 1 & 5  & 74  & 285 \\ \hline
3000000 & 3100000 & 0 & 1 & 6  & 68  & 303 \\ \hline
3100000 & 3200000 & 1 & 1 & 2  & 95  & 356 \\ \hline
3200000 & 3300000 & 0 & 1 & 8  & 67  & 369 \\ \hline
3300000 & 3400000 & 0 & 0 & 9  & 108 & 347 \\ \hline
3400000 & 3500000 & 0 & 1 & 10 & 97  & 442 \\ \hline
3500000 & 3600000 & 0 & 1 & 9  & 112 & 509 \\ \hline
3600000 & 3700000 & 0 & 1 & 12 & 125 & 511 \\ \hline
3700000 & 3800000 & 0 & 0 & 17 & 130 & 518 \\ \hline
3800000 & 3900000 & 0 & 2 & 6  & 160 & 592 \\ \hline
3900000 & 4000000 & 0 & 2 & 12 & 145 & 575 \\ \hline
\end{tabular}

 Профиль  
                  
 
 Re: Антимагические квадраты
Сообщение03.04.2015, 06:42 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Progger
спасибо вам огромное, что не бросили задачу.

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

Изображение

При поиске это, конечно, надо учитывать. Я в своих давних экспериментах поступала так: сначала искала ассоциативные квадраты Стенли 7-го порядка; этот поиск выполняется довольно быстро даже по моей примитивной программе. Затем для тех центральных элементов, для которых квадраты 7-го порядка нашлись, уже искала ассоциативный квадрат 9-го порядка. Увы, мне далеко уйти не удалось.

Посмотрите на иллюстрацию. Все вложенные ассоциативные квадраты - порядков 3, 5, 7 - имеют ту же самую константу ассоциативности 2518246, потому что у них одинаковый центральный элемент.
Это всё просто и очевидно.
А вот самая большая матрёшка - ассоциативный квадрат 9-го порядка - уже не получилась, то есть она вполне себе хорошая, но не все числа в ней простые.

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

Осталось спросить третьего героя эпопеи: на чём он остановился? :wink:

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

Модераторы: Модераторы Математики, Супермодераторы



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

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


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

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