2014 dxdy logo

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

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




На страницу Пред.  1 ... 244, 245, 246, 247, 248, 249  След.
 
 Re: Пентадекатлон мечты
Сообщение16.10.2025, 19:19 
Аватара пользователя
Yadryara в сообщении #1706095 писал(а):
будет совершенно легальный паттерн? Тогда нет проблем.

Не, ну не так просто оказалось переделать. Но получилось, теперь работает и у меня, и у Демиса.

Посмотрю ещё какие бывают паттерны. А то работы не хватает. Всего 4-5 потоков работают. Чисто интуитивно, выше 1e50 пока не хочется лезть.

 
 
 
 Re: Пентадекатлон мечты
Сообщение16.10.2025, 19:23 
Аватара пользователя
Dmitriy40 в сообщении #1706129 писал(а):
Только поиск такого паттерна будет супермедленным - нет быстрых isprime, придётся сразу запускать медленные factor. Но как концептуальная возможность ...


Если будет хуже (по оценки времени; оценки докуда считать и количество итераций - будет лучше), чем с тремя простыми, то нужно рассматривать с 1 и 2 простыми, сейчас оптимум простых от 0 до 3; 4-ре простых, как понимаю, считаем хуже (по времени), чем три простых.

Можно и четыре простых рассмотреть, если будет паттерн, где количество pqr будет больше 12.

-- 16.10.2025, 19:26 --

Huz в сообщении #1706116 писал(а):
I'm not sure exactly what you need for your Excel file, but if you send me an email with the definition I suspect I can easily provide it as a CSV file. (Keeping up with the forum via translation is hard work.)


Thanks for the offer!
Maybe I'll write later. Or patterns can be generated by Dmitry on his side

 
 
 
 Re: Пентадекатлон мечты
Сообщение16.10.2025, 19:28 
EUgeneUS в сообщении #1706054 писал(а):
1. А существуют ли паттерны типов "4-0-13-4 (9)" и "5-0-13-3 (9)"?
Про эти пока не знаю, зато вот что генератор выдал паттерны 5-0-6-10(9) и 5-0-6-10(8) и 5-0-5-11(8). А ведь у последних двух lcm будет в 59^2=3481 раз меньше, 8.5e39 вместо 3e43, т.е. они более выгодные выходит.

 
 
 
 Re: Пентадекатлон мечты
Сообщение16.10.2025, 19:33 
EUgeneUS в сообщении #1706064 писал(а):
vicvolf в сообщении #1706060 писал(а):
Для паттерна D(36,15) вероятность того, что случайное $n \leq x$ удовлетворяет паттерну, равна:
$\boxed{P_{\text{pat}}(x) = \frac{\mathfrak{S}(H)}{1{,}307{,}674{,}368{,}000} \cdot \frac{1}{42{,}074{,}422{,}790{,}400 \cdot (\log x)^{15}}}$
где:
- $\mathfrak{S}(H)$ — сингулярный ряд для множества $H$ из 15 сдвигов
- $\log x$ — натуральный логарифм

Тут грубое приближение. В числителе должен быть множитель, зависящий от $\ln (\ln x)$.
Мне кажется, что мы говорим о разном. Не могли бы Вы сформулировать задачу?

 
 
 
 Re: Пентадекатлон мечты
Сообщение16.10.2025, 20:09 
Аватара пользователя
Dmitriy40 в сообщении #1706141 писал(а):
. А ведь у последних двух lcm будет в 59^2=3481 раз меньше, 8.5e39 вместо 3e43, т.е. они более выгодные выходит.

В любом случае нужно собрать статистику и обсчитать один из них, где количество pqr больше.

В первом приближении, по сравнению с 3 простыми:
количество проверок вырастет примерно (несколько меньше) в 25 раз. (Насколько меньше считать надо)
Число, до которого считаем уменьшится примерно в 3481/25 раз, может даже сильнее.

 
 
 
 Re: Пентадекатлон мечты
