Запустить задачу на мощном компе

[denny]

Приветствую всех! Сейчас работаю над парой последовательностей для OEIS,
нужно провести длительные (но элементарные по сути) вычисления.
Пара знакомых не готовы доверить мне мощные ПК
хотел арендовать в компьютерном клубе, там тоже сторонний софт нельзя

Между тем любой участник dxdy взглянув на код поймет, что это чисто арифметика,
там нет никаких http-запросов, биткоинов и т.д.

Сейчас код оформлен на Julia, но легко переписать на Python. Есть на Github, не package,
не docker, просто текстовые файлы. Можно и здесь выложить.
Буду очень признателен, если кто-то сможет поучаствовать в вычислениях,
напишу благодарность при публикации на OEIS!
Заодно можно обсудить оптимизацию алгоритма.

[Aritaborian]

Возм., вам поможет Google Colab.

[EUgeneUS]

denny
Обратите внимание вот на эту тему.

1. Как показывает опыт,

denny в сообщении #1600820 писал(а):

Заодно можно обсудить оптимизацию алгоритма.

с этого имеет смысл начинать.

2. Как исторически сложилось, в авторы результата в OEIS записывались те, на чьих мощностях найден результат, а не авторы программ.

[denny]

EUgeneUS в сообщении #1600887 писал(а):

denny
Обратите внимание вот на эту тему.

1. Как показывает опыт,

denny в сообщении #1600820 писал(а):

Заодно можно обсудить оптимизацию алгоритма.

с этого имеет смысл начинать.

2. Как исторически сложилось, в авторы результата в OEIS записывались те, на чьих мощностях найден результат, а не авторы программ.

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

-- 13.07.2023, 23:16 --

Aritaborian в сообщении #1600836 писал(а):

Возм., вам поможет Google Colab.

Ага, спасибо! Возможно в моем случае это вариант

[mihaild]

А есть причины не выложить код сразу? Я бы попробовал покрутить (ну и где запускать тоже есть, но обещать не могу).

[denny]

mihaild в сообщении #1600915 писал(а):

А есть причины не выложить код сразу? Я бы попробовал покрутить (ну и где запускать тоже есть, но обещать не могу).

Прошу прощения, показалось сделал ссылку к "гитхаб".
Вот
https://github.com/lesobrod/egyptian-fractions
Там достаточно подробный Readme. Сюда все дублировать не очень удобно,
но чуть позже напишу, о чем идет речь.

[denny]

Отмечу, что я читал разные материалы на эту тему именно с точки зрения математики, теории чисел.
Похоже, тут ничего нового не придумаешь. Поэтому вопрос именно в разделе Computer Science.
Главное это алгоритмы и вычисления.

Кратко.
Гармонические числа $H(n)=\sum_{k=1}^{n}\dfrac{1}{k}$
Кроме $n = 1$, никогда не являются целыми.
Египетские дроби: $4/17 = 1/5 + 1/29 + 1/1233 + 1/3039345$
Кратчайшие египетские дроби: $4/17 = 1/5 + 1/30 + 1/510$
Обобщенные (mixed sign) египетские дроби: $4/17 = 1/4 - 1/68$

Посмотрим на расстояния от $H(n)$ до ближайших целых
$H(n)-\lfloor H(n) \rfloor$ и $\lceil H(n) \rceil - H(n)$
(все вычисления ведутся в Rationals) "в духе" именно гармонического ряда.
Появилась интуитивная идея: разложить эти расстояния на египетские дроби и найти кратчайшее разложение.
Наивно говоря, получить из гармонического числа целое "прикладыванием" минимального количества различных кусочков гармонического ряда.
Пример.
$n=10, H(n)= 7381/2520$
$3 - 7381/2520 = 179/2520 = 1/30 + 1/42 + 1/72$
$7381/2520 - 2 = 2341/2520 = 1/2 + 1/7 + 1/8 + 1/9 + 1/20$
(в обоих случаях указаны кратчайшие варианты)

