Euler Solution 125

From ProgSoc Wiki

Jump to: navigation, search

Solutions for Problem 125

Find the sum of all the numbers below 108 that are the sum of consencutive squares of positive integers and are also palindromes.

Haskell by SanguineV

Runtime: 4.037 seconds

import Data.List

{- Reverse an integer, or return -1 if it would have a leading zero. -}
rev :: Integer -> Integer
rev n | mod n 10 == 0 = -1
rev n = inner n 0
  where
    inner :: Integer -> Integer -> Integer
    inner n' acc | n' < 10 = (acc * 10) + n'
    inner n' acc = inner (div n' 10) ((acc * 10) + (mod n' 10))

{- Return true if a number is a palindrome -}
pal :: Integer -> Bool
pal n = n == rev n
 
{- Generate numbers as the sum of (at leats 2) consecutive elements of a list
 - up to a limit -}
genLim :: Integer -> [Integer] -> [Integer]
genLim lim [] = []
genLim lim (x:xs) | x > lim = []
genLim lim (x:xs) = (inner x xs) ++ (genLim lim xs)
  where
    inner :: Integer -> [Integer] -> [Integer]
    inner n (z:zs) | n + z > lim = []
    inner n (z:zs) = [n + z] ++ (inner (n + z) zs)

{- Find the sum of all palindromes created by the sum of consecutive squares -}
main = print (sum (filter pal (uniq (sort (genLim 100000000 (map (\z -> z * z) [1..]))))))

Python by Althalus

Runtime: 1.2 seconds (1.7 without psyco)

import psyco
psyco.full()
def isPalindrome(number):
    number = str(number)
    for i in range (0,int(len(number)//2)):
        if number[i] != number[-(i+1)]:
            return False
    return True

goal = 10**8
# Get our squares
squares = map(lambda x: x*x, range(1,goal**0.5))

# prep some vars
x,results=0,{}
loop de loop
while x < len(squares)-2:
    res = squares[x]
    y = x+1
    while y < len(squares)-1:
        res += squares[y]
        if res > goal:
            break
        if isPalindrome(res):
            results[res] = 1
        y += 1
    x += 1
print "total",len(results)
print "sum",sum(results)
Personal tools