2014 dxdy logo

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

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




На страницу Пред.  1 ... 248, 249, 250, 251, 252  След.
 
 Re: Пентадекатлон мечты
Сообщение19.10.2025, 16:47 
EUgeneUS в сообщении #1706379 писал(а):
Паттерн "0-2-16-3(9)" ещё не считал, а для паттерна "0-4-14-3(8)":
Для $N = 1,0 \cdot 10^{50}$, вероятность найти цепочку за одну проверку $8,1 \cdot 10^{-13}$
На два порядка у Вас ошибка. Вы не учитываете, что ищем числа не в $x$, а в $x/v_i$, где $v_i$ - множитель, заданный паттерном. Но в целом мой "калькулятор шансов" так и работает: для каждой позиции цепочки вероятность считается как
$P_i = b_{n_i} P_{n_i}(N/v_i)$, где
$P_{n_i}(N)$ - асимптотики для того количества множителей ($n_i$), которое задано паттерном для i-го места.
(Которые взял из одного из первых Ваших сообщений в этой теме. За что Вам большое спасибо).
$b_{n_i}$ - множитель, указывающий во сколько раз вероятность больше асимптотики из-за "решета Эратосфена", которое опять же задаётся паттерном (набором простых, которые в нём используются).
Совершенно верно! Асимптотические оценки работают при $x \to \infty$, но для конкретного $x = 10^{50}$ существуют поправочные множители. Вероятность того, что случайное число имеет структуру "pqrs" (4 простых множителя) примерно пропорциональна:
$P_{\text{pqrs}} \sim \frac{(\log\log x)^3}{\log x}$
в то время как для "pqr":
$P_{\text{pqr}} \sim \frac{(\log\log x)^2}{\log x}$
Для $x = 10^{50}$, $\log\log x \approx 4.746$, разница составляет примерно $4.746$ раза, что может не компенсировать другие факторы.
Общее ожидаемое количество цепочек:
$N \sim \frac{x}{L} \times P_{\text{candidate}}$
Для паттерна "0-4-14-3(8)" с L в 129 раз меньше, количество кандидатов в 129 раз больше. Даже если $P_{\text{candidate}}$ у него немного хуже, он может оказаться эффективнее.
EUgeneUS в сообщении #1706379 писал(а):
vicvolf в сообщении #1706371 писал(а):
Паттерн "0-2-16-3(9)" представляет собой оптимальный компромисс между вероятностью успеха и вычислительной сложностью, что делает поиск цепочек D(48,21) возможным .
Это опрометчивый вывод, и скорее всего неверный.
Во-1х. Асимптотика для $pqrs$ лучше, чем для $pqr$, однако, для интересующих порядков чисел, вероятность попасть в $pqr$ больше, чем в $pqrs$.
Во-2-х. Для поиска оптимального паттерна нужно их сравнивать друг с другом.
Вот, например, "0-2-16-3(9)" и "0-4-14-3(8)" у первого асимптотика немного получше, но у второго множитель при итераторе (lcm) в $59^2/3^3 \approx 129$ раз меньше. И какой будет лучше? Вопрос.
В-3-х. Количество цепочек, которые нужно проверить, не равно "вычислительная мощность".
Проверки на простоту выполняются во много-много раз быстрее, чем факторизация. И цепочки проверяются не путем проверки всех чисел, а только до первой неудачи в какой-нибудь позиции.
Пока всё указывает, что для реализации на PARI\GP более оптимальным будет паттерн с одним простым неизвестным.
Это критически важное уточнение! На практике:
- Проверка простоты (для позиций "p") — очень быстрая
- Факторизация (для "pq", "pqr", "pqrs") — значительно медленнее
- Ранний выход — при первой неудаче проверка цепочки прерывается
Поэтому паттерны с большим количеством позиций, требующих факторизации, могут быть менее эффективными, даже если их теоретическая вероятность выше.

 
 
 
 Re: Пентадекатлон мечты
Сообщение19.10.2025, 16:53 
Аватара пользователя
vicvolf в сообщении #1706412 писал(а):
Для паттерна "0-4-14-3(8)" с L в 129 раз меньше, количество кандидатов в 129 раз больше. Даже если $P_{\text{candidate}}$ у него немного хуже, он может оказаться эффективнее.


Это так, и этот вопрос изучался (вот только что получены результы).

 
 
 
 Re: Пентадекатлон мечты