Если обозначить $a(n)$ последовательность значений наименьших длин египетских дробей,
то $a(10) = 3$. Мне удалось вычислить $a(n)$ до $n=30$:

$$1, 1, 1, 2, 2, 3, 3, 3, 3, 2, 3, 4, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 4, 5, 5, 4, 4$$

После $n=30$ мой (довольно мощный) ноут начинает сильно шуметь, особенно если "попросить" Julia запустить все ядра.
Алгоритм поиска основан на переборе с рекурсией, и ничего более оптимального пока не находится.

Цитата:

If there is an expansion with $k$ terms, one of the denominators is at most $kq/p$.
So to check whether there is an expansion with at most $k$ terms: for each $m$ from $\lceil q/p\rceil $ to $\lfloor kq/p\rfloor$,
check recursively whether $ p/q-1/m $ has an expansion with at most $ k-1 $ terms.

В продолжение темы можно рассмотреть $b(n)$ - наименьшие длины обобщенных египетских дробей. Ясно, что $b(n) \leq a(n)$, поэтому перебор не слишком сильно возрастает.

В readme на гитхаб описание более подробное, код на Julia проверял на их форуме, говорят, оптимизировать больше особо нечего.
Если у кого есть права на review в OEIS, вот драфты:

https://oeis.org/draft/A364200
https://oeis.org/draft/A363937

[mihaild]

А какой получается максимальный знаменатель для $n \leq 30$?
И почему решено рассматривать $\min(H(n) - \lfloor H(n) \rfloor, \lceil H(n) \rceil - H(n))$ вместо отдельно округления вверх и вниз?

[denny]

mihaild в сообщении #1600959 писал(а):

А какой получается максимальный знаменатель для $n \leq 30$?
И почему решено рассматривать $ \min(H(n) - \lfloor H(n) \rfloor, \lceil H(n) \rceil - H(n)) $ вместо отдельно округления вверх и вниз?

К сожалению, промежуточные результаты (т.е. сами дроби) в коде не собираются, для ускорения считается только длина.
Но я включу сбор самих результатов, по крайней мере для небольших $n$

А с $\min$ это отдельная тема.
Мне написали ЛС (на другом форуме), что для такого типа дробей
$ X < Y \Rightarrow LSEF(X) < LSEF(Y) $
(LSEF means length of the shortest egyptian fraction)
Но тема с доказательством заглохла. Поэтому да, для полной гарантии надо оба отрезка отдельно рассматривать,
в ближайшее время внесу изменения.

[Dmitriy40]

mihaild в сообщении #1600959 писал(а):

А какой получается максимальный знаменатель для $n \leq 30$?

Выхлоп программы на PARI:

(Оффтоп)

