2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 3, 4, 5, 6, 7, 8, 9 ... 215  След.
 
 Re: Пентадекатлон мечты
Сообщение21.02.2022, 16:23 
Аватара пользователя


29/04/13
8136
Богородский
VAL в сообщении #1549301 писал(а):
Меня, например, смущает округление в задаче, где все изначально целочисленно.

А я, напротив, считаю что для некоторых диапазонов это весьма удачный приём. Ни одного подходящего простого пока пропущено не было.

VAL в сообщении #1549301 писал(а):
Вот для 8 паттернов с 98 на 11-м месте (это maple, а не PARI):

Пощадите :-). Я тока-тока с PARI чуток освоился, а тут новая напасть — Maple.

VAL в сообщении #1549301 писал(а):
Действительно для 28 подходящих случаев больше (814 против примерно 700).

814 на 4-м месте я прекрасно вижу, а вот где эти примерно 700 на 11-м месте? Или это усреднённое значение?

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение21.02.2022, 16:42 
Заслуженный участник


20/08/14
11781
Россия, Москва
VAL в сообщении #1549305 писал(а):
Насколько реально внести такие изменения?
Реально все.
Про 11 чисел уже и так встал вопрос, если Вы голосуете за 11 вместо 14, то ОК, мне тоже так кажется боле логичным. Вот вариант exe с проверкой лишь 11 чисел (в облаке пока оставлю старый): https://dropmefiles.com/vryWw
Количество мелких простых увеличить — в ближайших планах. 65536 конечно перебор (таблицы в программе станут десятки мегабайт, но проблема не в их размере, а в превышении размера кэша L3), но что-то разумное хочу сделать. На мой взгляд достаточно отфильтровать так чтобы проверка в PARI занимала менее 10% общего времени (вместо 70% как сейчас).
Размер чисел $k$ на входе тоже нетрудно, но непонятно надо ли: $2^{64}\cdot 4.4\cdot10^{26}\approx 8\cdot10^{45}$, это более семи тысяч лет счёта в один поток.
Плюс в планах проверить скорость фильтрации по делимости индекса первой проверкой.

PS. Проверил на PARI достижимое качество фильтрации при разных пределах на малые делители для миллиона чисел где-то около $10^{14}$:
$2^8: 5154$
$2^9: 1353$
$2^{10}: 439$
$2^{11}: 166$
$2^{12}: 57$
$2^{13}: 34$
$2^{14}: 14$
ИМХО достаточно из миллиона чисел оставить PARI проверить 57 вместо сегодняшних 5154, позволит уложиться в пару мегабайт таблиц. Впрочем посмотрим.

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


27/06/08
4062
Волгоград
Yadryara в сообщении #1549308 писал(а):
Пощадите :-). Я тока-тока с PARI чуток освоился, а тут новая напасть — Maple.
Как говорится, "взялся за гуж...".
Впрочем, можете и не проверять, а поверить :-)
Yadryara в сообщении #1549308 писал(а):
814 на 4-м месте я прекрасно вижу, а вот где эти примерно 700 на 11-м месте? Или это усреднённое значение?
Усредненное. Но 98 неожиданно оказалось не на 11-м, а на 14 месте :shock: :oops:

Сейчас либо найду, либо пересчитаю для случая, когда 98 на 11-м.

Стоп!
98 и не может быть на 11-м месте. На 11-м месте может быть 49. Как раз когда 28 на 4-м.

Так что с чем сравниваем?

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


29/04/13
8136
Богородский
VAL в сообщении #1549317 писал(а):
98 и не может быть на 11-м месте.

Вот именно. Но не я начал эту путаницу:

VAL в сообщении #1549301 писал(а):
Вот для 8 паттернов с 98 на 11-м месте


Да, 98 может быть только на 2-м, либо на 14-м месте. Вот берём паттерн с любым из этих расположений, смотрим его статистику и сравниваем с 814 для 28. На том же диапазоне проверяемых чисел.

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

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение21.02.2022, 18:54 
Заслуженный участник


20/08/14
11781
Россия, Москва
Yadryara в сообщении #1549292 писал(а):
Вы внимательно читали лемму 6 в той самой статье 2018 года?
Процитирую главный вывод из той леммы:
Цитата:
Let n25, n26, . . . , n15 (where ni is congruent to i modulo 32) are the numbers of such run.
...
Thus n0 and n8 cannot at the same time belong to a required run
ОК, n0 и n8 одновременно быть не могут, не вопрос, это понятно. Но нигде тут не сказано что недопустим вариант n1,...,n15. Либо я в упор не вижу где.

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение21.02.2022, 19:12 
Аватара пользователя