Сообщение19.10.2025, 16:56 
EUgeneUS в сообщении #1706410 писал(а):
Результаты калькулятора шансов на "серебряном наборе паттернов"
Скажите, а почему pats везде одинаковое 9! ?

-- 19.10.2025, 17:10 --

EUgeneUS
Генератор закончил работу.
Улучшений от выложенных результатов нет.
Не были показаны:
v=[ 4, 23085, 182, 289, 24, 1, 110, 3, 4, 49, 18, 25, 32, 3, 2, 169, 420, 121, 2, 9, 49096];\\6-0-6-9(8)
v=[ 14440, 153, 2, 1, 12, 5, 154, 507, 32, 1, 2430, 1, 4, 147, 2, 25, 24, 121, 578, 171, 1820];\\5-0-10-6(8)
v=[ 14440, 153, 2, 11, 12, 245, 338, 3, 32, 1, 2430, 1, 28, 3, 242, 25, 24, 1, 578, 15561, 20];\\4-0-13-4(8)

 
 
 
 Re: Пентадекатлон мечты
Сообщение19.10.2025, 17:28 
Аватара пользователя
Dmitriy40 в сообщении #1706414 писал(а):
Скажите, а почему pats везде одинаковое 9! ?


Я специально одинаковое брал, чтобы сравнивать паттерны на одинаковом количестве "размножения".
Для (8) потом дополнил 8!

Dmitriy40 в сообщении #1706414 писал(а):
Не были показаны:


Я их сохраню. Но, думаю, для программы на PARI/GP они точно не пригодятся.

-- 19.10.2025, 18:13 --

Вот "золотой паттерн" - 1-1-16-3(8)

результаты пробных запусков:

(Оффтоп)

Код:
"Pat";"pats";"i_m/pat";"i_m all";"n_all";"N";"P(1)";"P(win)";"Часов на 1е47";"Часов всего";"Лет"
"0-3-16-2(8)";40320;85830000;3460665600000;1411951564800;118138216085270000000000000000000000000000000000000;2,12210396061124E-012;0,9500287784;41,5;49027,3596753872;5,5967305566
"1-1-16-3(8)";40320;293200000;11821824000000;4823304192000;403566641411277000000000000000000000000000000000000;6,21156351546482E-013;0,9500146859;8,1;32688,8979543134;3,7316093555
"2-0-16-3(8)";40320;1068000000;43061760000000;17569198080000;1470017641761330000000000000000000000000000000000000;1,70594940386275E-013;0,9500741462;6,3;92611,1114309635;10,5720446839


3.73 года в один поток. 1.2 месяца в 40 потоков.
На данный момент, в паттерне с нулем простых нашлось уже 4 кандидата, а паттернах с 1 и 2 простыми - ниодного.
Может статистический выброс. А может накосячил, когда программы настраивал.
В любом случае, результаты пробных запусков нужно перепроверить.

Что интересно, вчерашние паттерны были хуже только на одну позицию в $pqr$, а показывали время в разы больше. Для одного простого в 1.5 - 2 раза.
Пробные запуски поводились для 8! паттернов. Путем "размножения паттернов" можно ещё выжать десятки процентов. До двух раз, при увеличении количества паттернов на 3 порядка, наверное.

 
 
 
 Re: Пентадекатлон мечты
Сообщение19.10.2025, 18:32 
Важно не только сколько кандидатов, но и насколько они хороши: 100500 valids=10 хуже 20 valids=20.

У меня по запускавшимся вариантам состояние такое (сколько простых, каких valids>16 сколько цепочек):
p0: 17х1шт, счёт 18ч
p0-8!: 18х1шт, счёт 45ч
p3: 18х2шт, 17х12шт, счёт 88ч
p5: 18х1шт, 17х2шт, счёт 67ч
Варианты p0 считались без ускорителей, на PARI. Варианты p3 и p5 - с 9 квадратами.
В общем, если не брать кучу 17-ек от p3, то все примерно одинаково (в пределах случайных выбросов).

EUgeneUS в сообщении #1706415 писал(а):
Вот "золотой паттерн" - 1-1-16-3(8)
С ним (и вторым таким же) проблема: нет разрешённых остатков по модулю 7. И тупая замена $7^2 \to 7^5$ проблему не решает. Потому что проблема на месте 480p, p почему-то получается кратным 7.

 
 
 
 Re: Пентадекатлон мечты
