It was the ’90s. I was sitting in class in 8th grade, bored out of my gourd. I started fiddling with my calculator and found something weird. If you take a number, lets say 789654, and subtract the reverse (456987) and divide the result by nine you get an answer 36963 that is the same backwards or forwards. A numerical anagram, like radar. It struck me as weird that this little trick only worked for some numbers. Then the other day I posted my little find to the comments section of Reddit and found that I’d stumbled upon what are known as Lychrel numbers The discussion in response to my comment is below. A coder competition to calculate Lychrel numbers using Erlang breaks out. It’s possibly the geekiest, most interesting thing I’ve ever witnessed.
Along the same lines: take a natural number and add its reverse. After a few iterations, you get a palindromic number. For example:
* 7326 + 6237 = 13563
* 13563 + 36531 = 50094
* 50094 + 49005 = 99099 <--- A Palindrome
89 takes an unusually large 24 iterations (the most of any number under 10,000 that resolves into a palindrome) to reach the palindrome 8813200023188.
Numbers that do not form a palindrome through the process of reversing and adding their digits have been named "Lychrel numbers".
The first known number starting from 0 that does not apparently form a palindrome is a three digit number. And here we have again a mysterious number for which we not now if it is just incidental, or that there is some deeper mathematical reason why it is exactly this number. It is 196.
permalink parent reply
reply cancel
sblinn 1 point 4 hours ago*
I wrote some Python to do bits of lychrel computation recursively — it was a bad idea as eventually I reached:
RuntimeError: maximum recursion depth exceeded in cmp
Probably bad code, anyway:
import sys
def reverse_int(i):
return int(str(i)[::-1])
def is_palindrome(i):
s = str(i)
return s == s[::-1]
def lychrel(min,max,depth):
print_each_fail = 0
print_each_success = 1
num_lychrel = num_not_lychrel = 0
for i in xrange(min,max):
j = do_lychrel(i,depth)
if j == 0:
num_lychrel += 1
if print_each_success:
print "%d is lychrel at depth %d" % (i,depth)
else:
num_not_lychrel += 1
if print_each_fail:
print "%d is not lychrel at depth %d" % (i,j)
print "in the xrange %d to %d at depth %d there are %d lychrel and %d non-lychrel numbers" % (min,max,depth,num_lychrel,num_not_lychrel)
def do_lychrel(i,depth,j=1):
palindrome_i = reverse_int(i)
palindrome_sum = i + palindrome_i
if is_palindrome(palindrome_sum):
return j
elif (j+1) >= depth:
return 0
else:
return do_lychrel(palindrome_sum,depth,(j+1))
if __name__ == "__main__":
lychrel(int(sys.argv[1]),int(sys.argv[2]),int(sys.argv[3]))
It was easy enough to re-write the recursive part as a loop so it would actually run:
def do_lychrel(i,depth):
j = 1
while (j<=depth):
palindrome_i = reverse_int(i)
palindrome_sum = i + palindrome_i
if is_palindrome(palindrome_sum):
return j
i = palindrome_sum
j += 1
return 0
Results are things like:
# python lychrel.py 10 2000 2000
196 is lychrel at depth 2000
295 is lychrel at depth 2000
394 is lychrel at depth 2000
493 is lychrel at depth 2000
592 is lychrel at depth 2000
689 is lychrel at depth 2000
691 is lychrel at depth 2000
788 is lychrel at depth 2000
790 is lychrel at depth 2000
879 is lychrel at depth 2000
887 is lychrel at depth 2000
978 is lychrel at depth 2000
986 is lychrel at depth 2000
1495 is lychrel at depth 2000
1497 is lychrel at depth 2000
1585 is lychrel at depth 2000
1587 is lychrel at depth 2000
1675 is lychrel at depth 2000
1677 is lychrel at depth 2000
1765 is lychrel at depth 2000
1767 is lychrel at depth 2000
1855 is lychrel at depth 2000
1857 is lychrel at depth 2000
1945 is lychrel at depth 2000
1947 is lychrel at depth 2000
1997 is lychrel at depth 2000
in the xrange 10 to 2000 at depth 2000 there are 26 lychrel and 1964 non-lychrel numbers
Whee. It could probably be written much better with some reduce or whatever functional mumbo-jumbo. No matter what I tried, I couldn’t get the recursive version to be “properly” tail recursive without manually writing the loop.
permalink parent reply
reply cancel
BioGeek 1 point 3 hours ago*
sblinn, you seem to have enjoyed yourself with these Lychrel numbers :)
Now, with your code in hand, you should easily be able to solve question 55 at projecteuler.net:
How many Lychrel numbers are there below ten-thousand?
permalink parent reply
reply cancel
sblinn 1 point 3 hours ago*
Heh, it is not answerable without some proviso as to what I’m calling the Lychrel “depth”. I could answer “how many lychrel numbers are there at a depth of 200 below ten-thousand”:
$ python lychrel_loop.py 1 10000 200
in the xrange 1 to 10000 at depth 200 there are 249 lychrel and 9750 non-lychrel numbers
But nobody can say yet whether even 196 is “really” a Lychrel number or not, right?
permalink parent reply
reply cancel
sblinn 1 point 3 hours ago*
Some Erlang code for lychrel calculations (probably very, very bad code!):
$ cat lychrel.erl
-module(lychrel).
-export([is_lychrel/1]).
-export([is_lychrel/2]).
is_lychrel(N) -> is_lychrel(N,infinity).
is_lychrel(N,D) -> is_lychrel(N,D,1).
%% if we've reached iteration such that we've exceeded depth, it is a lychrel number at depth:
is_lychrel(_N,D,I) when I >= D -> true;
%% main guts
is_lychrel(N,D,I) ->
Nrev = reverse_int(N),
Nsum = N + Nrev,
Bpal = is_palindrome(Nsum),
if
Bpal -> false;
true -> is_lychrel(Nsum,D,I+1)
end.
reverse_int(N) ->
list_to_integer(lists:reverse(integer_to_list(N))).
is_palindrome(N) ->
N == reverse_int(N).
$ erlc lychrel.erl
$ erl
Erlang (BEAM) emulator version 5.5.2 [source] [async-threads:0] [hipe] [kernel-poll:false]
Eshell V5.5.2 (abort with ^G)
1> c(lychrel).
{ok,lychrel}
2> lychrel:is_lychrel(89,12).
true
3> lychrel:is_lychrel(89,24).
true
4> lychrel:is_lychrel(89,25).
false
5> lychrel:is_lychrel(8).
false
6> lychrel:is_lychrel(86).
false
7> lychrel:is_lychrel(89).
false
8> lychrel:is_lychrel(10911).
false
9> lychrel:is_lychrel(1186060307891929990).
false
10> lychrel:is_lychrel(196).
That last one won’t return — EVER — if the conjecture is true.
edit: little update that saves the resulting palindrome and iteration count:
%% main guts
is_lychrel(N,D,I) ->
Nrev = reverse_int(N),
Nsum = N + Nrev,
Bpal = is_palindrome(Nsum),
if
Bpal -> {false,I,Nsum};
true -> is_lychrel(Nsum,D,I+1)
end.
erl:
2> lychrel:is_lychrel(196,2000).
true
3> lychrel:is_lychrel(10911).
{false,55,4668731596684224866951378664}
4> lychrel:is_lychrel(1186060307891929990).
{false,261,
44562665878976437622437848976653870388884783662598425855963436955852489526638748888307835667984873422673467987856626544}
Any help making this properly tail-recursive would be awesome.
permalink parent reply
reply cancel
degustideathstar 10 points 1 day ago
Dividing by nine (or, actually, dividing by n-1 in a base-n system) has some kind of funny properties. This is probably related to how the digits in multiples of nine add up to multiples of nine.
permalink parent reply
reply cancel
sblinn 6 points 9 hours ago*
Fun. I wrote a little python program to calculate it (called it lychrel9 as I have no idea what the proper term would be):
in the xrange 0 to 100 there are 100 lychrel9 palindromic and 0 lychrel9 non-palindromic numbers
in the xrange 0 to 1000 there are 1000 lychrel9 palindromic and 0 lychrel9 non-palindromic numbers
in the xrange 0 to 10000 there are 6745 lychrel9 palindromic and 3255 lychrel9 non-palindromic numbers
The lowest is 1011. Breaking it down by 1000s yields surprisingly uniform results:
in the xrange 1000 to 2000 there are 633 lychrel9 palindromic and 367 lychrel9 non-palindromic numbers
in the xrange 2000 to 3000 there are 639 lychrel9 palindromic and 361 lychrel9 non-palindromic numbers
in the xrange 3000 to 4000 there are 643 lychrel9 palindromic and 357 lychrel9 non-palindromic numbers
in the xrange 4000 to 5000 there are 645 lychrel9 palindromic and 355 lychrel9 non-palindromic numbers
in the xrange 5000 to 6000 there are 645 lychrel9 palindromic and 355 lychrel9 non-palindromic numbers
in the xrange 6000 to 7000 there are 643 lychrel9 palindromic and 357 lychrel9 non-palindromic numbers
in the xrange 7000 to 8000 there are 639 lychrel9 palindromic and 361 lychrel9 non-palindromic numbers
etc. Going for only slightly larger numbers seems to be about the same distribution:
in the xrange 10000 to 20000 there are 6350 lychrel9 palindromic and 3650 lychrel9 non-palindromic numbers
But once we get to 6-digit numbers, the majority do not fit:
in the xrange 100000 to 200000 there are 42415 lychrel9 palindromic and 57585 lychrel9 non-palindromic numbers
in the xrange 100000 to 1000000 there are 385252 lychrel9 palindromic and 514748 lychrel9 non-palindromic numbers
in the xrange 1000000 to 2000000 there are 424210 lychrel9 palindromic and 575790 lychrel9 non-palindromic numbers
etc.
The interesting bit to me is that all numbers minus their reverse are evenly divisible by 9. Also interesting (perhaps) is that the set of “lychrel9″ and “non-lychrel9″ numbers is expensively computable (and determinable — unlike a lychrel number which cannot be proven to be such a number one way or another) and are perhaps useful in algorithms.
permalink parent reply
reply cancel
sblinn 2 points 6 hours ago*
For the curious, the horrible awfulness that is my python code for it:
import sys
def reverse_int(i):
return int(str(i)[::-1])
def is_palindrome(i):
s = str(i)
return s == s[::-1]
def lychrel9(min,max):
print_each_fail = 0
print_each_success = 0
num_palindromic = num_not_palindromic = 0
for i in xrange(min,max):
j = abs(i - reverse_int(i))
k = j / 9
if is_palindrome(k):
num_palindromic += 1
if print_each_success:
print "%d is lychrel9 palindromic" % i
else:
num_not_palindromic += 1
if print_each_fail:
print "%d is not lychrel9 palindromic" % i
print "in the xrange %d to %d there are %d lychrel9 palindromic and %d lychrel9 non-palindromic numbers" % (min,max,num_palindromic,num_not_palindromic)
if __name__ == "__main__":
lychrel9(int(sys.argv[1]),int(sys.argv[2]))
permalink parent reply
reply cancel
sblinn 2 points 6 hours ago*
Neat, another palindrome curiousity, this time with primes:
http://primes.utm.edu/curios/page.php/229.html
The smallest prime that remains prime when added to its reverse.
Replacing each digit of prime 229 with its square, respectively its cube, results in two new primes: 4481 and 88729, with a palindromic difference of 84248. Coincidentally, 229 + 4481 + 88729 is palindromic as well.
And there’s a cipher paper out there using palindromic differences (PDF):
http://csrc.nist.gov/pki/HashWorkshop/2006/UnacceptedPapers/MACHADO_caligo.pdf
While working on HoundWire I would often go to Park Bench Deli (a few blocks up the hill from where that photo was taken) in Altadena with various interesting people. One fellow diner was our intern from Caltech. Caltech is the west coast rival of MIT so they have some very smart professors wandering the halls. One out of every thousand alumni has received the Nobel Prize. The point is that the professors there know a little bit about what they teach. 
Today I worked on a roof. I was sitting there clacking away at my laptop, configuring a router, and looked up. It’s very peaceful up there. 
The Geico Cavemen visited me this Halloween. It made my day. 