? for(n=2,40,h=sum(i=1,n,1/i); print("H(",n,")=",h,": ",frac(h),", ",1-frac(h));)
H(2)=3/2: 1/2, 1/2
H(3)=11/6: 5/6, 1/6
H(4)=25/12: 1/12, 11/12
H(5)=137/60: 17/60, 43/60
H(6)=49/20: 9/20, 11/20
H(7)=363/140: 83/140, 57/140
H(8)=761/280: 201/280, 79/280
H(9)=7129/2520: 2089/2520, 431/2520
H(10)=7381/2520: 2341/2520, 179/2520
H(11)=83711/27720: 551/27720, 27169/27720
H(12)=86021/27720: 2861/27720, 24859/27720
H(13)=1145993/360360: 64913/360360, 295447/360360
H(14)=1171733/360360: 90653/360360, 269707/360360
H(15)=1195757/360360: 114677/360360, 245683/360360
H(16)=2436559/720720: 274399/720720, 446321/720720
H(17)=42142223/12252240: 5385503/12252240, 6866737/12252240
H(18)=14274301/4084080: 2022061/4084080, 2062019/4084080
H(19)=275295799/77597520: 42503239/77597520, 35094281/77597520
H(20)=55835135/15519504: 9276623/15519504, 6242881/15519504
H(21)=18858053/5173168: 3338549/5173168, 1834619/5173168
H(22)=19093197/5173168: 3573693/5173168, 1599475/5173168
H(23)=444316699/118982864: 87368107/118982864, 31614757/118982864
H(24)=1347822955/356948592: 276977179/356948592, 79971413/356948592
H(25)=34052522467/8923714800: 7281378067/8923714800, 1642336733/8923714800
H(26)=34395742267/8923714800: 7624597867/8923714800, 1299116933/8923714800
H(27)=312536252003/80313433200: 71595952403/80313433200, 8717480797/80313433200
H(28)=315404588903/80313433200: 74464289303/80313433200, 5849143897/80313433200
H(29)=9227046511387/2329089562800: 2239777822987/2329089562800, 89311739813/2329089562800
H(30)=9304682830147/2329089562800: 2317414141747/2329089562800, 11675421053/2329089562800
H(31)=290774257297357/72201776446800: 1967151510157/72201776446800, 70234624936643/72201776446800
H(32)=586061125622639/144403552893600: 8446914048239/144403552893600, 135956638845361/144403552893600
H(33)=53676090078349/13127595717600: 1165707207949/13127595717600, 11961888509651/13127595717600
H(34)=54062195834749/13127595717600: 1551812964349/13127595717600, 11575782753251/13127595717600
H(35)=54437269998109/13127595717600: 1926887127709/13127595717600, 11200708589891/13127595717600
H(36)=54801925434709/13127595717600: 2291542564309/13127595717600, 10836053153291/13127595717600
H(37)=2040798836801833/485721041551200: 97914670597033/485721041551200, 387806370954167/485721041551200
H(38)=2053580969474233/485721041551200: 110696803269433/485721041551200, 375024238281767/485721041551200
H(39)=2066035355155033/485721041551200: 123151188950233/485721041551200, 362569852600967/485721041551200
H(40)=2078178381193813/485721041551200: 135294214989013/485721041551200, 350426826562187/485721041551200

Но проверять все числа до знаменателя не всегда нужно, достаточно проверить диапазон $[x,2x]$ для некоторого $x$ обычно сильно меньшего половины знаменателя.

denny
Относительно легко проверяется что решений длиной 3 после n=14 нет вплоть до n=615 за исключением возможно n=226 (при котором знаменатель превышает 5.29e93).
Чуть сложнее, но тоже недолго, проверяются значения равные 4 для n до 30, они соответствуют текущему содержанию OEIS.
Значения 5 пока проверил для n до 30 кроме n=27, тоже совпадают с OEIS. Значение для n=27 что-то загрузился поиск, никак не найдёт.

И вопрос

ReadMe писал(а):

There is strong conjecture that for such kind of numbers

$$X<Y \Rightarrow LSEF(X) < LSEF(Y)$$

but this is very open question.

надо считать закрытым и опровергнутым: $LSEF(10)>LSEF(11)$.

[mihaild]

В смысле знаменатель египетских дробей а не гармонических чисел:) Хотя вопрос "какой может быть минимальный знаменатель при минимальном числе дробей" сложнее, чем просто "минимальное число дробей".
Если добавить эвристику "сначала перебирать знаменатели от $\lceil f \rceil \cdot 2$ до $\lceil k / f\rceil$, а уже потом от $\lceil f\rceil$ до $\lceil f \rceil \cdot 2$", то при $n \leq 30$ самый большой минимальный знаменатель получается 37281736631739600 при $n = 30$.
(я думал о том, не считаем ли мы по много раз одни и те же разложения, но, видимо, нет)

[Dmitriy40]

У меня самый большой знаменатель в разложении при n=28 (правда n=27 я пока так и не нашёл) (в списке только знаменатели) (если решений два, то показано с наименьшим числителем):

Используется синтаксис Text

