Search for numbers whose digits are summed up to a simple

Question

I tried to solve this problem on SPOJ, in which I have to find the number of numbers in a range whose numbers are summed up to a simple one. This range can be very large (given an upper bound of 10 ^ 8). The naive decision was timed, I just went in cycles on the whole range and checked the required condition. I can not find a template or formula. Can someone please give directions to continue?

Thanks in advance...

Answer 1

Here are some suggestions:

• try writing a function that determines how many numbers in a given range have a given sum of digits. The easiest way to implement this is to write a function that returns the number of numbers with a given sum of digits to a given value a (let's call it f (sum, a)), and then the number of such numbers in the range a to b will be f (sum, b) - f (sum, a - 1)
• Please note that the sum of the numbers themselves will not be too high - up to 8 * 9 <100, so the number of simple amounts to check is really small.

Hope this helps.

Answer 2

I (seriously) doubt whether this “opposite” approach will be faster than the @izomorphius suggestion, but may give rise to some thoughts about improving the performance of your program:

1) Get a list of primes in the range 2..71 (you can omit 1 and 72 for any reason, since none is prime).

2) List the whole sections of each of the prime numbers in the list. Here is some Python code . You want to change this so as not to generate invalid partitions, such as numbers with numbers greater than 9.

3) For each of these sections, lay out with 0s to make a set of 8 digits, then list all the permutations of the filled set.

Now you have a list of the numbers you need.

Answer 3

Generate primes using a sieve of Eratosthenes to the maximum amount (9 + 9 ...). Put them in a hash table. Then you will most likely be able to quickly go through 10 ^ 8 numbers and add your amounts. There may be more effective methods, but it should be fast enough.