Сообщение16.10.2025, 20:31 
Аватара пользователя
Погодите. А точно ничего не путаете? VAL говорил, что меньше 3-х одиночных простых не бывает. Правда, это вроде про D(48,20), а не про D(48,21).

А сейчас промолчал почему-то...

 
 
 
 Re: Пентадекатлон мечты
Сообщение16.10.2025, 20:35 
Аватара пользователя
vicvolf в сообщении #1706142 писал(а):
Мне кажется, что мы говорим о разном

Скорее всего.
vicvolf в сообщении #1706142 писал(а):
Не могли бы Вы сформулировать задачу?


В этой теме обсуждается поиск цепочек последовательных натуральных чисел с одинаковым количеством делителей.

Задача: мы начали искать какую-то такую цепочку, например $D(48, 21)$ - 21 последовательное натуральное число с 48 делителями у каждого.
Вопрос задачи: мы эту цепочку найдем когда? Через месяц или когда звезды потухнут, а черные дыры испарятся?

-- 16.10.2025, 20:37 --

Yadryara в сообщении #1706150 писал(а):
VAL говорил, что меньше 3-х одиночных простых не бывает. Правда, это вроде про D(48,20), а не про D(48,21).


Вот и я откуда-то помню, что меньше трех не бывает....
При увеличение длины минимальное количество простых не может уменьшитлся.

 
 
 
 Re: Пентадекатлон мечты
Сообщение16.10.2025, 22:11 
DemISdx в сообщении #1706122 писал(а):
VAL в сообщении #1706058 писал(а):
Кстати, подоспели еще два числа. Для YAFU совсем пустяковые.
Тем более, что если одно разложится как надо, другое можно не трогать (они для одного и того же $k$)
[..]
Готово:
[..]
Отлично!
$M(660) \ge 8$

(Начало цепочки)

Код:
n = 178353037164443191420993084423873132384211615394283272657775750588426762431323280921857168222051415675679949991958570238361110179915095057809659628212890621
n + 4 = 5^10 × 29^4 × 59^2 × 18048219939232848996982799577847 × 411007811788710203897049716383490275573432121068325927350694005386181570469828213280067494044813333738314087
n + 7 = 2^2 × 19^10 × 37^4 × 567603168432476980091953008703632841603775561512865720516291 × 6836483990413877127279034790983327369712289266086653351276391266794364495107
Помнил, что $k=660$ упорно не поддавалось мне 3 года назад.
Но когда заглянул в давние проги, понял, что я почему-то зациклился на поиске цепочек через 8 isprime :shock:
Переделал на 4 isprime и все легко нашлось.

 
 
 
 Re: Пентадекатлон мечты
Сообщение16.10.2025, 22:24 
EUgeneUS в сообщении #1706147 писал(а):
Dmitriy40 в сообщении #1706141 писал(а):
. А ведь у последних двух lcm будет в 59^2=3481 раз меньше, 8.5e39 вместо 3e43, т.е. они более выгодные выходит.
В любом случае нужно собрать статистику и обсчитать один из них, где количество pqr больше.
Максимальное значение pqr пока такое: 5+0+8+8(8). Таких паттернов найдено уже 38шт, работа не закончилась. Первый найденный:
v=[ 4, 37791, 2, 25, 24, 1, 98, 363, 20, 1, 18, 1, 32, 105, 338, 1, 12, 1, 31790, 9, 20216];
Чтобы из него получить допустимый по модулю 3 надо правую 9 превратить в 243.

-- 16.10.2025, 22:25 --

EUgeneUS в сообщении #1706152 писал(а):
Вот и я откуда-то помню, что меньше трех не бывает....
Возможно не бывает без вот таких фокусов с $3^5$ ...

-- 16.10.2025, 23:16 --

Поиском по одному паттерну с тремя простыми нашлась одна valids=18 и три valids=17 (ну и 16 несколько):

(Оффтоп)

