Сумма цифр у кратного числа

[maxal]

General
Отправьте в OEIS новую последовательность:
a(n) = minimal positive integer m such that A077196(m)=n
12 членов у ваc, как я понял, уже есть

[Sasha2]

Насчет 17 все очень даже тривиально
Ответ 2
Число 100000001.

[General]

maxal писал(а):

General
Отправьте в OEIS новую последовательность:
a(n) = minimal positive integer m such that A077196(m)=n
12 членов у ваc, как я понял, уже есть

Действительно, хорошая идея, спасибо. Попробую, может, до понедельника a(13) всё-таки найдётся, а если нет - то 12 отошлю.
Сейчас последоватлеьность такая:
1, 7, 3, 79, 41, 33, 239, 2629, 9, 2981, 21649, 813, ?, 51139, 13947, ?, ?, 99,
и ещё а(27)=999, а(36)=9999

Задача очень интересная, написал о ней у себя на сайте:
О сумме цифр, обобщённом признаке делимости и одной нерешённой задаче

[maxal]

General
Кстати, по какому алгоритму вы вычисляли значения A077196?
И сколько суммарно потребовалось времени, чтобы вычислить 56000 значений?

[Руст]

Найти число n для которого $a(n)=m$ можно таким образом. Пусть $N=\frac{10^m-1}{9}$. Ясно, что $S(N)=m$. Пусть $n|N$. Тогда m является периодом числа 10 по модулю n. Допустим, что это минимальный период. Пусть число R делится на n. Тогда существует делитель b числа N для которого $n|b|N, s(b)\le S(R)$. Доказательство простое, если $R\ge 10^m$ заменяем степени меньшими, группируем цифры если есть переполнение, повторяя процедуру несколько раз получим искомое число b. Поэтому просматривая делители числа N находим (пусть не минимальное) число n, для которого $a(n)=m$.
Например для m=13 надо факторизовать число N из 13 единиц и если для некоторого минимального делителя n все делители b $n|b|N$ имеют $s(b)\ge 13$, то n нам подходит.

[Руст]

Обозначим через $m(n), b(n)$ функции, для которых $m(n)$ минимальная сумма цифр для чисел делящихся на n, b(n) минимальное число с суммой цифр $m(n)$, делящиеся на n. Пусть $a(m)$ минимальное число $n$, такое, что $m(n)=m$ (я раньше другое обозначал, не совпадающее с обозначениями автора).
Приведу алгоритм вычисления функции $a(m)$ для любого основания исчисления r. В соответствии с этим придётся разделит простые числа на нулевой класс, состоящий из делителей основания r (2,5 для r=10), первый класс, состоящий из простых делителей числа r-1 (3, для r=10) и общий класс - остальные простые. Каждое число $n=n_0n_1n_2$ разлагается на множители с простыми делителями из нулевого класса, первого класса и общего класса, например $n=108=4*27*1$ для $r=10$. Очевидно $m(n)=m(n_1*n_2),b(n)=b(n_1*n_2)r^k$, где k легко вычисляется по разложениям $n_0,r$.
Пусть $n=n_2$ (без простых делителе нулевого и первого класса). Вычислим для такого числа

$$n=n_2=\prod_i p_i^{k_i}$$

