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

[denny]

Большое спасибо всем за поддержку! Очень хотелось бы найти первую $LSEF=6$

[mihaild]

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

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

Кстати если гипотеза была такая, то это тоже неправда:
$H(17) = 3 + \frac{5385503}{12252240}$, $\frac{5385503}{12252240} < 1/2$, но $LSEF(\frac{5385503}{12252240}) = 5$ а $LSEF(1 - \frac{5385503}{12252240}) = 4$.

[Dmitriy40]

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

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

denny
В такой формулировке вопрос тоже закрыт и опроевргнут:
n=17=42142223/12252240: 5385503/12252240=[3, 10, 161, 124865, 1873151280] vs 6866737/12252240=[2, 17, 616, 1750320], min=4
n=18=14274301/4084080: 2022061/4084080=[3, 7, 53, 20130, 2640766128] vs 2062019/4084080=[2, 205, 72160, 66978912], min=4
n=19=275295799/77597520: 35094281/77597520=[3, 9, 128, 294272, 5121436320] vs 42503239/77597520=[2, 21, 8294, 24728880], min=4
Меньшее значение имеет больший LSEF.

[denny]

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

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

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

Кстати если гипотеза была такая, то это тоже неправда:
$H(17) = 3 + \frac{5385503}{12252240}$, $\frac{5385503}{12252240} < 1/2$, но $LSEF(\frac{5385503}{12252240}) = 5$ а $LSEF(1 - \frac{5385503}{12252240}) = 4$.

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

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

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

denny
В такой формулировке вопрос тоже закрыт и опроевргнут:
n=17=42142223/12252240: 5385503/12252240=[3, 10, 161, 124865, 1873151280] vs 6866737/12252240=[2, 17, 616, 1750320], min=4
n=18=14274301/4084080: 2022061/4084080=[3, 7, 53, 20130, 2640766128] vs 2062019/4084080=[2, 205, 72160, 66978912], min=4
n=19=275295799/77597520: 35094281/77597520=[3, 9, 128, 294272, 5121436320] vs 42503239/77597520=[2, 21, 8294, 24728880], min=4
Меньшее значение имеет больший LSEF.

Вот это отлично! А то некто написал гипотезу и слился (это не здесь). Контрпримеры сам найти не смог. Теперь ок, внесена ясность.

[Dmitriy40]

$a(31)=5$:
n=31=290774257297357/72201776446800: 1967151510157/72201776446800=[87, 91, 210, 37297260, 2380278344400], len=5

[denny]

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

Значение для n=27 что-то загрузился поиск, никак не найдёт.

$n=27$ и $n=31$ посчитались быстрее, если заменить вручную

ceil(BigInt, inv(f)):floor(BigInt, k / f)

на

floor(BigInt, k / f):-1:ceil(BigInt, inv(f))

т.е на обратный порядок

-- 14.07.2023, 21:04 --

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

$a(31)=5$:
n=31=290774257297357/72201776446800: 1967151510157/72201776446800=[87, 91, 210, 37297260, 2380278344400], len=5

Отлично, вношу в OEIS draft. Буду рад дать ссылку на ваш аккаунт какой-то. Думаю, рано или поздно последовательность опубликуют.

[Dmitriy40]

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

посчитались быстрее, если заменить вручную

У меня своя программа, на медленном PARI/GP (пока что раздумываю как бы это дело на асме написать) . И там ограничения довольно хитро расставлены, да ещё и меняю их при каждом запуске.

(аккаунт)

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

Буду рад дать ссылку на ваш аккаунт какой-то.

Да можете просто написать "from _Dmitry Petukhov_" и OEIS сам подставит мой аккаунт там. А можете и не писать, невелика потеря.

[Dmitriy40]

Написал расчётный модуль перебора последних двух чисел на асме (меньше 20 команд процессора), вот что с ним насчиталось:
n=32=586061125622639/144403552893600: 8446914048239/144403552893600=[31, 39, 1680, 1153243, 15579194400], len=5
n=33=53676090078349/13127595717600: 1165707207949/13127595717600=[19, 29, 598, 87584, 4352400], len=5
n=34=54062195834749/13127595717600: 1551812964349/13127595717600=[16, 19, 325, 671853, 3214308333600], len=5
n=35=54437269998109/13127595717600: 1926887127709/13127595717600=[8, 46, 32844, 84448, 71345628900], len=5
n=36=54801925434709/13127595717600: 2291542564309/13127595717600=[6, 140, 1334, 20930400, 49228483941], len=5
Дополнительно проверил что $a(31\ldots69)\geq 5$.

[Dmitriy40]

Ещё пара значений:
n=38=2053580969474233/485721041551200: 110696803269433/485721041551200=[5, 36, 8050, 83936034, 797571496800], len=5
n=39=2066035355155033/485721041551200: 123151188950233/485721041551200=[4, 370, 1190, 20010754400, 20306063610], len=5