16948256634087746076068267461645252005741587516704870546: 48, 48, 48, 48, 48, 48, 48, 12, 96, 48, 48, 48, 48, 48, 48, 48, 48,192, 48, 48, 48, valids=18
16644786016901643993575650440389543320200234448955724946: 24, 48, 24, 24, 48, 48, 48, 48, 48, 48, 48, 24, 48, 48, 48, 48, 48, 48, 48, 48, 48, valids=17
20925630527640079044678256122035683041455354403224364946: 48, 48, 24, 96, 48, 48, 48, 48, 48, 48,192, 48, 48, 48, 48, 48, 48, 48, 24, 48, 48, valids=17
21641763311941630849890325221249445044529822944029624146: 48, 48, 48, 24, 96, 48, 48, 48, 24, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 96, 48, valids=17

 
 
 
 Re: Пентадекатлон мечты
Сообщение17.10.2025, 05:10 
Аватара пользователя
Dmitriy40 в сообщении #1706155 писал(а):
v=[ 4, 37791, 2, 25, 24, 1, 98, 363, 20, 1, 18, 1, 32, 105, 338, 1, 12, 1, 31790, 9, 20216];
Чтобы из него получить допустимый по модулю 3 надо правую 9 превратить в 243.


Запустил расчет статистики по паттерну
Код:
v=[ 4, 37791, 1058, 25, 20184, 961, 98, 363, 20, 1369, 18, 1681, 32, 194145, 338, 2209, 12, 2809, 31790, 243, 20216];\\ 5+0+8+8(8)
nd=48;\\Количество делителей
pr2=primes([5,53]);\\Эти квадраты размещены
ip=20;\\Перебирать будем по месту +20


Прогнозирует 13-14 часов, вместо 20-21 часа для 9 необязательных простых в квадрате.
Это эффект от улучшения скорости факторизации на менее размерных числах.
Считается тут:
Код:
i1=round(1e7); i2=i1+round(1e5);\\Интервал счёта, справа не включая

В боевом расчете числа будут более размерными. Так что этот эффект может нивелироваться.

 
 
 
 Re: Пентадекатлон мечты
Сообщение17.10.2025, 05:51 
Аватара пользователя
VAL в сообщении #1704105 писал(а):
EUgeneUS в сообщении #1704102 писал(а):
полусотня VS треть миллиона (и только на перестановках минимальных необязательных простых)
Ну извините, миллиона логических ядер на моих 4-х компах не нашлось :cry:

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

Давайте, кстати, взглянем на обновлённую таблицу лучших приближений к D(48,21):

Код:
Start                                                     Location              Valids
17668887847524548413038893976018715843277693308027547     11111111111111111111      20  VAL
26775093546337571754412744723988589091340703171346        1111111 1111111111 11     19  An
85214054718602387929373909199904790013177732572016804946  1111111 1111111111 11     19  VAL
51684540038790306040313810619606026245800104809434        11 111111 1111111 111     18  An
72909466110460584674297272553362643585315288960146        1111111 1111 11 11111     18  An
82702393061651749407237510142718298553252873153434        1 11 11111111 1111111     18  An
154631495973083613535277148109710834053326309716946       111  11111111111111 1     18  An
585605360962144936768057576267008749038198122219346       1111111 111 1111111 1     18  An
606402818949710702556903161178143151197645296548946       11111 1 1111111111 11     18  An
628680904801738074581702744562430440461822260856146       11111 111111111 111 1     18  An
7463656036994854901626760003614676193212978675835346      111111111  1111 11111     18  An
16948256634087746076068267461645252005741587516704870546  1111111  11111111 111     18  Dm
29825395661688231658603848650736899419196053570174356946  111111111111111 11  1     18  VAL
90715763859608616730714175556209422588238079327693680146  1111111111111111 1  1     18  VAL

Видите большущую разницу в величине чисел? Так вот, маленькие числа найдены именно этим многопаттерным способом.

 
 
 
 Re: Пентадекатлон мечты
