Last night I discovered another cool mathematical concept akin to the Collatz conjecture - Lychrel numbers.

Image via Wikipedia

The idea of a lychrel number is pretty straightforward: Take a number, add its reverse, continue until you reach a palindrome number. If you never reach a palindrome, then this is a Lychrel number.

Something like this:

349 + 943 = 1292,
1292 + 2921 = 4213
4213 + 3124 = 7337
not lychrel

If you’ve ever done any theoretical computer science, you’ll immediately spot a problem. This isn’t a very good algorithm. Problem is with that “never” word in the description – an algorithm is a finite set of steps, when you need an infinite amount of steps to reach a conclusion that’s … not very useful.

Honestly I am not certain what class of problems lychrel numbers fall into. The “not a lychrel number” is a half-decidable problem. It will always tell you when a number is not lychrel but it will never terminate when it is. If my understanding is correct, this would make “is a lychrel number” an non-decidable problem.

Project Euler is kind enough to limit the problem a little bit and make it a fun algorithm to write before bed when your brain is half dead. Find all lychrel candidates under 10,000 assuming it should never take more than 50 iterations.

Solving that problem becomes rather trivial in Haskell:

 
reverse' = read . reverse . show
 
palindrome n = n == reverse' n
 
-- max denotes max recursion depth
lychrel n max
  | max <= 0 = True
  | palindrome$n+r = False
  | otherwise = lychrel (n+r) (max-1)
    where r = reverse' n
 
lychrels max =
  length [x | x <- [1..max], lychrel x 50]

Oh and actually the first number that needs more than 50 iterations to converge into a palindrome is 10677, so the problem is pretty safely stated.

For a final bit of fun, the number 4994, itself a palindrome, is a lychrel candidate.

Related articles

• Collatz, Haskell and Memoization (swizec.com)
• All numbers lead to one (flowingdata.com)
• Rare Date: Today Is Once-in-10,000-Years Palindrome (livescience.com)
• problematic views, futuring maths. (mathsetc.wordpress.com)
• Why 11/11/11 is mathematically amazing (msnbc.msn.com)

---
Need a freelance developer? Email me!

You should follow me on twitter
Follow @Swizec  Subscribe to RSS