|
Дано натуральное число 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 
Alexchek |
|
Пусть число $%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 Май '22 5:27 
maxal |