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

[maxal]

Свежие находки:
A173443(13) $\leqslant 3000811,$
A173443(16) $\leqslant 5165039,$
A173443(20) $\leqslant 12344321,$
A173443(21) $= 243309,$
A173443(24) $\leqslant 33333333.$

[maxal]

Для 13, 16 и 20 указанные оценки оказались точными значениями:

A173443(13) = 3000811,
A173443(16) = 5165039.
A173443(20) = 12344321.

[AlexandreII]

Ответ: для простого $p$ $10^{p-1} = 1 \mod p$ (малая теорема Ферма)
Поэтому $10^{(p-1)/2} = -1 \mod p$.

$10^{(p-1)/2} + 1 = 0\mod p$.
Т.е. число из двух единиц и многих нулей, делящееся на $p$, это $10^{(p-1)/2}+1$.
Для p=17 это $10^8+1$.

[Руст]

$10^{(p-1)/2}=(\frac{10}{p})\mod p$ не обязательно -1.

[AlexandreII]

$10^{(p-1)/2} = x \mod p$
$x^2 = 10^{p-1}=1 \mod p$
т.е. $x = 1$ или $x=-1 \mod p$.

$10^{(p-1)/2}=1 \mod p$ в двух случаях:
1. $10 = 1 \mod p$, отсюда p = 3
2. $(p-1)/2 = p-1$, отсюда p = 1
Согласен, в совсем общем случае мое утверждение неверно, но в рамках задачи - вполне.

-- Вс ноя 28, 2010 18:41:39 --

Кстати, отсюда для числа, делящегося на три, минимальная сумма цифр равна 3, а не 2, как для других простых

-- Вс ноя 28, 2010 18:42:49 --

по mod 5, да, $10^{n} = 0$, для других простых вроде верно

-- Вс ноя 28, 2010 18:44:38 --

В общем, важно, чтобы
1. $10 \ne 1 \mod p$
2. $10 \ne 0 \mod p$

Простые p, которые удовлетворяют данному условию - это все, кроме 2, 3, 5

-- Вс ноя 28, 2010 18:50:54 --

Вот полный ответ:
1. мин. сумма цифр числа, которое делится на 2, равна 1: например 10
2. мин. сумма цифр числа, которое делится на 3, равна 3: например 3
3. мин. сумма цифр числа, которое делится на 5, равна 1: например 10
4. для остальных простых p мин. сумма цифр числа, которое делится на p, равна 2: например $10^{(p-1)/2}+1$

[maxal]

AlexandreII в сообщении #381434 писал(а):

4. для остальных простых p мин. сумма цифр числа, которое делится на p, равна 2: например $10^{(p-1)/2}+1$

Это неверно. Контрпример: $p=31$, для которого A077196(31)=3.