title: Python: efficient way to find palindrome numbers that are sums of consecutive squares
body: <p>This is a problem from <a href="https://www.codewars.com/kata/palindrome-integer-composition" rel="nofollow noreferrer">codewars</a>. </p>
  
  <p>Given an integer N, write a function <em>values</em> that finds how many numbers in the interval (1,...,N) are palindromes and can be expressed as a sum of consecutive squares. </p>
  
  <p>For example, <em>values(100)</em> will return 3. In fact, the numbers smaller than 100 that have the above property are: </p>
  
  <ul>
  <li>5 = 1+4, </li>
  <li>55 = 1+4+9+16+25</li>
  <li>77 = 16+25+36</li>
  </ul>
  
  <p>Palindromes that are perfect squares such as 4, 9, 121, etc do not count. Tests are up to N=10^7.</p>
  
  <p>I can solve the problem and pass all the test cases, but I cannot meet the efficiency requirements (the process is killed after 12s).</p>
  
  <p>Am I simply missing some key observation, or there is something wrong with the efficiency of my code below? I broke it down a bit for better readability.</p>
  
  <pre><code>from numpy import cumsum
  
  def is_palindrome(n):
      return str(n) == str(n)[::-1]
  
  def values(n):
  
      limit = int(n**0.5) # could be improved
      pals = []
  
      for i in range(1,limit):
          # take numbers in the cumsum that are palindromes &lt; n
          sums = [p for p in cumsum([i**2 for i in range(i,limit)]) if p&lt;n and is_palindrome(p)]
          # remove perfect-squares and those already counted
          pals.extend(k for k in sums if not (k in pals) and not (k**0.5).is_integer())
  
      return len(pals)
  </code></pre>
  
  <p>Note: I'm aware that checking that a number is a perfect square using sqrt(n).is_integer() might not be perfect but should be enough for this case.</p>