29/04/13
8136
Богородский
Ну вот моя добавка-то:

Yadryara в сообщении #1549292 писал(а):
Нельзя чтобы хоть какое-то число 15-шки делилось ровно на $8$ или, тем более, ровно на $16$. А на числовой оси такие места есть только вблизи чисел кратных $32$. Вот и получается, что наши планеты удалены не дальше чем на 7 единиц от центральной звезды. Они равны $32p\pm7$.

Или Вы не согласны, что нельзя допустить, чтобы хоть какое-то число 15-шки делилось ровно на $8$ или, тем более, ровно на $16$ ?

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение21.02.2022, 20:34 
Заслуженный участник


20/08/14
11781
Россия, Москва
Иначе говоря, $4pq=0\pmod8$ в позиции $n+7$ неразрешимо при любых нечётных $p,q$? ОК, это я понимаю, значит $32p$ действительно обязательна.

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение21.02.2022, 21:48 
Заслуженный участник


27/06/08
4062
Волгоград
Dmitriy40 в сообщении #1549324 писал(а):
Но нигде тут не сказано что недопустим вариант n1,...,n15.
Совершенно верно.
Yadryara в сообщении #1549326 писал(а):
Или Вы не согласны, что нельзя допустить, чтобы хоть какое-то число 15-шки делилось ровно на $8$ или, тем более, ровно на $16$ ?
На 16, ни одно из искомых чисел, конечно, делиться не может. Иначе число делителей было бы кратно 5.
Но делиться на 8 среднему числу искомого набора никто не запрещает (в том числе и лемма 6).
Например, среди пятнашек, где среднее число равно $8(301522186930606735689318659+82601031698135096600604150k)^2$, практически наверняка найдется искомая.
Вот только числа здесь гораздо больше, чем в пятнашках, где посередине $32p$.

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение21.02.2022, 22:56 
Заслуженный участник


20/08/14
11781
Россия, Москва
Выше говорилось про оптимальность шага (модуля), но я вот обнаружил два интересных зеркальных паттерна:
Используется синтаксис Text
n+0     n+1     n+2     n+3     n+4     n+5     n+6     n+7     n+8     n+9     n+10    n+11    n+12    n+13    n+14
45p     2pq^2   13pq^2  12p     7pq^2   50p     3pq^2   32p     11pq^2  18p     5pq^2   28p     3pq^2   2pq^2
        2pq^2   3pq^2   28p     5pq^2   18p     11pq^2  32p     3pq^2   50p     7pq^2   12p     13pq^2  2pq^2   45p
В которые можно подставить 9 произвольных простых в квадрате на места $q^2$ и свободное и получить прямые условия на 14 чисел из 15-ти. При подстановке простых $19,47,41,29,43,37,31,23,17$ в указанном порядке в первый паттерн шаг (модуль) получится порядка $6\cdot3\cdot10^{33}$. Полезнее ли это пока без понятия. Моя программа работает на 30% медленнее (10с вместо 7с), но фильтрует почти вдвое лучше (2700 вместо 4700 на миллион).

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение21.02.2022, 23:06 
Заслуженный участник


27/06/08
4062
Волгоград
Dmitriy40 в сообщении #1549336 писал(а):
Выше говорилось про оптимальность шага (модуля), но я вот обнаружил два интересных зеркальных паттерна:
Используется синтаксис Text
n+0     n+1     n+2     n+3     n+4     n+5     n+6     n+7     n+8     n+9     n+10    n+11    n+12    n+13    n+14
45p     2pq^2   13pq^2  12p     7pq^2   50p     3pq^2   32p     11pq^2  18p     5pq^2   28p     3pq^2   2pq^2
        2pq^2   3pq^2   28p     5pq^2   18p     11pq^2  32p     3pq^2   50p     7pq^2   12p     13pq^2  2pq^2   45p