Сообщение17.10.2025, 10:35 
VAL в сообщении #1706081 писал(а):
vicvolf в сообщении #1706074 писал(а):
Мне не удалось найти интернет-источники, которые подтверждают это конкретное обозначение или упомянутую вами статью Дюнша и Эгглтона 1989 года.
ссылка
Спасибо! Ознакомился со статьей. Интересно, но там нет вывода асимтотик количества цепочек и вероятности, поэтому пришлось сделать.

Оценка вероятности существования цепочек чисел с одинаковым числом делителей

Постановка задачи
Рассмотрим задачу о нахождении цепочек последовательных натуральных чисел, имеющих одинаковое фиксированное количество делителей. Формально: для заданных натуральных чисел $ k $ и $ m $ мы хотим оценить вероятность того, что для случайного $ n \leq x $ выполняется:
$d(n) = d(n+1) = \cdots = d(n+m-1) = k$
где $ d(n) $ — число положительных делителей $ n $.

Вывод формул:
1. Асимптотика для одного числа
Известный результат в аналитической теории чисел утверждает, что для фиксированного $ k $ количество чисел $ n \leq x $ с $ d(n) = k $ имеет асимптотику:
$N_k(x) \sim C_k \cdot x \cdot \frac{(\log\log x)^{a(k)}}{\log x}$
где:
- $ C_k > 0 $ — постоянная, зависящая от мультипликативной структуры $ k $
- $ a(k) $ — неотрицательное целое число, определяемое разложением $ k $ на простые множители
Вероятность для одного числа:
$P_1(k) = \frac{N_k(x)}{x} \sim C_k \cdot \frac{(\log\log x)^{a(k)}}{\log x}$

2. Наивная оценка (предположение о независимости)
Если бы события $ d(n+i) = k $ были независимы для разных $ i $, то вероятность цепочки длины $ m $ оценивалась бы как:
$P_{\text{naive}}(m,k) \sim \left[C_k \cdot \frac{(\log\log x)^{a(k)}}{\log x}\right]^m$

3. Учёт локальных зависимостей
На самом деле, числа в цепочке тесно связаны арифметическими зависимостями, которые влияют на вероятность. Основные источники зависимостей:
Структурные ограничения на показатели степеней
Число с фиксированным $ k $ делителями имеет жёсткую структуру. Если $k = p_1^{a_1} \cdots p_r^{a_r}$, то $n = q_1^{b_1} \cdots q_r^{b_r}$, где $ (b_1+1)\cdots(b_r+1) = k $. Показатели $ b_i $ жёстко зафиксированы.

Появляется комбинаторный множитель $ \frac{1}{m!} $- учёт неразличимости структур при распределении простых чисел по позициям в цепочке.

Локальные корреляции от малых простых
Малые простые создают сильные корреляции между соседними числами:
- Запрет одинаковых простых делителей: Если $ n $ и $ n+1 $ оба делятся на простое $ p $, то $ p \mid 1 $ — невозможно
-Структурные условия делимости: Для данного $ k $ возможны только определённые комбинации показателей
Появляется сингулярный ряд $ \mathfrak{S}(H) $, учитывающий корреляции между разными позициями:
$\mathfrak{S}(H) = \prod_p \frac{\gamma_p(H)}{(1 - 1/p)^m}$
где $ \gamma_p(H) $ — вероятность, что все числа в цепочке "проходят" локальные условия по модулю $ p $.

Арифметические прогрессии с запретами
Для каждого малого простого $ p $ некоторые остатки $ n \mod p $ запрещены.

Вычисления:
1. Для фиксированного $ k $ определяем, какие остатки $ r \mod p $ возможны для чисел с $ d(n) = k $
2. Находим остатки $ r \mod p $, для которых ВСЕ числа $ n, n+1, \ldots, n+m-1 $ удовлетворяют индивидуальным условиям
3. $ v_p(H) $ = количество запрещённых остатков $ r \mod p $

