// you’re reading...
1 Star2 Stars3 Stars4 Stars5 Stars (12 votes, average: 5.00 out of 5)
Loading...Loading...

Project Euler Solutions

Project Euler 125 Solution

Project Euler 125 Solution

Project Euler 125: Finding square sums that are palindromic


Problem Description

The palindromic number 595 is interesting because it can be written as the sum of consecutive squares: 62 + 72 + 82 + 92 + 102 + 112 + 122.

There are exactly eleven palindromes below one-thousand that can be written as consecutive square sums, and the sum of these palindromes is 4164. Note that 1 = 02 + 12 has not been included as this problem is concerned with the squares of positive integers.

Find the sum of all the numbers less than 108 that are both palindromic and can be written as the sum of consecutive squares.

Analysis

We add sequences of consecutive squares and record those that are uniquely palindromic. Once the sum has exceeded our limit, L, we can break from the current sequence’s starting number and start with the next. We use a set to eliminate duplicate sum-of-squares.

One may believe that utilizing the formula from Problem 6 (See also, Project Euler 6 Solution: Find the difference between the sum of the squares and the square of the sum.) to calculate the sum of squares from 1 to n may yield a faster solution. But simply calculating (and recalculating) sections of the series is much faster and more obvious.

\sum\limits_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6}

It is unusual for a brute force solution, such as this one, to perform so well when compared to other more efficient, but often less intuitive, methods which typically include arcane calculations or clever array calisthenics. I have yet to see a Python solution that is faster and more concise than the one presented here.

When code is written with a focused intention and a concise pragma, the result is always clear and understandable code.

Project Euler 125 Gingerbread Man PatternI seldom find clever ways to find patterns of this nature, which could be completely random, without first looking at the big picture. Computers are good at doing this on a very large scale.

As an analogy, the picture at the right could possibly have a pattern or some logical scenario in context. But looking at the picture on a too small scale may obscure those observations from view. It’s only when we expand our visual perspective that a pattern may reveal itself.

Of course, if it doesn’t reveal itself we may always be tempted to discount a random pattern and keep expanding and searching until a pattern is perceived. This may imprison our thinking to a lifelong quest for order out of chaos where none exists, or exists merely by coincidence.

In summary, stick with brute force for these kind of discrete problems because that’s how the universe would handle it. Well, it actually keeps replacing one brute force for another until it evolves into an optimum solution. But that’s a story for another time.

Project Euler 125 Solution

Runs < 0.200 seconds in Python 2.7.
from Euler import is_palindromic

def pe125(L):
   pal = set()
   sqrt_L = int(L ** 0.5)
   for i in xrange(1, sqrt_L):
      sos = i*i
      while sos < L:
         i += 1
         sos += i*i
         if is_palindromic(sos): 
            pal.add(sos)
   return sum(pal)

print "PE125: Sum of unique palindromes:", pe125(10**8)
Use this link to get the Project Euler 125 Solution Python 2.7 source.

Answer

Slowly swipe from either end beginning with the white vertical bar to get an idea of the starting or ending digits. For less drama, just double click the answer area. The distance between the two bars will give you an idea of the magnitude. Touch devices can tap and hold the center of the box between the two bars and choose define to reveal the answer.
|2906969179|

Comments

Project Euler 125 Solution last updated

Discussion

No comments yet.

Post a comment