[Dmitriy40]

$a(42)\geq 6$. Примера ровно на 6 пока не нашёл.
$a(37)$ под вопросом, чтобы доказать что оно больше 5 надо перебрать порядка 8 триллионов чисел (разные продолжения $1/5+1/631+\ldots$), это пока нереально. Или таки найти пример длиной 5 ...

[Dmitriy40]

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

Или таки найти пример длиной 5 ...

Ура, она таки нашлась, значит $a(37)=5$:
n=37=2040798836801833/485721041551200: 97914670597033/485721041551200=[5, 741, 4234, 1949900, 31936191840], len=5

[Dmitriy40]

Хм, однако выходит что все $a(40\ldots45)\geq6$ ...
Значения $a(31\ldots39)=5$ в OEIS добавил.

[denny]

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

Хм, однако выходит что все $a(40\ldots45)\geq6$ ...
Значения $a(31\ldots39)=5$ в OEIS добавил.

А каков алгоритм таких проверок? Я бы на Julia сделал...

И еще хотелось бы поискать обобщенные, с разными знаками варианты (которые, естественно, короче уже найденных классических). Пока только $n=10$ и $n=22$ найдены.

[Dmitriy40]

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

А каков алгоритм таких проверок? Я бы на Julia сделал...

На самом деле асм тут и не нужен, он лишь ускоряет перебор когда нужно перебрать больше десятка-сотни тысяч чисел в какой-то позиции. Плюс пока у меня ограничение в нём на знаменатель ($<2^{64}$ ради простоты кода), потому большие знаменатели обрабатываются на PARI и медленно.
А сам алгоритм прост: ограничение глубины рекурсии до 4 (для поиска решений длиной 5). Если решения не найдено, значит $a()$ больше проверенного значения.
Плюс для ускорения нахождения решений с небольшими числами я ограничиваю верхний порог проверяемых чисел на самом глубоком уровне рекурсии и только если с таким условием решения не найдено, то запускаю второй (иногда и третий и четвёртый) раз уже только для непроверенного диапазона чисел (проход рекурсивного дерева без реальной проверки очень быстр).

-- 16.07.2023, 14:02 --

Кстати hint: если проверяем и $\{H(n)\}$ и $1-\{H(n)\}$ ($\{\}$ - дробная часть), то выгоднее сначала проверить максимальное из них - потому что в нём почти 100% будет первое значение $1/2$ и соответственно перебор остальных станет короче на одну позицию, что резко его ускорит, а перебор всех других значений в первой позиции выполняется вообще за секунды.
И ещё hint: на каждом уровне рекурсии выгоднее перебирать от больших знаменателей к меньшим — при этом следующему уровню остаётся число больше и длина перебора будет меньше. Если решения нет, то без разницы с какой стороны перебирать одинаковый объём вычислений, зато если решение есть и оно с достаточно малыми числами, то будет найдено быстрее/раньше. Тут могут быть исключения, вон много решений выше имеют наоборот минимальные числа в первых позициях, но всё же имеет смысл.

-- 16.07.2023, 14:12 --

denny
Я Вас поздравляю — все ранее поставленные задачи выполнены: и $a(31\ldots40)$ посчитаны, и первая 6-ка найдена:
n=40=2078178381193813/485721041551200: 135294214989013/485721041551200=[6, 10, 87, 2618, 6737367, 232301367698400], len=6

[Dmitriy40]

И ещё. При переборе от $\lceil 1/f \rceil$ до $\lfloor k/f \rfloor$ приличная часть будет перебираться минимум дважды. Например для $\{H(13)\}=64913/360360$ и длины 4 перебор третьего числа при первых двух $1/6+1/180$ будет $127\ldots252$, но $127$ будет потом перебрано ещё раз при первых двух $1/6+1/127$ с интервалом перебора $179\ldots357$. Для исключения таких повторов надо наложить дополнительное условие, например строгого возрастания знаменателей, тогда при первых двух $1/6+1/180$ будет перебираться не $127\ldots252$, а только лишь $181\ldots252$. А для первых $1/6+1/221$ перебирать останется лишь $222\ldots223$ вместо $112\ldots223$.

Вторым источником повторов может стать множественность представления дробей. Например для того же $\{H(13)\}=64913/360360$ первые два числа $1/6+1/84=1/7+1/28$ дают ровно одинаковый остаток для перебора и соответственно он будет перебран дважды. Как и $1/6+1/90=1/9+1/15$, и $1/6+1/105=1/7+1/30$, и $1/6+1/132=1/11+1/12$. Для больших $n$ и длин есть варианты и с десятками повторов. Правда большинство из них с относительно малыми объёмами перебора, потому на общее время не влияют, но есть и неприятные исключения.