[Tutor] OverflowError in lucky numbers script, was Re: Tutor Digest, Vol 95, Issue 55

[Peter Otten]

Shreesh bhat wrote:

> *Lucky Numbers*
> A number is called lucky if the sum of its digits, as well as the sum of
> the squares of its digits is a prime number. How many numbers between A
> and B are lucky?
> Input:
> The first line contains the number of test cases T. Each of the next T
> lines contains two integers, A and B.
> Output:
> Output T lines, one for each case containing the required answer for the
> corresponding case.
> 
> Constraints:
> 1 <= T <= 10000
> 1 <= A <= B <= 10^18
> Sample Input:
> 2
> 1 20
> 120 130
> Sample Output:
> 4
> 1
> Explanation:
> For the first case, the lucky numbers are 11, 12, 14, 16.
> For the second case, the only lucky number is 120.
> 
> 
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
> My solution:
> 
> def isprime(n):
>   n=abs(int(n))
>   if n<2:
>     return False
>   if n==2:
>     return True
>   if not n & 1:
>     return False
>   for x in range(3,int(n**0.5)+1,2):
>     if n % x == 0:
>       return False
>   return True
> 
> def islucky(n):
>   sum1=0
>   sum2=0
>   while n!=0:
>     r=n%10
>     sum1+=r
>     sum2+=r*r
>     n=n/10

>   if isprime(sum1) & isprime(sum2):
>     return True
>   return False

Don't use '&' here, you're not bit-twiddling and the idiomatic code is

return isprime(sum1) and isprime(sum2)

which also has the advantage that it "short-ciruit"s, i. e. isprime(sum2) is 
only evaluated if isprime(sum1) is true.
 
> number=raw_input()
> 
> 
> for i in range(int(number)):
>     inp=raw_input()
>     a=inp.split()
>     startnum=int(a[0])
>     endnum=int(a[1])
>     li=map(islucky,xrange(startnum, endnum))
>     count=0
>     for j in li:
>         if j:
>             count+=1
>     print count
> 
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
> 
> Traceback (most recent call last): File
> "/run-1327085301-1965755690/solution.py",
>  line 35, in li=map(islucky,xrange(startnum, endnum))
> OverflowError: Python int too large to convert to C long
> 
> 
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
> It shows this error for very large numbers or slows down with large
> numbers. I m using Ubuntu 32-bit.

The arguments of xrange() are limited to C integers, they cannot be larger 
than sys.maxint (2**31-1 on a 32-bit system or 2**63-1 on a 64-bit system). 
range() can handle larger numbers, but you'll always see a slowdown -- 
larger numbers have more digits and (on average) larger sums, and thus take 
longer to test.