3
\$\begingroup\$

Many numbers can be expressed as the sum of a square and a cube. Some of them in more than one way.

Consider the palindromic numbers that can be expressed as the sum of a square and a cube, both greater than 1, in exactly 4 different ways. For example, 5229225 is a palindromic number and it can be expressed in exactly 4 different ways:

22852 + 203

22232 + 663

18102 + 1253

11972 + 1563

Find the sum of the five smallest such palindromic numbers.

I used brute force; it solves in around 11 seconds. I thought about it for some time but couldn't come up with any obvious optimizations, the problem seems built for brute force. Any suggestions?

Note that I'm using PyPy which makes math code run much faster...

"""Find the sum of the five smallest palindromic numbers
that can be expressed as the sum of a square and a cube."""

from math import log10
from collections import Counter
from timeit import default_timer as timer

def is_palindrome(n):
    length = int(log10(n))
    while length > 0:
        right = n % 10
        left = n / 10**length
        if right != left:
            return False
        n %= 10**length
        n /=10
        length -= 2
    return True

start = timer()
palindromes = Counter()

for square in xrange(1, 30000):
    squared = square**2
    for cube in xrange(1, 3000):
        cubed = cube**3
        total = squared + cubed
        if is_palindrome(total): palindromes[total] += 1

ans = sum(x[0] for x in palindromes.most_common(5))
elapsed_time = timer() - start
print "Found %d in %d s." % (ans, elapsed_time)
\$\endgroup\$
1

1 Answer 1

1
\$\begingroup\$

@Kevin Brown is correct, your programme runs in 18 seconds on my PC, if I write:

def is_palindrome(n):
    return str(n) == str(n)[::-1]

it takes only 16 seconds.

\$\endgroup\$
1
  • \$\begingroup\$ You using PyPy? On my computer it runs in around 20s with that version. \$\endgroup\$
    – Joshua
    Jun 21, 2015 at 12:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.