Trying to script a program that lists numbers whose digits add up to a prime in Python. How would I be able to fix an overflow error?

Question

def isPrime(num):
    s=0
    for j in range (1, num):
        if(num%j==0):
            s=s+1
            if(s>1):
                break
    return(s)

a = 10**20;
b = 10**400;
for i in xrange(a, b):
        if(isPrime(i)==1 and isPrime(sum(int(x) for x in str(i)))==1):
            print('Sum of all digits of', i, 'is', sum(int(x) for x in str(i)))

My objective is to output all the numbers within 10^20 and 10^400 whose digits add up to a prime number in order to answer the question, "How many integers in the range [10^20, 10^400] exist such that the sum of their digits is a prime number?"

While googling around, I read that range would overflow and that xrange would be more efficient. When xrange was used, the error "OverflowError: Python int too large to convert to C long;" occurs.

How can I output the answer without error?

You'll need to find another way to do it, or buy yourself some eternity... — Thierry Lathuille, May 20 '17 at 19:27
You will need some serious amount of ram here,and not a algorithm as simple as this one — Stavros Avramidis, May 20 '17 at 19:31
You need to look more at permutation and combinations. You are not interested in the order of digits, just in the sum of the digits. A 10^20 size number will have 20 digits. Treat them as set of lists of individual digits: (0, 0, 0, ... 0, 0) to (9, 9, 9, ... 9, 9). Once you have a list which adds up to a prime then work out how many permutations of that list there are. — rossum, May 24 '17 at 14:10

score 1 · Accepted Answer · edited May 23 '17 at 12:18

A question was asked similar to this for python 2.x it seems: Handling big numbers in code this may help for smaller numbers...

In general, this answer via Quora is quite informative: https://www.quora.com/How-large-can-Python-handle-big-number like others have said, it will depend on how much memory you have available.

From the Quora article:

The real limit depends on the amount of memory Python has access to. If it had, say, 1GB at its disposal, that would amount to approximately 80000000008000000000 bits. That would, therefore, let you have numbers all the way up to 2800000000028000000000. If somehow we could use the Titan supercomputer’s 600+ TiB of CPU memory specifically for making numbers, we could go all the way up to about 22522252. That's a lot.

Trying to script a program that lists numbers whose digits add up to a prime in Python. How would I be able to fix an overflow error?

1 Answers1