В которые можно подставить 9 произвольных простых в квадрате на места $q^2$ и свободное и получить прямые условия на 14 чисел из 15-ти. При подстановке простых $19,47,41,29,43,37,31,23,17$ в указанном порядке в первый паттерн шаг (модуль) получится порядка $6\cdot3\cdot10^{33}$. Полезнее ли это пока без понятия.
В этом варианте нужна простота 14 чисел. Паттерны, в которых нужна простота 11 чисел, перспективнее. Конечно, проверка на простоту быстрее, но вероятность, что число из интересующего нас диапазона окажется произведением двух простых в 4 с лишним раза выше.
Цитата:
Моя программа работает на 30% медленнее (10с вместо 7с), но фильтрует почти вдвое лучше (2700 вместо 4700 на миллион).
Хорошо бы 1 на миллион :-)

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


29/04/13
8136
Богородский
VAL в сообщении #1549333 писал(а):
На 16, ни одно из искомых чисел, конечно, делиться не может. Иначе число делителей было бы кратно 5.

Примерно на это и намекал, говоря "тем более". Если мы хотим получить 12 делителей, то 4-я степень простого нам никак не годится, а могут пригодится только степени 1, 2, 3, 5, 11.

VAL в сообщении #1549333 писал(а):
Но делиться на 8 среднему числу искомого набора никто не запрещает (в том числе и лемма 6).

Важное уточнение: лучше говорить "ровно на 8". Значит я эту лемму слишком широко трактовал.

VAL в сообщении #1548034 писал(а):
За исключением среднего числа в цепочке, которое кратно 32 (это необходимое условие).

Надо было, видимо, уточнить, что это условие необходимо именно для указанного диапазона.

Молодец, Dmitriy40, проявил ту самую дотошность.

Dmitriy40 в сообщении #1549246 писал(а):
Спасибо за дотошность.

И Вам спасибо.

Yadryara в сообщении #1548971 писал(а):
наработки по задаче с разных сторон и под увеличительным стеклом

Я специально написал про лупу. Потому что надо бы не под лупой, а под микроскопом рассматривать многие вещи, но это затруднительно.

VAL в сообщении #1549317 писал(а):
Впрочем, можете и не проверять, а поверить :-)

То то и оно, что нельзя нам здесь верить друг другу, а надо проверять, да ещё как тщательно. В интересах дела.

Ну так что насчёт эпической битвы 28 против 98 ?

Да, вот у меня ошибка. К счастью, не в самом паттерне, а в его описании:
Yadryara в сообщении #1549263 писал(а):
3-й этап. Ещё две: $2^2\cdot7$ и $7^2\cdot2$

Не надо умножать на 2 в конце: $2^2\cdot7$ и $7^2$

Dmitriy40, а можно Вас попросить как-то по-другому изображать паттерны? Ну не помещаются они по ширине страницы даже в мелком масштабе! Необязательно как у меня, но чтоб покомпактней.

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение22.02.2022, 11:29 
Аватара пользователя


29/04/13
8136
Богородский
Пока единственное ядро моего компа считает, попытаюсь написать обобщающий пост.

Во-первых, уточнение. Предлагаю считать самой перспективной концепцией КМК37-11.

Почему я удлиняю название и уточняю насчёт 11-ти:

VAL в сообщении #1548506 писал(а):
При этом в наборах нет третьего числа, кратного 7, и вторых чисел, кратных 11 и 13 (последние теоретически могли бы присутствовать, но их допущение резко снижает эмпирическую вероятность успеха, поскольку в интересующем нас диапазоне произведения двух простых встречаются гораздо чаще, чем простые).

Ну так вот, я проговорю явно то, что может быть не замечено, как уже было. Если хоть одно из вторых чисел кратных 11 и/или 13 попадёт в паттерн, то огромных простых будет уже 12, а то и больше.

А для нас и 11 огромных простых это очень много. Пока продолжаю считать, что меньшее количество невозможно.

Жду момента, когда уважаемый Dmitriy40, тщательно проверит все другие пути и вернётся к КМК37-11.

Также 12 дней жду ответа на этот важный вопрос:

Yadryara в сообщении #1548505 писал(а):
VAL в сообщении #1203960 писал(а):
координировать действия нескольких участников

Вот я как раз и хочу подробно разобраться, какие варианты уже проверены и какие результаты достигнуты.

Например, спрошу проверялся ли ранее тот самый паттерн, для которого Dmitriy40 делал программу:

