Дано натуральное число N <= 10^9. Вычислите количество чисел от 1 до N, у которых сумма цифр такая же, как и у числа N. Например, есть число 790, сумма его цифр равна 16. Начал с того, что нашел минимальное как 16 mod(9) = 7, а дальше идет количество 9-ок, равное целой части от деления 16/9 = 1.7777, т.е. получаем 79. Вот в этом моменте я и застрял, если идти перебором то получаем последовательность 79, 88 ... 781 790, но в какой-то момент мы получаем числа 105, 114 и т.д., которые не попадают под критерий суммы цифр 16. Можно ли как-то вычислить нужное количество?

задан 1 Авг '21 23:19

изменен 2 Авг '21 0:25

10|600 символов нужно символов осталось
1

Пусть число $%N$% состоит из $%d$% цифр: $%N=\overline{n_1n_2\dots n_d}$% с суммой $%s=n_1+\dots+n_d$%. Понятно, что число с суммой цифр $%s$% не превосходящее $%N$% - это по сути композиция суммы $%s$% в $%d$% цифр не превышающих 9. Обозначим количество таких композиций через $%q_9(s,d)$%. Однако, не всякая такая композиция даёт число, не превосходящее $%N$%. Если точнее, то количество требуемых чисел дается формулой: $$ 1 + \sum_{u=0}^{d-1} \sum_{m=0}^{n_{u+1}-1} q_9(s-n_1-\dots-n_u-m,d-u-1), $$ где $%u$% обозначает количество начальных цифр числа совпадающих с начальными цифрами $%N$%, а начальная единица учитывает само $%N$%.

Остается вывести формулу для $%q_9(s,d)$%, что проще всего сделать, заметив, что это коэффициент при $%x^s$% в $$(1+x+x^2+\dots+x^9)^d = (1-x^{10})^d(1-x)^{-d}.$$ Откуда: $$q_9(s,d) = \sum_{k=0}^{\lfloor s/10\rfloor} (-1)^{k+s}\binom{d}{k} \binom{-d}{s-10k}.$$

P.S. Вот примерная реализация этой формулы на Sage, которая вычисляет искомое количество для случайного числа.

Эти количества также присутствуют в OEIS как последовательность A254524.

ссылка

отвечен 15 Май 5:27

изменен 15 Май 5:31

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,934
×1,545

задан
1 Авг '21 23:19

показан
403 раза

обновлен
15 Май 5:31

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru