На какую наибольшую степень числа 3 может делиться сумма?

[Dmitriy40]

gris в сообщении #1701340 писал(а):

Dmitriy40, почему в Энциклопедии нет этих замечательных чисел?

Мне откуда знать? Никто не добавил. Добавьте.

[waxtep]

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

C:\>fsum.exe 1000000007
571737250
Time: 9.283s

Спасибо! Значит, получается, простое число порядка $10^8$ обсчитается за десятые доли секунды, но всего их перебрать надо тоже где-то $10^8$ - задача на годик плюс минус на хорошей машине. Хм. (и не факт, что что-то найдётся, ведь $\kappa_n\sim\kappa_{n-1}!$ - лишь туманная гипотеза/выдумка)

wrest, первооткрыватель двух шлемоблещущих чисел - gris конечно, мне же хотелось попробовать найти третье. Ведь... вот есть даже девятки - т.е. нулевой остаток в этих суммах встречается и не раз, да только не на своем месте. Рано или поздно мог бы и на нужном нолик выпасть

[Dmitriy40]

waxtep в сообщении #1701352 писал(а):

Значит, получается, простое число порядка $10^8$ обсчитается за десятые доли секунды,

Нет, за секунду:
C:\>fsum.exe 100000007
85226649
Time: 1.062s
Зависимость для одного числа от его величины линейная, но числа растут тоже почти линейно (логарифм из-за простых в знаменателе мало влияет), в сумме получается почти квадратично.
Но для времён менее полусекунды начинает влиять время запуска и передачи результата в PARI, потому время перестаёт падать квадратично при уменьшении чисел и становится ближе к линейному.

Для второй задачи, поиска ровно n "нулей", я сделал обработку сразу списка чисел (например все простые в каждой тысяче натуральных), это существенно повысило скорость. Плюс можно же запускать многопоточно. В итоге за 4.5ч в ~3 потока (вместо 4-х имеющихся, это глюки PARI под виндой) проверилось до 1e7. Значит до 1e8 мне хватит пары недель ... Тем более что и простые можно генерить прямо "на лету" (мне лень было добавлять этот код, как и многопоточность реализовывать), тогда PARI вообще не нужен.

[mihaild]

Моя текущая реализация https://github.com/mihaild/dxdy/blob/ma ... l/main.cpp на моей машине обещает перебрать до $10^8$ за сутки.

[Dmitriy40]

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

Моя текущая реализация https://github.com/mihaild/dxdy/blob/ma ... l/main.cpp на моей машине обещает перебрать до $10^8$ за сутки.

Это в 128 потоков что ли? Тогда верю в сутки. У меня их всего 4. Я на 1e7 остановил, найденные восьмёрки привёл выше.

[mihaild]

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

Это в 128 потоков что ли?

В 24. Восьмерки подтверждаю.

[Dmitriy40]

Кстати, была у меня мысль по ускорению: не выполнять взятие остатка каждое умножение, накопить штук 5-10 умножений (пока влезают в пару-тройку регистров) и потом один раз взять модуль. А уж сложений можно накопить тысячи-миллионы. Но прикинув сколько потребуется умножений и сложений для работы с длинным числом посчитал выигрыш сомнительным (не кардинальным).

И кстати сложение по модулю лучше делать как сложение плюс if, чем с % (скорость может подняться раза в 1.5, проверьте) - не думаю что компилятор заменит медленное деление на сравнение и вычитание.

[mihaild]

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

И кстати сложение по модулю лучше делать как сложение плюс if, чем с % (скорость может подняться раза в 1.5, проверьте)

Как именно? x += y; if (x > z) x -= z;? У меня сразу становится в полтора раза медленнее (всё целиком, не просто сложение; сложение, соответственно, работает сильно медленнее)
Что там получается в ассемблере - https://godbolt.org/z/6W4qv6ffh - я понять уже не могу.

[Dmitriy40]

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

Как именно? x += y; if (x > z) x -= z;?

Да, типа такого. Только в if знак >=, как и есть в вашем примере кода ниже.

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

У меня сразу становится в полтора раза медленнее (всё целиком, не просто сложение; сложение, соответственно, работает сильно медленнее)

Странно. Но хорошо что проверили.

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

Что там получается в ассемблере - https://godbolt.org/z/6W4qv6ffh - я понять уже не могу.