Получаем поправочный множитель $ \prod_{p \mid L} \frac{1}{1 - \frac{v_p(H)}{p}} $, где $ L = \text{НОК}(1, 2, \ldots, m) $ — параметр, определяющий множество малых простых, по которым учитываются локальные зависимости.

Объединяя все поправки, получаем эвристическую формулу:
$\boxed{P(m,k) \sim \frac{\mathfrak{S}(H)}{m!} \cdot \left[C_k \cdot \frac{(\log\log x)^{a(k)}}{\log x}\right]^m \cdot \prod_{p \mid L} \frac{1}{1 - \frac{\nu_p(H)}{p}}}$

Пример: D(48,21)
Исходные данные:
- $ k = 48 $, $ m = 21 $, $ x = 10^{50} $
- Для $ k = 48 $: $ a(48) = 4 $, $ C_{48} \approx 0.1 $
- $ L = \text{НОК}(1,2,\ldots,21) = 232{,}792{,}560 $

Вычисление параметров:
- $ \log x = \log(10^{50}) = 50 \cdot \log 10 \approx 115.13 $
- $ \log\log x = \log(115.13) \approx 4.746 $
- $ 21! \approx 5.1 \times 10^{19} $

1. Вероятность одного числа
$P_1(48) \sim 0.1 \cdot \frac{(4.746)^4}{115.13}$
$4.746^2 \approx 22.52,\quad 4.746^4 \approx 507.0$
$P_1(48) \approx 0.1 \cdot \frac{507.0}{115.13} \approx 0.1 \cdot 4.404 \approx 0.4404$

2. Наивная оценка цепочки
$P_{\text{naive}} \sim (0.4404)^{21}$
$\log_{10}(P_{\text{naive}}) = 21 \cdot \log_{10}(0.4404) = 21 \cdot (-0.3562) \approx -7.48$
$P_{\text{naive}} \approx 10^{-7.48} \approx 3.31 \times 10^{-8}$

3. Учёт зависимостей
Оценим поправочные множители:
- $ \frac{\mathfrak{S}(H)}{21!} \approx 10^{-20} $ (сильные структурные ограничения для m=21)
- $ \prod_{p \mid L} \frac{1}{1 - \frac{\nu_p(H)}{p}} \approx 2 $ (учёт влияния малых простых)

Итоговая вероятность:
$P(48,21) \sim 10^{-20} \cdot 3.31 \times 10^{-8} \cdot 2 \approx 6.62 \times 10^{-28}$

4. Ожидаемое количество цепочек
$N_{\text{expected}} \sim x \cdot P(48,21) = 10^{50} \cdot 6.62 \times 10^{-28} \approx 6.62 \times 10^{22}$

Выводы:
Для D(48,21) в диапазоне до $ 10^{50} $:
$P(48,21) \sim 6.6 \times 10^{-28}$
$N_{\text{expected}} \sim 6.6 \times 10^{22} \text{ цепочек}$
- Цепочка D(48,21) почти наверняка существует в этом диапазоне
- Ожидается огромное количество экземпляров ($ \sim 10^{22} $).

 
 
 
 Re: Пентадекатлон мечты
Сообщение17.10.2025, 10:58 
Аватара пользователя
Хорошие новости надо сообщать сразу, чего же тянуть кота за резину.

Yadryara в сообщении #1706051 писал(а):
Моё время счёта — 38 часов.

Я думал. что у Демиса займёт 25-30 часов. Ан нет — уложился в 10 часов в один поток!!

Вот такая штука практика.

Так что очередь за компом VALа. Не о 32-х потоках речь идёт, а об одном, для теста. 7-й или 8-й зеркальный комплект на выбор. Программа уже готова, её только запустить на PARI.

И кстати, VAL, вопрос Дмитрия тоже не заметили?

 
 
 
 Re: Пентадекатлон мечты