минимальный период для основания r по модулю n как $T(n)=gcd(T(p_i^{k_i})$. При этом вначале вычисляется $T(p_i)$ факторизацией числа $p_i-1$ и делением на простые числа $q|p_i-1$ периода, первоначально взятого как $p_i-1$ и сокращённого на q, пока остается периодом. Далее вычисляется на какую степень делится $v_{p_i}(r^{T(p_i)}-1)$, что дает $T(p_i^{k_i})=T(p_i)*p_i^c, c=max(0,k_i-v_{p_i}(r^{T(p_i)}-1))$. Тогда число из T(n) единиц делится на n, т.е. $m(n)\le T(n),b(n)\le N(T(n))$, где $N(k)$ число из k единиц $N(k)=\frac{r^k-1}{r-1}$. Для произвольного n минимальное число состоящее только из цифр 1 и возможно из нулей в конце находится из $N(l(n))*r^k, l(n)=\frac{n_1T(n)}{(n_1,T(n))}$.
Пусть $l_1=l(b(n))$. Тогда число из $l_1$ единиц и число из $l(n)$ единиц делятся на $n_1n_2$, так как $l(n)$ минимальное число из одних 1 делящихся на $n_1n_2$, получаем $l(n)|l_1$ (иначе найдётся число с меньшим количеством 1, делящийся на n). Была идея, как отсюда получит, что $m(n)|l(n)$ и в качестве числа $b$ (пусть не минимального из $s(b)=m(n)$ можно взять $n|b|N(l(n))$. Идею потерял. Соответственно возможно не минимальное можно искать так $a(m)=p_1^{k_1}q$, где $p_1$ простое число первого класса, q простой делитель $N(m)$ числа из m единиц, точнее даже как $q|\Phi_m(r)$ - делитель значения кругового многочлена.
Похоже, что это даст минимальное $a(m)$. Соответственно $a(13)$ надо искать как минимальный простой делитель $\Phi_{13}(10)=\frac{10^{13}-1}{9}$. Наверно из-за простоты этого числа $a(13)$ большое и вы GENTRAl не могли найти.

[maxal]

Руст
Суммы 13 и 16 по твоему рецепту нашлись:
A077196(265371653)=13
A077196(477076475359)=16
Правда, я не мудрствуя лукаво, просто перебрал делители $\frac{10^n-1}{9}$, и для каждого вычислил значения A077196.

Добавлено спустя 1 час 49 минут 30 секунд:

Руст в сообщении #191758 писал(а):

В соответствии с этим придётся разделит простые числа на нулевой класс, состоящий из делителей основания r (2,5 для r=10), первый класс, состоящий из простых делителей числа r-1 (3, для r=10) и общий класс - остальные простые. Каждое число $n=n_0n_1n_2$ разлагается на множители с простыми делителями из нулевого класса, первого класса и общего класса, например $n=108=4*27*1$ для $r=10$. Очевидно $m(n)=m(n_1*n_2),b(n)=b(n_1*n_2)r^k$, где k легко вычисляется по разложениям $n_0,r$.

Последнее равенство неверно. Например для $n=6$, $r=10$:

$$b(6)=12\ne b(3)\cdot 10=30.$$

[Руст]

Да $b(n)$ как минимальный не обязательно так представляется. Дальше я избегал от нахождения минимального, а просто искал хотя бы одно из значений специального вида, среди делителей числа $N(l(n))*r^k$.

[General]

Здорово!
Написал большой пост про алгоритм, но что-то проглючило, пока напишу, что
A077196(2071723)=17
А собственно кратное - 1100203001211
Времени затрачено чекунды 3

[maxal]

General
Ну собственно большой пост писать необязательно - скорее всего используется вариация на тему динамического программирования. Сложность пропорциональна произведению $n$ и показателя $10$ по модулю $n$. Угадал?

[General]

Да-да, именно так.
За первый час нашлись значения A077196 где-то для первых 20-30 тысяч чисел, ну а после 50000 - где-то по 1000 значения за час (разумеется, перебирались только нечётные и не делящиеся на 5 числа)

[maxal]

Рассмотрим репьюнит $R_n=\frac{10^n-1}9=\underbrace{11\dots1}_{n}$. Как мы уже выяснили A077196$(R_n)=n$, а вот усиление этого утверждения:

Докажите, что всякое кратное числа $R_n$ содержит не менее $n$ ненулевых цифр.

(моё решение)

[Edward_Tur]

http://kvant.mirror1.mccme.ru/1971/06/r ... nta_ma.htm

[maxal]

Edward_Tur в сообщении #356433 писал(а):

http://kvant.mirror1.mccme.ru/1971/06/resheniya_zadachnika_kvanta_ma.htm

Если обобщить, то можно утверждать, что натуральные кратные числа $\frac{10^{mn}-1}{10^m-1}$ содержат не менее $n$ ненулевых цифр.
Для репьюнитов имеем $m=1$, в задаче из Кванта - $(m,n)=(2,6)$.

[maxal]

General в сообщении #191992 писал(а):

Написал большой пост про алгоритм, но что-то проглючило, пока напишу, что
A077196(2071723)=17
А собственно кратное - 1100203001211

Только сейчас заметил несостыковку. В вашем кратном сумма цифр равна 12, и поэтому A077196(2071723)=12, что я также подтверждаю своими вычислениями.

А вот A077196(5363222357)=17, и поэтому A173443(17) $\leq 5363222357$.