Сообщение19.10.2025, 18:40 
Аватара пользователя
Вот влияние количества паттернов для 1-1-16-3(8)

(Оффтоп)

Код:
"Pat","pats","i_m/pat","i_m all","n_all","N","P(1)","P(win)"
"1-1-16-3(8)",40320,293200000,11821824000000,4823304192000,403566641411277000000000000000000000000000000000000,"6,21156351546482E-013","0,9500146859"
"1-1-16-3(8)",100000,105750000,10575000000000,4314600000000,145556522650801000000000000000000000000000000000000,"6,94520294686685E-013","0,9500422316"
"1-1-16-3(8)",362880,24840000,9013939200000,3677687193600,34190298543518400000000000000000000000000000000000,"8,15105975022678E-013","0,9500985294"
"1-1-16-3(8)",1000000,7930000,7930000000000,3235440000000,10915019225088700000000000000000000000000000000000,"9,25912880038621E-013","0,9500001648"
"1-1-16-3(8)",4000000,1663000,6652000000000,2714016000000,2288988740842770000000000000000000000000000000000,"1,10435110693443E-012","0,9500746592"
"1-1-16-3(8)",10000000,591000,5910000000000,2411280000000,813465415629482000000000000000000000000000000000,"1,2425773603185E-012","0,9500234777"


Смотреть нужно на "i_m all" - это общее количество итераций. При увеличение паттернов с $8!$ до $10^7$ в два раза и падает. Плюс плюшки за счёт хорошего снижения $N$ - факторизация облегчается.

-- 19.10.2025, 18:44 --

По проверке времени расчета.
Расчет для оценки времени нужно запускать
а) на одинаковом количестве паттернов для каждого типа паттернов, так сравнивать удобно. Я проверял на $8!$.
б) на диапазоне $N$ - как посчитано для данного типа паттерна и для данного количества паттернов. Я прямо $N$ из калькулятора и подставлял, как начальное значение.

-- 19.10.2025, 18:46 --

Dmitriy40 в сообщении #1706423 писал(а):
С ним (и вторым таким же) проблема: нет разрешённых остатков по модулю 7. И тупая замена $7^2 \to 7^5$ проблему не решает.

Беда....
И двумя простыми 2-0-16-3(8), похоже, что-то подобное.

-- 19.10.2025, 18:48 --

Жаль, конечно, если с 16 $pqr$ не найдутся.
Вчерашние 2-1-14-4(8) и 1-2-15-3(8) заметно худшее время показывали, раза в 1.5-2.

-- 19.10.2025, 18:56 --

Если 1-x-16-y(8) не найдутся, то, вероятно, "золотым паттерном" будет 1-2-15-3(8). Но его нужно ещё с 1-1-16-3(9) сравнить, тот может и получше оказаться.

Если 2-x-16-y(8) не найдутся, то, хорошо бы для сравнения 2-х-15-y(8).

 
 
 
 Re: Пентадекатлон мечты
Сообщение19.10.2025, 19:33 
EUgeneUS в сообщении #1706413 писал(а):
vicvolf в сообщении #1706412 писал(а):
Для паттерна "0-4-14-3(8)" с L в 129 раз меньше, количество кандидатов в 129 раз больше. Даже если $P_{\text{candidate}}$ у него немного хуже, он может оказаться эффективнее.

Это так, и этот вопрос изучался (вот только что получены результы).
Мой первоначальный вывод действительно был слишком упрощённым и оптимистичным.

Пересмотренный анализ оптимальности паттернов

Факторы, которые я недооценил:

1. Баланс между L и P_candidate
- Меньший L даёт больше кандидатов: $ N \sim x/L \times P_{\text{candidate}} $
- Для "0-4-14-3(8)" с L в 129 раз меньше, это компенсирует худшую асимптотику

2. Практическая скорость проверки
- Проверки на простоту (для "p") vs факторизация (для "pq", "pqr", "pqrs")
- Ранний выход при первой неудаче
- Для PARI/GP паттерны с одним "p" могут быть оптимальнее

3. Конечные значения x vs асимптотика
- Для $ x = 10^{50} $ асимптотические оценки могут не отражать реальное положение
- Вероятности для разных структур ("pqr" vs "pqrs") сравнимы по порядку величины

Новые данные и их значение

