Dynamic programming - save calculating times

Question

I had an overflow error with this program here!, I realized the mistake of that program. I cannot use range or xrange when it came to really long integers. I tried running the program in Python 3 and it works. My code works but then responds after several times. Hence in order to optimize my code, I started thinking of strategies for the optimizing the code.

My problem statement is 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?.

I started with this:

squarelist=[0,1,4,9,16,25,36,49,64,81]

def isEven(self, n):
   return
def isPrime(n):
   return

def main():
    t=long(raw_input().rstrip())
    count = []
    for i in xrange(t):
            counts = 0
            a,b = raw_input().rstrip().split()
            if a=='1':
                    a='2'
    tempa, tempb= map(int, a), map(int,b)
    for i in range(len(b),a,-1):
       tempsum[i]+=squarelist[tempb[i]]

What I am trying to achieve is since I know the series is ordered, only the last number changes. I can save the sum of squares of the earlier numbers in the list and just keep changing the last number. This does not calculate the sum everytime and check if the sum of squares is prime. I am unable to fix the sum to some value and then keep changing the last number.How to go forward from here?

My sample inputs are provided below.

87517 52088
72232 13553
19219 17901
39863 30628
94978 75750
79208 13282
77561 61794

finding the sum of squares is not going to be computationally intensive. Checkin if it is prime is going to be. You could try memoization there instead. — Access Denied
@AccessDenied, I tried optimization with memoization. Recursion fails due to the fact that recursion limit is set to 999. Memoization works but even with memoization, I am going to be using a lot of memory. Also, Just for one single computation, for the first input value in 87517 52088,my machine ran for 17 s. Now, for the code that I am writing, I have 100-1000 such value. So you can imagine.! Even accessing stored tems takes quite a bit of time from my experience. — user2459905
Why would it take more time ? can u share wht exactly u memoized and how you did it ? Have u tried a map DS to store the prime nos found ? Also the idea of storing till last but 1 term wont work cause for every 10 numbers one more number is also going to change. — Access Denied

Christian Schramm Christian Schramm · Accepted Answer · 2013-09-02T20:46:13

I didn't get what you want to achieve with your code at all. This is my solution to the question as I understand it: For all natural numbers n in a range X so that a < X < b for some natural numbers a, b with a < b, how many numbers n have the property that the sum of its digits and the sum of the square of its digits in decimal writing are both prime?

def sum_digits(n):
    s = 0
    while n:
        s += n % 10
        n /= 10
    return s

def sum_digits_squared(n):
    s = 0
    while n:
        s += (n % 10) ** 2
        n /= 10
    return s

def is_prime(n):
    return all(n % i for i in xrange(2, n))

def is_lucky(n):
    return is_prime(sum_digits(n)) and is_prime(sum_digits_squared(n))

def all_lucky_numbers(a, b):
    return [n for n in xrange(a, b) if is_lucky(n)]

if __name__ == "__main__":
    sample_inputs = ((87517, 52088),
                     (72232, 13553),
                     (19219, 17901),
                     (39863, 30628),
                     (94978, 75750),
                     (79208, 13282),
                     (77561, 61794))

    for b, a in sample_inputs:
        lucky_number_count = len(all_lucky_numbers(a, b))
        print("There are {} lucky numbers between {} and {}").format(lucky_number_count, a, b)

A few notes:

The is_prime is the most naive implementation possible. It's still totally fast enough for the sample input. There are many better implementations possible (and just one google away). The most obvious improvement would be skipping every even number except for 2. That alone would cut calculation time in half.
In Python 3 (and I really recommend using it), remember to use //= to force the result of the division to be an integer, and use range instead of xrange. Also, an easy way to speed up is_prime is Python 3's @functools.lru_cache.
If you want to save some lines, calculate the sum of digits by casting them to str and back to int like that:
```
def sum_digits(n):
    return sum(int(d) for d in str(a))
```
It's not as mathy, though.

Dynamic programming - save calculating times

1 Answers