n=2=3/2: 1/2=[2], len=1
n=3=11/6: 1/6=[6], len=1
n=4=25/12: 1/12=[12], len=1
n=5=137/60: 17/60=[4, 30], len=2
n=6=49/20: 9/20=[4, 5], len=2
n=7=363/140: 57/140=[3, 14, 420], len=3
n=8=761/280: 79/280=[4, 32, 1120], len=3
n=9=7129/2520: 431/2520=[6, 230, 57960], len=3
n=10=7381/2520: 179/2520=[15, 230, 57960], len=3
n=11=83711/27720: 551/27720=[56, 495], len=2
n=12=86021/27720: 2861/27720=[10, 312, 180180], len=3
n=13=1145993/360360: 64913/360360=[6, 75, 7480, 15315300], len=4
n=14=1171733/360360: 90653/360360=[4, 858, 2520], len=3
n=15=1195757/360360: 114677/360360=[4, 15, 858, 2520], len=4
n=16=2436559/720720: 274399/720720=[3, 22, 520, 55440], len=4
n=17=42142223/12252240: 6866737/12252240=[2, 17, 616, 1750320], len=4
n=18=14274301/4084080: 2062019/4084080=[2, 205, 72160, 66978912], len=4
n=19=275295799/77597520: 42503239/77597520=[2, 21, 8294, 24728880], len=4
n=20=55835135/15519504: 6242881/15519504=[3, 15, 444, 123728, 119629510], len=5
n=21=18858053/5173168: 1834619/5173168=[3, 47, 32080, 5152290, 1023565869340], len=5
n=22=19093197/5173168: 1599475/5173168=[4, 17, 2755, 4098960, 9608338319580], len=5
n=23=444316699/118982864: 31614757/118982864=[4, 64, 11979, 105365184, 27517925473038], len=5
n=24=1347822955/356948592: 79971413/356948592=[5, 42, 4305, 96155675, 961878294577200], len=5
n=25=34052522467/8923714800: 1642336733/8923714800=[6, 58, 7476, 67707640, 7669699600], len=5
n=26=34395742267/8923714800: 1299116933/8923714800=[7, 368, 173926, 19302383100], len=4
n=27=312536252003/80313433200: ?
n=28=315404588903/80313433200: 5849143897/80313433200=[14, 715, 559224, 70175996814, 2871270912355756419600], len=5
n=29=9227046511387/2329089562800: 89311739813/2329089562800=[27, 780, 36975, 14536368], len=4
n=30=9304682830147/2329089562800: 11675421053/2329089562800=[200, 77706, 16532874306, 59497349338165200], len=4

[mihaild]

Для $n = 28$ можно сильно меньше: [1420599600, 2012868, 43, 90, 26].

-- 14.07.2023, 13:17 --

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

надо считать закрытым и опровергнутым: $LSEF(10)>LSEF(11)$.

Я так понимаю, там была гипотеза что если $X$ - дробная часть гармонического числа, то из $X \leq 1/2$ следует $LSEF(X) \leq LSEF(1 - X)$, а из $X \geq 1/2$ следует $LSEF(X) \geq LSEF(1 - X)$ - т.е. что можно проверять только округление к ближайшему.

[Dmitriy40]

Вы правы, решений много, я находил не лучшие, есть например и такие:
n=28=315404588903/80313433200: 5849143897/80313433200=[27, 52, 65, 850, 14536368], len=5
n=28=315404588903/80313433200: 5849143897/80313433200=[27, 28, 22724, 38896, 126225], len=5

[mihaild]

Для $n$ от $31$ до $40$ решений длины меньше 5 нет, а длина 5 перебирается очень долго.
Может быть получится хотя бы для суммы двух найти решение быстрее чем перебором?
$\frac{1}{x} + \frac{1}{y} = \frac{a}{b}$
$(ax - b)(ay - b) = b^2$
Т.е. нам нужен такой $d$ - делитель $b^2$, что $b + d$ и $b + b^2 / d$ делятся на $a$. Но как его искать быстрее - непонятно.

Для всех $n \leq 30$ есть решение минимальной длины, в котором все знаменатели кроме двух не очень больше (десятки тысяч), и не содержат больших простых множителей.