Код:
45p 722p 841qr 12p 49qr   50p 507p 32p 961qr 18p   605p 28p 867p 1058p 1369qr


VAL в сообщении #1548506 писал(а):
С учетом указанных ограничений возникает несколько десятков тысяч идентичных начальных условий для программы поиска.

"Идентичные начальные условия для программы поиска" мы уже вовсю называем паттернами.

А Вы пытались рассчитать точное количество этих паттернов в рамках КМК37-11? Не о сотнях ли тысяч надо в таком случае говорить?

Я вот пытался ограничить количество самых приоритетных паттернов до $2880$, используя новые ограничения:

На 3-м этапе брать только 28, но не 98.

На 4-м этапе брать только 605, но не 845, 1445, ..., 6845 .

Дальше есть ещё ограничения. Но обоснованность их всех пока сомнительна, да.

Тем временем комп проверил диапазон 0-500 миллиардов. И счёт в противостоянии $605$ и $2645$ получился $31 : 9$. На этот раз тоже преимущество меньшего числа над большим. Но не в 8, а в 3 раза. Хотя числа, конечно, пока маловаты.

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


27/06/08
4062
Волгоград
VAL в сообщении #1549333 писал(а):
Например, среди пятнашек, где среднее число равно $8(301522186930606735689318659+82601031698135096600604150k)^2$, практически наверняка найдется искомая.

Таки не найдется!
Среднее число в пятнашке имеет вид $8p^2$. Тогда 6-е число $2(4p^2-1)=2(2p-1)(2p+1)$, где $2p-1$ кратно 9 и больше 9. Поэтому у 6-го числа не менне 24 делителей.

Так что условие "среднее число в пятнашке имеет вид $32p$", по-видимому, все же, необходимо.

-- 22 фев 2022, 18:10 --

Yadryara в сообщении #1549357 писал(а):
Я вот пытался ограничить количество самых приоритетных паттернов до $2880$, используя новые ограничения:
У меня получилось $2\cdot (12+20) \cdot 720=46080$ вариантов. Впрочем, считал наспех. Но порядок числа, видимо, такой.

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение22.02.2022, 19:48 
Аватара пользователя


29/04/13
8136
Богородский
Ещё одно непонимание попробую ликвидировать.

Dmitriy40 в сообщении #1549183 писал(а):
Насколько я понял у VAL и так используются все возможные варианты размещения чисел, именно поэтому более двух тысяч программ.

Вот именно, что далеко не все:

VAL в сообщении #1548506 писал(а):
С учетом указанных ограничений возникает несколько десятков тысяч идентичных начальных условий для программы поиска. У меня автоматически сгенерированы порядка 2000 таких программ.
VAL в сообщении #1549386 писал(а):
У меня получилось $2\cdot (12+20) \cdot 720=46080$ вариантов.

Так вот, я по-прежнему сильно подозреваю что нет никаких десятков тысяч идентичных начальных условий.

И всем же ведь будет лучше, если я окажусь прав. Если одни варианты действительно имеют приоритет над другими, перебор сократится в $\dfrac{46080}{2880}=16$ раз. Это предварительно, я думаю, что исходно более 46 тысяч имеется. Прошу более подробный расчёт. Думаю по 7 этапам удобно будет рассчитать.

Моя идея, которая пока подтверждается, заключается в том, что паттерн надо конструировать из самых маленьких множителей.

Правда, подтверждается она только мной, но и не опровергается пока никем, ибо:

VAL в сообщении #1549301 писал(а):
814 против примерно 700

Это оказалось неверным.

VAL в сообщении #1549266 писал(а):
Так, флуктуации в пределах статистической погрешности (780 против 694 на 10 000 )

А это пока не подтверждено ничем.

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение22.02.2022, 20:07 
Заслуженный участник


27/06/08
4062
Волгоград
Yadryara в сообщении #1549393 писал(а):
Правда, подтверждается она только мной, но и не опровергается пока никем, ибо:

VAL в сообщении #1549301

писал(а):
814 против примерно 700
Это оказалось неверным.
Неверным оказалось лишь то, что я по неаккуратности приписал 98 11-ю позицию. На самом деле в рассматриваемом паттерне 98 стояло в 14-й. А частотность вполне себе верная.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 3218 ]  На страницу Пред.  1 ... 3, 4, 5, 6, 7, 8, 9 ... 215  След.

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



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

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


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

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