Euler Solution 125

From ProgSoc Wiki

(Difference between revisions)
Jump to: navigation, search
(Solutions for Problem 125)
 
Line 35: Line 35:
  {- Find the sum of all palindromes created by the sum of consecutive squares -}
  {- 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..]))))))
  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)
[[Category: Euler]]
[[Category: Euler]]

Latest revision as of 02:10, 22 July 2011

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