# 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
```

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]))
```