Эмпирическое сравнение паттернов — единственный способ определить действительно оптимальную стратегию.

Что показывают практические исследования:
- Сравнительный анализ паттернов необходим для определения лучшего
- Теоретическая асимптотика — лишь один из факторов
- Эмпирические замеры скорости проверки критически важны

Исправленный вывод
На основании ваших замечаний и новых данных:

1. Паттерн "0-2-16-3(9)" не является однозначно оптимальным — он представляет лишь один из возможных компромиссов

2. Для практической реализации в PARI/GP более перспективны:
- Паттерны с меньшим L (даже в ущерб асимптотике)
- Паттерны с минимальным количеством позиций, требующих факторизации
- Паттерны, позволяющие эффективный ранний выход

3. Окончательный выбор оптимального паттерна требует:
- Эмпирического сравнения нескольких кандидатов
- Учёта конкретных характеристик вычислительной системы
- Анализа реальной скорости проверки, а не только теоретической вероятности

 
 
 
 Re: Пентадекатлон мечты
Сообщение19.10.2025, 20:25 
Аватара пользователя
Сейчас такие лидеры гонки (в порядке призовых мест):
0-3-16-2(8)
1-2-1-3(8)
1-1-16-3(9)

Оценка времени на пробных запусках:

(Оффтоп)

Код:
Pat   pats   i_m/pat   i_m all   n_all   N   P(1)   P(win)   Часов на 1е47   Часов всего   Лет
0-3-16-2(8)   40320   85830000   3460665600000   1411951564800   118138216085270000000000000000000000000000000000000   2,12210396061124E-012   0,9500287784   41,5   49027,3596753872   5,5967305566
1-2-15-3(8)   40320   419000000   16894080000000   6892784640000   576720404761865000000000000000000000000000000000000   4,34760768324158E-013   0,9500489796   11,5   66322,8465476145   7,5711012041
1-1-16-3(9)   362880   28140000   10211443200000   4166268825600   4993621928836050000000000000000000000000000000000000   7,19217581815023E-013   0,9500360628   1,5   74904,3289325407   8,5507224809


Если округлить $5,5967305566$ до 6 лет. То получается на 40 потоков 1.8 месяца.
В принципе подъёмно. И это оценка на моём медленном компе.

 
 
 
 Re: Пентадекатлон мечты
Сообщение20.10.2025, 06:04 
Аватара пользователя
Dmitriy40 в сообщении #1706389 писал(а):
Ну вот в Ваших же словах они не стоят друг над другом и потому непонятно с какой стороны дырка.

Потому что это не колышет. Словосочетание "дырявая 17-ка" употреблено в том смысле, что между какими-то из 17-ти единичек имеется хотя бы один промежуток.

Так получилось что у меня тоже считается комплект паттернов 0-6-8-7-8!, который считает Дмитрий. Я запускал его для тестов и, похоже, накосячил. И перебор пошёл по-другому. Пока не остановил счёт по нему. Он считает до некруглой высоты 2.29e47. Результаты:

Код:
Valids    8   9   10   11   12   13   14   15      Sum
Found     1   3    5    6    7    3    5    1       32

Средневзвешенный valids пока низок:

Код:
(04:57) gp > mass_center(v)=[1..#v]*v~/vecsum(v)
% = (v)->[1..#v]*v~/vecsum(v)

(04:58) gp > mass_center([0,0,0,0,0, 0,0, 1,3,5,6,7,3,5,1, 0,0,0,0,0, 0])+.

% = 11.580645161290322580645161290322580645

Напомню, что ранее удалось получить значение 12.18, причём для тысячи приближений.

Да, в данном случае 11.58 пока всего лишь по 32-м приближениям.

Возможно, Дмитрий собрал гораздо больше статистики.

Может сложиться, что и здесь парабола будет в виде кастрюли.

 
 
 
 Re: Пентадекатлон мечты
Сообщение20.10.2025, 06:55 
Аватара пользователя
Yadryara в сообщении #1706457 писал(а):
Так получилось что у меня тоже считается комплект паттернов 0-6-8-7-8!, который считает Дмитрий.

Дмитрий нашел паттерн с нулём простых лучше: 0-3-16-2(8).
Он у меня считается до 1E47. Должен считаться около 2-х суток.
Запустил вечером, но ночью моргнул свет и все пропало.
Если ещё раз моргнет - брошу этот расчет до появления программы с возможностью перезапуска с прерванного места (наверное по последней зафиксированной перестановке нужно возобновлять).

Для вероятности 0.95 в паттерне 0-3-16-2(8) на 8! перестановок нужно считать до 1.1814Е50.
1E47 - это примерно 8.45 десятитысячных от необходимого, соответственно.

Yadryara в сообщении #1706457 писал(а):
Средневзвешенный valids пока низок:

А он и будет низок. Эффективность паттерна будет выражаться не столько в сдвиге гистограммы вправо (если это вообще возможно), а в "скорости" её наполнения.

-- 20.10.2025, 07:25 --

Yadryara в сообщении #1706457 писал(а):
Может сложиться, что и здесь парабола будет в виде кастрюли.


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

 
 
 
 Re: Пентадекатлон мечты
Сообщение20.10.2025, 08:10 
Аватара пользователя
То есть практические итоги пока явно не в пользу паттерна без одиночных простых. Сравниваем:

Код:
              3-0-13-5-9!        0-6-8-7-8!
Приб/час              6.0               2.8
Valids               12.0              11.6

Казалось бы, какие вопросы: и приближений в два раза меньше находится и качество этих приближений пониже. Конечно, попробую ещё посмотреть "золотой паттерн".

Может начать проверку на асме с конца? То есть проверить места, где ожидаются pqrs.

Пусть $p$ — наименьше из них. Чтобы такая конструкция собралась, надо чтобы значение $p$ не превышало корень 16-той степени из $n$. Правильно понимаю?

Для $n=10^{50}$ это где-то 1333. Более редкие расклады для 16-ти делителей тоже вроде не сильно долго проверять.

 
 
 
 Re: Пентадекатлон мечты
Сообщение20.10.2025, 08:37 
Аватара пользователя
Yadryara в сообщении #1706461 писал(а):
То есть практические итоги пока явно не в пользу паттерна без одиночных простых. Сравниваем:


А вот так - паттерны с разным количеством простых - сравнивать нельзя.
Там распределения будут сильно разные.
Вы и сами это можете посмотреть на собранной статистике.
Для паттернов с одинаковым количеством простых, но с разным $pqr$ распределения, вообше говоря, тоже будут различаться. Но не так сильно.
Еще, если скорость роста гистограммы смотреть на паттернах с одинаковым количеством простых, но разным lcm, вопрос в каких числах, по порядку величины, нужно сравнивать?

 
 
 
 Re: Пентадекатлон мечты
Сообщение20.10.2025, 09:32 
Аватара пользователя
EUgeneUS
Парабола конечно в кавычках. «Можно ли прогнозировать правую ветвь "параболы" по левой»

EUgeneUS в сообщении #1706458 писал(а):
Если ещё раз моргнет - брошу этот расчет до появления программы с возможностью перезапуска с прерванного места (наверное по последней зафиксированной перестановке нужно возобновлять).

Ну так Дмитрий выше специально рассказывал, как для перезапуска с прерванного места использовать forperm.

 
 
 
 Re: Пентадекатлон мечты
Сообщение20.10.2025, 09:34 
Аватара пользователя
Yadryara
Я Вам расскажу, как на этой статистике можно делать оценки.

1. Считаем, что распределение кандидатов описывается биномиальным распределением $B(21-p_n,P)$, где
$p_n$ - количество неизвестных простых в паттерне
$P$ - параметр биномиального распределения, пока неизвестный.

2. Собираем статистику на несколько сотен кандидатов для конкретного паттерна.
Сдвигаем гистограмму на $p_n$ позиций влево (простые имеются в кандидатах достоверно).

3. По этой выборке оцениваем параметр биномиального распределения $P$.

4. Зная $P$, рассчитываем вероятность попадания в последний "бин". В зависимости от числа простых его номер будет $k=21 - p_n$.
$P_{\text{WIN}}= P^{21-p_n}$
Получили оценку вероятности найти 21 в расчете на количество кандидатов.

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

 
 
 
 Re: Пентадекатлон мечты
Сообщение20.10.2025, 11:00 
Аватара пользователя
EUgeneUS, да, вроде 0-3-16-2-8! это хороший комплект. За 80 минут в одном потоке нашлось 10 приближений. Запустил пока в 4 потока.

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

 
 
 [ Сообщений: 3779 ]  На страницу Пред.  1 ... 248, 249, 250, 251, 252  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group