Как много последовательных чисел могут встретиться?

[svv]

Спасибо! Для пятёрок видно, что если не $40$, то $40\pm 9n$.

[Ktina]

Мне только что подсказали добрые люди, что максимальная длина цепочки не превосходит 8.

[Aritaborian]

Добрые люди это как-то обосновали?

[svv]

Что цепочки не могут быть длинными, видно из таких соображений.
Рассмотрим числа, которые отличаются только двумя последними цифрами, а сумма цифр $S$ у них одна и та же. Типа: $1027, 1036, 1045, 1054$ и т.д. Соседние отличаются на $9$. Значит, остаток от деления числа из этой последовательности на $S$ будет то нечётным, то чётным — то есть, за исключением $2$, не простым.

[Aritaborian]

Спасибо; понял.

[Ktina]

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

Добрые люди это как-то обосновали?

Добрые Люди писал(а):

На данный момент можно лишь заметить, что есть ограничение на длину цепочек. Среди трёх и более последовательных чисел встречается делящееся на 3. Тогда сумма цифр тоже делится на 3, и это же верно для остатка от деления числа на сумму цифр. Значит, он равен 3 в этом случае. Из этого пока ничего не следует, но если тот же аргумент применить к девяти последовательным числам, то среди них найдётся делящееся на 9, и тогда остаток будет делиться на 9, не будучи простым. Значит, максимальная длина цепочки не превосходит 8. Эта оценка сверху, скорее всего, не лучшая.

[Dmitriy40]

svv в сообщении #1224154 писал(а):

Для пятёрок видно, что если не $40$, то $40\pm 9n$.

Наблюдение подтверждается и дальше, как и строгое соответствие суммы 40 и младшей цифры 3. Проверено до $5\cdot 10^{11}$. "Шестёрок" не найдено.

(Оптимизация)

К сожалению, использование этого наблюдения для ускорения вычислений результата не дало, хоть проверять $1/9$ чисел, хоть $1/5$ (для поиска "пятёрок"), скорость отличается на считанные проценты. Видимо неподходящие числа в обоих случаях отбрасываются достаточно рано/быстро. Может конечно я плохо накодил ... Ну и париться с асм64 и avx2 пока что лень, не та задача.

[Aritaborian]

Dmitriy40, сколько машинного времени ушло на расколошмачивание этого объёма чисел? И если не секрет, ТТХ компьютера.

[Dmitriy40]

(Aritaborian)

Да не секрет: Intel Core i5 Haswell 4 ядра 3.7ГГц (остальное не влияет).
Программа на дельфи x32, без особых оптимизаций (только деление и взятие остатка оптимизировано на асме, дельфи для int64 чисел такую пургу компилит, мрак). Ну внутренний цикл перебора миллиона чисел чуток оптимизирован, не считает сумму цифр каждого числа, а использует предпросчитанные таблицы. А, да, цикл перебирает числа с шагом 5 - "пятёрки" не пропустятся, при обнаружении кандидата (а их где-то с один процент) область расширяется в обе стороны для определения реальной длины последовательности. Проверка чисел на простоту совсем тупая, делениями на простые до $\sqrt{x}$ (до ~50 тысяч делений на число вылезает). Переписывать вычислительный цикл на асм64 или avx2 лень (не вижу что можно этим сильно ускорить).
Счёт идёт примерно 18ч (несколько раз оптимизировал и перезапускал), в один поток.С увеличением чисел заметно затормаживается (на глаз - уже раза в 3 медленнее), очевидно проверка на простоту тормозит процесс.

[Aritaborian]

(Dmitriy40)

Спасибо.

[mihaild]

(Оффтоп)

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

Переписывать вычислительный цикл на асм64 или avx2 лень (не вижу что можно этим сильно ускорить).

Основная часть тут - это собственно проверка на простоту, и ее можно было бы очень хорошо ускорить, если бы были SIMD инструкции для деления или хотя бы умножения 64-битных чисел. Но нету.

-- 11.06.2017, 23:01 --

svv в сообщении #1224191 писал(а):

Соседние отличаются на $9$. Значит, остаток от деления числа из этой последовательности на $S$ будет то нечётным, то чётным — то есть, за исключением $2$, не простым.

Кажется этот аргумент не покрывает случай, когда у числа в разряде десятков стоит $9$ (тогда у числа, на $9$ большего, сумма цифр другая).

-- 11.06.2017, 23:21 --

До $10^{12}$: (последняя цифры, сумма цифр, сколько раз встретилось): [(('0', 49), 6), (('0', 67), 1), (('1', 58), 13), (('2', 31), 3), (('2', 49), 16), (('3', 40), 42), (('4', 31), 4), (('4', 67), 2), (('9', 58), 3)].
Т.е. сумма цифр сравнима с $4$ по модулю $9$.

[Dmitriy40]

Днём решил добить до $10^{12}$, запустил в 4 потока, только что завершилось.
Все результаты mihaild (чуть опередил) подтверждаю, полностью совпадают с моими.
Не ожидал что встретятся с младшей 9.

(Оффтоп)

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

Основная часть тут - это собственно проверка на простоту, и ее можно было бы очень хорошо ускорить, если бы были SIMD инструкции для деления или хотя бы умножения 64-битных чисел. Но нету.

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

[mihaild]

(Оффтоп)

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

Хотя умножение и не спасло бы, эти методы замены деления недостаточно точные для целых чисел.

Т.к. мы работаем в $\mathbb{Z}_{2^{64}}$, то можно заменить деление на фиксированный набор чисел (список простых) умножением на обратные по модулю - для делящихся нацело получим правильный результат - в частности, что-то меньшее $\frac{2^{64}}{p}$, для не делящихся - что-то большее.
Теоретически это можно было бы ускорить с помощью GPU, но я под них писать не умею.

[Dmitriy40]

(Оффтоп)

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

Т.к. мы работаем в $\mathbb{Z}_{2^{64}}$, то можно заменить деление на фиксированный набор чисел (список простых) умножением на обратные по модулю - для делящихся нацело получим правильный результат - в частности, что-то меньшее $\frac{2^{64}}{p}$, для не делящихся - что-то большее.

Наконец-то дошли руки разобраться с этим, действительно работает, оказалось я не то обратное число брал. Был не прав выше про недостаточную точность. Теперь думаю как это прикрутить к AVX2 без 64 бит умножений, задача-минимум: уложиться в 40 тактов на простое число, чтобы обогнать обычное деление.
UPD. Ха! Реализовал внутренний цикл, анализатор говорит 1.2 такта на число! И думаю можно сэкономить одну команду и получить ровно такт на число. Осталось добавить кучку таблиц и начальные проверки.