def number_of_niven_numbers(digits): """ - Count the number of Niven numbers less than or equal to 10^digits. """ N = digits ret = 0 cnts = [0] * (digits + 1) for digit_sum in range(1, N * 9 + 1): curr = [[0] * digit_sum] curr[0][0] = 1 next_mods = [0] * digit_sum for i in range(digit_sum): next_mods[i] = 10 * i % digit_sum for left_digits in range(N): left_sum_max = min(9 * left_digits, digit_sum) next = [[0] * digit_sum for _ in range(min(left_sum_max + 9, digit_sum) + 1)] for left_sum in range(left_sum_max + 1): for left_mod in range(digit_sum): cnt = curr[left_sum][left_mod] if cnt == 0: continue next_mod_base = next_mods[left_mod] for next_digit in range(min(min(digit_sum, 9), digit_sum - left_sum) + 1): next_sum = left_sum + next_digit next_mod = next_mod_base + next_digit if next_mod >= digit_sum: next_mod -= digit_sum next[next_sum][next_mod] += cnt curr = next if digit_sum < len(curr): cnts[left_digits + 1] += curr[digit_sum][0] return cnts[N] + 1