Euler Solution 55

From ProgSoc Wiki

Jump to: navigation, search

Contents

Solutions for Problem 55

How many (candidate) Lychrel numbers are there below ten-thousand? For the purpose of this problem, a number shall be considered to be Lychrel if a palindrome cannot be produced after 50 iterations.

Ruby by tomchristmas

Runtime: 356ms. Wow. Didn't expect it to run this fast. Even more remarkable: I wrote this piece of code in five minutes, in one go (stealing from my problem 36) and it found the answer on the first execution!

def is_palindrome?(str)
    str.slice!(str.length/2) if str.length % 2 == 1
    return (str[0..((str.length/2) - 1)] == str[(str.length/2)..(str.length - 1)].reverse)
end

lychrel = 0

1.upto(9999){|x|
  c = 0
  pal = false

  xx = x
  while c < 50 && !pal 
        xx += xx.to_s.reverse.to_i
        pal = true if is_palindrome?(xx.to_s)
        c += 1        
  end

  if !pal
    lychrel += 1 
    puts x
  end
}

puts "Number of candidate Lychrels below 10000: #{lychrel}"

Well, since my implementation is so "pants-droppingly fast", why not have a go at increasing the number of iterations to see if you can obtain fewer Lychrel candidates. I cranked it up to 1000 iterations (runtime: 40.910s) and I *still* get the same number of Lychrels! Then I tried 10000 iterations and 201 minutes and 37.803 seconds later....I *still* get the same number of Lychrels! Who's game enough to try a million? :P

Python by Althalus

Runtime: 280ms

def flip(n):
 return int(str(n)[::-1])

def isPalindrome(number):
 if str(number) == str(number)[::-1]: return True
 return False

def isLychrel(n):
 count=0
 while count < 50:
  n += flip(n)
  if isPalindrome(n):
   return False
  count+=1
 return True
 
lychrels = 0
for i in xrange(1,10000):
 if isLychrel(i): lychrels+=1

print lychrels

Haskell by SanguineV

Runtime: 137.275 ms

{- Reverse an integer -}
rev :: Integer -> Integer
rev n = inner 0 n
  where
    inner :: Integer -> Integer -> Integer
    inner ac i | i < 10 = 10 * ac + i
    inner ac i = inner (10 * ac + (mod i 10)) (div i 10)

{- Determine if a number is lychrel (up to 50 iterations) -}
lychrel :: Integer -> Bool
lychrel x = not (inner 49 (rev x + x))
  where
    inner :: Integer -> Integer -> Bool
    inner 1 _ = False
    inner it m = m == rm || inner (it - 1) (m + rm)
      where
        rm = rev m

{- Find the number of lychrel numbers below 10000 -}
main = print (length (filter lychrel [1..9999]))
Personal tools