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

[General]

а) Какое наименьшее значение может принимать сумма цифр числа, кратного 17-ти?
б) Числа, кратного 31-му?
в) Числа, кратного 41-му?

[worm2]

По-моему, во всех 3-х задачах ответ 2.
Нужно рассмотреть числа вида $10^n+1$, дальше очевидно.

Добавлено спустя 3 минуты 7 секунд:

Ан нет, не всё так просто

[ИСН]

Ох, непросто! Просто только у 17 и вообще у первообразных корней, а так прямо непонятно, что делать. Ну, то есть, для частных случаев понятно: выписывать все остатки от степеней 10, сидеть и перебирать, там немного...

[General]

Вот-вот, я сам так и перебирал (только программой, не вручную).

Особо интересно число 11233 - для него программа со всеми оптимизациями нашла кратное с минимальной суммой цифр минут за 30-40.

Пока (среди чисел, не делящихся на 3) наибольшее значение минимума суммы цифр кратных чисел достигается для числа 2981.
Ещё интересны числа 79, 407 и 239

[Руст]

Алгоритм простой. Надо выяснить порядок числа 10 по модулю числа a=17,31,41,...(взаимно простого с 10, в противном случае к этому сводится с помощью нулей в конце) m чётный или нет. Если он чётен, то $a|10^m-1=(10^{m/2}-1)(10^{m/2}+1)\to a|10^{m/2}+1$ и ответ 2. В случае нечётности ответ больше 2. Необходимым и достаточным условием нечётности является нечётность порядка 10 относительно любого нечётного простого делителя p числа а. Для этого необходимо, чтобы 10 был по крайней мере квадратичным вычетом, что легко проверяется.

[General]

Условия получения ответа 2 необходимо подкорректировать.

К примеру, для числа 11 или 17 оно срабатывает (среди остатков этих чисел на степени десятки имеется +1 и -1), а вот для числа 11*17=187, хотя последоватлеьность остатков степеней десятки на это число имеет чётный период, равный 16, но среди чисел, кратных 187-ми наименьшая сумма цифр будет равна 4 и достигаться в числе 210001

[Руст]

Руст писал(а):

$a|10^m-1=(10^{m/2}-1)(10^{m/2}+1)\to a|10^{m/2}+1$ и ответ 2.

Вообще то я вначале это писал для нечётного простого а или для степени простого числа. Для составного возможно деление разных сомножителей. Поэтому требуется уточнение. Пусть

$$a=\prod_i p_i^{k_i}$$

. Определим $m_i$ как минимальное число, для которого $p_i^{k_i}|10^{m_i}-1$. Если хотя бы одно из чисел $m_i$ нечётно то искомая сумма цифр $S>2$. Записывая $m_i=2^{r_i}l_i$ где $l_i$ нечётное получаем, что если $r_i$ разные, то $S>2$. Необходимым и достаточным условием $S=2$ является $r_i=r\ge 1 \forall i$. В частности если есть простые делители вида $p=3\mod 4$ число 10 не должен быть квадратичным вычетом по ним, а по всем делителям (если есть и такие) $p=1\mod 4$ число 10 должен быть квадратичным вычетом.
Интересная гипотеза: $S(a)\le 18$. Легко показать, что $S(99)=18$.

[maxal]

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

Интересная гипотеза: $S(a)\le 18$.

Я думаю, $S(a)$ неограничена. Идея - взять достаточно большой простой $p$ делитель числа $10^k-1$, тогда с большой вероятностью $S(p) > \log_k p.$
Так как существует ровно $k$ различных степеней 10 по модулю $p$, и сумма любых $t$ из них "покроет" не более $k^t$ вычетов по модулю $p$. Поэтому, если $k^t<p$, то становится вероятно, что 0 не покроется, а то есть $S(p)>t$.

Например, для опровержения $S(a)\leq 18$, можно попробовать взять $k=41$ и $p=201763709900322803748657942361$, для которых $\log_k p > 18.1$ Хотя проверить так ли это на самом деле тут будет довольно трудоемко.

[Руст]

Эта действительно глупая гипотеза (об этом я давно уже догадался), так как очевидно $S(10^n-1)=9n$.

[worm2]

Кстати, последовательность $S(n)$ имеется в OEIS (разумеется, кто бы сомневался!). Однако там мало членов, и в комментсах чушь написана.

[General]

Ух ты, спасибо, а я, честно говоря, там даже и не искал. Действительно, там материала очень мало и суждения поверхностные

Я нашёл числа, не делящиеся на 9, но у ктоторых S(n)=9. Наименьшее из них - число 717=3*239.

Ещё интересно число $2439=3^2*271$: оно не делится ни на 99, ни на 909, но S(2439)=18.

Среди чисел, не делящихся на 9 наибольшая S(n), равная 15-ти достигается у числа 13947=3*4649

А среди чисел, не делящихся на 3 наибольшее значение S(n), равное 11-ти достигается в порстом числе 21649

Завтра как уйду на работу, оставлю программу работать на весь день.

[maxal]

worm2 писал(а):

Кстати, последовательность $S(n)$ имеется в OEIS (разумеется, кто бы сомневался!). Однако там мало членов, и в комментсах чушь написана.

Отослал исправления к A077196, а заодно и к смежным A077194 и A077195.

[General]

А как туда отсылать исправления?

[maxal]

General
см. http://oeis.org/Submit.html

[General]

Спасибо, отослал им б-файл для чисел до 56000. Нашёл ещё одно число-рекордсмен, 51139=11*4649. S(51139)=14.

Что интересно, чисел с S=13 пока не нашлось