How many numbers less than N have a prime sum of digits?

Question

I'm working on solving Project Euler's Problem 845. It's asking us to find the $10^{16}$-th positive integer number that has a prime sum of digits. Adopting a 'naive' solution, I compute the sum of digits, verify it's prime and increase a counter each time I find one. Obviously though, this won't get me very far. It takes my Python program a few minutes (5 or so) to correctly find the $10^8$-th number. No chance of ever getting to the $10^{16}$-th number though. Therefore, I'm looking for a smarter algorithm that can solve this problem without going through each and every number. Is there a way to compute sum of digits without breaking up the number in digits and summing, but base the result on the sum of digits of previous numbers? That's wwhat I'm trying now, but no progress. Any help would be greatly appreciated. Thank you!

Answer 1

Hint: use inclusion-exclusion to solve the problem of counting $k$-digit numbers that have digit sum $s$: $$x_1 + \cdots + x_k = s, \quad 0 \le x_i \le 9$$

Then search $n$ and do casework on values $\le n$, where $n$ is not necessarily a power of 10.

Actually, you can do a more expensive but simple dynamic programming solution too. Inclusion-exclusion for a given digit sum $s$ and number of digits $k$ can be computed in $O(k)$ time (assuming math operations like binomial are constant time and there are a fixed 10 possible digits), which is much better than a DP in $O(sk)$, if your values are absurdly large.