Там всё как написано, стр. 423-428 - вычитание и если оказалось не меньше, то перезапись на новое.
Тормозит вероятно из-за множества обращений в память, особенно по записи, тем более условных. Такие моменты (условная перезапись памяти) легко могут страшно тормозить. По хорошему должно быть сначала копирование в другой регистр (это есть), вычитание и если что, то модификация регистра (можно одной командой условной пересылки как у меня в коде выше), и лишь в итоге запись готового в память, уже без условий и лишь один раз.

-- 11.09.2025, 03:48 --

Обнаружил у себя ошибку для $2^{31}<p<2^{32}$, поправил, оба файла в облаке обновил, ссылки те же.

-- 11.09.2025, 04:06 --

Проверил как у меня будет при замене sub+cmovc на div: для $p=4294967291$ время ухудшается с 38.7с до 47.4с. Хм, не сильно, думал будет хуже, похоже команда div в процессорах оптимизирована для случая малых чисел.

[mihaild]

Внезапно - можно попросить LLM переписать код на CUDA (если просить написать с нуля, то получается бред), и после некоторого допинывания он вроде бы даже работает (по крайней мере предыдущие результаты воспроизводит), и считает до $10^8$ за 25 минут.
Нашел еще три девятки
73739857: [6235359, 6414028, 20707256, 29077216, 42789242, 48187907, 50455742, 59049130, 71542857]
78527249: [1309012, 1314912, 10538320, 24564045, 24937373, 32475313, 42528008, 48110782, 70855513]
98449157: [21143860, 23027419, 33619199, 48486686, 51781066, 53999947, 57086251, 64851692, 82766190]
Больше ничего интересного не нашлось.
До миллиарда обещает считаться двое суток.

[mihaild]

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

похоже команда div в процессорах оптимизирована для случая малых чисел

А какие числа тут малые?

[Dmitriy40]

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

А какие числа тут малые?

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

-- 11.09.2025, 19:09 --

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

Внезапно - можно попросить LLM переписать код на CUDA (если просить написать с нуля, то получается бред), и после некоторого допинывания он вроде бы даже работает (по крайней мере предыдущие результаты воспроизводит), и считает до $10^8$ за 25 минут.

Удиивтельно что LLM выдал достаточно хороший код, действительно внезапно ...
А вот что хорошо параллелится - не удивительно, тут же можно и по простым параллелить, и по факториалу по модулю. Код внутреннего цикла достаточно простой (умножение, деление, сложение, снова или деление или сравнение плюс условное вычитание, которое кстати на GPU делается вообще без штрафов) и в то же время не настолько простой чтобы уложиться в пяток тактов, как раз задачка для GPU.

[mihaild]

Реализация на CUDA https://github.com/mihaild/dxdy/blob/ma ... al/main.cu. Условное вычитание дало прирост примерно 20% к производительности, алгоритм Барретта при умножении еще примерно утроение. В итоге до $10^8$ считается за 390 секунд, до $10^9$ обещает 10 часов. Еще процентов на 10 можно было бы ускорить отправкой всех чисел на подсчет сразу, но мне больше нравится возможность следить за прогрессом.

-- 11.09.2025, 20:11 --

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

Удиивтельно что LLM выдал достаточно хороший код, действительно внезапно

Там в целом ничего сложного. Но всю обвязку с копированием я совсем не знаю, как писать, а читать документацию всегда было лень.
В целом у меня просто сильно устаревшее представление о GPU. Я как-то не задумывался, что на них можно на каждом ядре цикл с целочисленной арифметикой считать.

Нашлись девятки
125816333: [4168573, 41608562, 51583106, 53564485, 59596441, 64874051, 66242996, 109743687, 124273619]
128096569: [31083535, 36979974, 47158457, 47485268, 49934824, 60255887, 61654817, 69144802, 75898499]
137719801: [22771441, 34650819, 45451974, 63934796, 67245188, 87495486, 111732945, 116580790, 119821025]
150036223: [24363564, 39953214, 50425127, 68163059, 83537136, 86980045, 108542657, 112341436, 139766002]
Больше, наверное, девятки выкладывать смысла нет. Посмотрим, что найдется до миллиарда.

(Оффтоп)

Первый раз такой шум от GPU, и 83 градуса. Ну зимой буду считать до десяти миллиардов.