Сообщение17.10.2025, 12:38 
EUgeneUS в сообщении #1706128 писал(а):
Dmitriy40 в сообщении #1706117 писал(а):
v=[ 9, 50, 49, 12, 289, 338, 1815, 2888, 1, 126, 1, 20, 3, 2, 1, 96, 35, 22, 117, 4, 1]
чудо какое :D
Надо статистику на него напустить. А как, если там нет простых?
И однако в этом чуде 0-6-7-8(8) тоже находятся цепочки! Запускал на ночь, чистый PARI, медленно, но нашлись 8 цепочек, из которых одна даже valids=17:
96100031146543695632608418489278806868523936309649: 28, 48, 48, 48, 48, 48, 48, 48, 48, 48, 24, 48, 24, 48, 48, 48, 48, 48, 48, 24, 48, valids=17
Остальные vailds=10-14.
Скорость перебора 60с на 1e6 значений i, при m=lcm(v)=2.294e41, т.е. 3.8e45/с.

С паттерном 5-0-8-8(8) тоже нашлись две длинные цепочки:
839959258412050706582280265714599432746929162531861405650: 48, 48, 48, 48, 48, 48, 48, 48, 24, 48, 48, 24, 48, 24, 48, 48, 48, 24, 48, 48, 48, valids=17
1011988149789983961687458524958725118967506966040950548050: 48, 48, 96, 48, 48, 96, 48, 48, 48, 24, 48, 24, 96, 48, 48, 48, 48, 48, 48, 48, 48, valids=16
Остальные 10шт valids=8-14.

Ну и в 3-0-13-5(9) нашлась 4-я valids=17:
39256746417897062753293437800667770183999173850948787346: 48, 48,192, 48, 48, 48, 48, 48, 48, 48, 24, 48, 48, 12, 48, 48, 48, 48, 48, 24, 48, valids=17

 
 
 
 Re: Пентадекатлон мечты
Сообщение17.10.2025, 12:46 
Аватара пользователя
Dmitriy40 в сообщении #1706177 писал(а):
И однако в этом чуде 0-6-7-8(8) тоже находятся цепочки! Запускал на ночь, чистый PARI, медленно, но нашлись 8 цепочек, из которых одна даже valids=17:
96100031146543695632608418489278806868523936309649: 28, 48, 48, 48, 48, 48, 48, 48, 48, 48, 24, 48, 24, 48, 48, 48, 48, 48, 48, 24, 48, valids=17
Остальные vailds=10-14.
Скорость перебора 60с на 1e6 значений i, при m=lcm(v)=2.294e41, т.е. 3.8e45/с.


А куда бы они делись?
В этом паттерне цепочек будет раз в $5^3=125$ больше, чем в паттерне с 3 простыми. В расчете на тот же диапазон $i$.
Оценка наивная, завышенная, но думаю раз в 100 будет.
Можете скинуть готовый такой паттерн (с расставленными квадратами простых, и правильной степенью тройки)?
А я вечером поставлю сбор статистики и на выходных посчитаю его.

-- 17.10.2025, 12:49 --

а с 1 и 2 простыми что-то интересное из паттернов не нашлось?

-- 17.10.2025, 13:04 --

vicvolf в сообщении #1706167 писал(а):
Постановка задачи
Рассмотрим задачу о нахождении цепочек последовательных натуральных чисел, имеющих одинаковое фиксированное количество делителей. Формально: для заданных натуральных чисел $ k $ и $ m $ мы хотим оценить вероятность того, что для случайного $ n \leq x $ выполняется:
$d(n) = d(n+1) = \cdots = d(n+m-1) = k$
где $ d(n) $ — число положительных делителей $ n $.


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

A119479, A292580 и статьи разделе LINKS к этим последовательностям.

 
 
 [ Сообщений: 3726 ]  На страницу Пред.  1 ... 244, 245, 246, 247, 248, 249  След.


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