CODEWITHSUNDEEP
algorithm
frodo
frodo

Reputation: 1571

Finding numbers whose digits sum to a prime

I was trying to solve this problem on SPOJ, in which I have to find how many numbers are there in a range whose digits sum up to a prime. This range can be very big, (upper bound of 10^8 is given). The naive solution timed out, I just looped over the entire range and checked the required condition. I cant seem find a pattern or a formula too. Could someone please give a direction to proceed in??

Thanks in advance...

Upvotes: 4

Views: 4326

Answers (3)

High Performance Mark
High Performance Mark

Reputation: 78344

I (seriously) doubt whether this 'opposite' approach will be any faster than @izomorphius's suggestion, but it might prompt some thoughts about improving the performance of your program:

1) Get the list of primes in the range 2..71 (you can omit 1 and 72 from any consideration since neither is prime).

2) Enumerate the integer partitions of each of the prime numbers in the list. Here's some Python code. You'd want to modify this so as not to generate partitions which were invalid, such as those containing numbers larger than 9.

3) For each of those partitions, pad out with 0s to make a set of 8 digits, then enumerate all the permutations of the padded set.

Now you have the list of numbers you require.

Upvotes: 1

Yuriy Faktorovich
Yuriy Faktorovich

Reputation: 68707

Generate the primes using the sieve of Eratosthenes up to the maximum sum (9 + 9...). Put them in a Hash table. Then you could likely loop quickly through 10^8 numbers and add up their sums. There might be more efficient methods, but this should be quick enough.

Upvotes: 0

Ivaylo Strandjev
Ivaylo Strandjev

Reputation: 70989

Here are some tips:

  • try to write a function that finds how many numbers in a given range have a given sum of the digits. Easiest way to implement this is to write a function that returns the number of numbers with a given sum of digits up to a given value a(call this 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)
  • Pay attention that the sum of the digits itself will not be too high - up to 8 * 9 < 100 so the number of prime sums to check is really small

Hope this helps.

Upvotes: 5

Related Questions