Научный форум dxdy

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

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

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

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

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

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

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

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

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

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

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

Вообще то я вначале это писал для нечётного простого а или для степени простого числа. Для составного возможно деление разных сомножителей. Поэтому требуется уточнение. Пусть . Определим как минимальное число, для которого . Если хотя бы одно из чисел нечётно то искомая сумма цифр . Записывая где нечётное получаем, что если разные, то . Необходимым и достаточным условием является . В частности если есть простые делители вида число 10 не должен быть квадратичным вычетом по ним, а по всем делителям (если есть и такие) число 10 должен быть квадратичным вычетом.
Интересная гипотеза: . Легко показать, что .

Я думаю, неограничена. Идея - взять достаточно большой простой делитель числа , тогда с большой вероятностью
Так как существует ровно различных степеней 10 по модулю , и сумма любых из них "покроет" не более вычетов по модулю . Поэтому, если , то становится вероятно, что 0 не покроется, а то есть .

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

Эта действительно глупая гипотеза (об этом я давно уже догадался), так как очевидно .

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

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

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

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

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

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

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

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

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

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

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

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