palindromes of sums less than 30, help to optimize my code

Question

On my way of studying Python i stacked on the problem:

I have to count all numbers from 0 to 130000 which are palindromes, but they should be palindromes after sum of the number and its reversed version. For example:
i = 93
93 + 39 = 132
132 + 231 = 363
count_of_palindromes should count all i which are palindromes after 1 or more iterations of summing, but less than 50.
I've already written the code but it's too way difficult to run on my PC, Python stops responding :(

Any advices how to optimize my code?

        count_of_palindromes = 0
        for i in range(0,130000):
            trying = 0
            if (i == int(str(i)[::-1])) != True:
                trying += 1
                sum = i + int(str(i)[::-1])
                while trying <= 50:
                    while (sum == int(str(sum)[::-1])) != True:
                        trying += 1
                        sum += int(str(sum)[::-1])                
                    if trying > 0 and trying <= 50:
                        count_of_palindromes += 1
                        break
        print(count_of_palindromes)

Thank you very much!

score 0 · Answer 1 · edited May 23 '17 at 12:15

0

This solution has a lot of conversions so it may not be the best solution but regardless it is a solution. have a look at this post he has a seemingly much better method of reversing integers without conversion https://stackoverflow.com/a/3806212/1642546

If you combine my code and that posts code. you probably will have a faster solution, but you must benchmark it to see.

token = 0
for x in range(130000):
   reversed = str(x)[::-1]
   original = str(x)
   sum = int(reversed) + int(original)
   if str(sum) == str(sum)[::-1]:
      token+=1
print(token)

edited May 23 '17 at 12:15

Community

1
1

answered Sep 11 '16 at 16:41

themidnightoil

13
7

The question actually was not how to reverse a number but how to easier and faster loop to calculate the sums.. – Valery Danilik Sep 11 '16 at 17:00
EXACTLY.I added an extra line in my original post to clarify. My solution is simpler and probably is faster, but what I am saying is he can do better if he avoids conversion. – themidnightoil Sep 11 '16 at 17:38

score 0 · Answer 2 · answered Sep 11 '16 at 17:31

I had an error in the code, that made the program almost ifinite :)
The correct code (in my opinion is below)

count_of_palindromes = 0
for i in range(12814):
    if (i == int(str(i)[::-1])) != True:
        trying = 1
        sum = i + int(str(i)[::-1])
        while trying <= 50:
            while (sum == int(str(sum)[::-1])) != True and trying <=50:
                trying += 1
                sum += int(str(sum)[::-1])                
            if trying > 0 and trying <= 50:
                count_of_palindromes += 1
                break
print(count_of_palindromes)

score 0 · Accepted Answer · answered Sep 11 '16 at 17:56

Let's tidy your code up a bit first for readability. We'll just take some of the syntax heavy string stuff and encapsulate it.

def reverse(n):
    return int(str(n)[::-1])

def is_palindrome(n):
    return n == reverse(n)

That's better. I think your problem is the second nested while loop. It runs until it finds a palindrome, then checks if it found it in the first fifty tries. You want it to run up to fifty times, then give up. I think the best way would be a second for loop

count_of_palindromes = 0
for i in range(130000):
    for tries in range(50):
        if(is_palindrome(i)):
            counter += 1
            break
        else:
            i = i + reverse(i)
print(count_of_palindromes)

There are some more ways of speeding this up by avoiding string operations and replacing them with math, but that's overkill for this. I was a little unclear on how your problem wants you to treat natural palindromes, so you may need to modify this solution

palindromes of sums less than 30, help to optimize my code

3 Answers3