## Lychrel Numbers

### September 1, 2015

Let `r`(n) be the function that reverses the digits of the number n, and let `s`(n) = n + `r`(n); for instance, `r`(281) = 182 and `s`(281) = 281 + 182 = 463. Repeatedly applying `s` to the result of `s`(n) frequently leads to a palindrome; for instance, starting with n = 281, `s`(281) = 463, `s`(463) = 827, `s`(827) = 1555, `s`(1555) = 7106, `s`(7106) = 13123, and `s`(13123) = 45254, which is a palindrome. There are some numbers, such as 196, that apparently don’t lead to palindromes; these numbers are called Lychrel numbers (A023108), and we say apparently because no one knows if there might be a palindrome if the computation is continued sufficiently far. It is conjectured that there are an infinite number of Lychrel numbers.

Your task is to write a function that determines if a number appears to be a Lychrel number and, if not, returns the chain of numbers that shows it is not. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

### 10 Responses to “Lychrel Numbers”

1. Paul said

In Python.

```def is_lychrel(m, iters=1000):
mrev = int(str(m)[::-1])
for t in range(iters):
if mrev == m:
return False
m += mrev
mrev = int(str(m)[::-1])
return True
```
2. FA said

In Scala.
Checks until 1000000000L
I hope that my understanding is correct what chain of numbers was required.

```package programmingpraxis

// https://programmingpraxis.com/2015/09/01/lychrel-numbers/
object LychrelNumbers {
def r(n: Long): Long = n.toString.reverse.toInt
def s(n: Long): Long = n + r(n)
def isPalindrome(n: Long): Boolean = n.toString == n.toString.reverse
def isLeadsToPalindrome(n: Long, max: Long): Boolean = if (n > max) false else isPalindrome(n) || isLeadsToPalindrome(s(n), max)
def chain(n: Long, max: Long): Seq[Long] = if (n > max) List() else List(n) ++ chain(s(n), max)
def lychrelStream(from: Long, max: Long): Stream[Tuple2[Long, Seq[Long]]] = {
if (isLeadsToPalindrome(from, max)) lychrelStream(from + 1, max)
else Stream.cons((from, chain(from, max)), lychrelStream(from + 1, max))
}

lychrelStream(1, 1000000000L).take(10).toList.mkString("\r\n")
//> res0: String = (89,List(89, 187, 968, 1837, 9218, 17347, 91718, 173437, 907808, 1716517, 8872688, 17735476, 85189247, 159487405, 664272356))
//| (98,List(98, 187, 968, 1837, 9218, 17347, 91718, 173437, 907808, 1716517, 8872688, 17735476, 85189247, 159487405, 664272356))
//| (177,List(177, 948, 1797, 9768, 18447, 92928, 175857, 934428, 1758867, 9447438, 17794887, 96644658, 182289327, 906271608))
//| (187,List(187, 968, 1837, 9218, 17347, 91718, 173437, 907808, 1716517, 8872688, 17735476, 85189247, 159487405, 664272356))
//| (196,List(196, 887, 1675, 7436, 13783, 52514, 94039, 187088, 1067869, 10755470, 18211171, 35322452, 60744805, 111589511, 227574622, 454050344, 897100798))
}
```
3. klettier said

F# solution:

```let decomposeInt n = n.ToString() |> Seq.toList

let rev (n) = n
|> decomposeInt
|> List.rev
|> List.map (fun i-> i.ToString())
|> List.reduce (fun i i1 -> i + i1)
|> fun s -> System.Int64.Parse(s)

let (|Palindrome|_|) (n) =
let num = decomposeInt n
let rec loop (num : 'a list) a b =
if a >= b then Some n
elif num.[a] = num.[b] then loop num (a+1) (b-1)
else None
loop num 0 (num.Length-1)

let s n = n + rev n

let ``Is Lychrel number`` n =
let rec loop = function
| Palindrome a ->  Some a
| a -> try
let newN = s a
loop newN
with
| :? System.FormatException
| :? System.OverflowException -> None
match loop n with
| Some a-> printfn "%A is not Lychrel number -> %A" n a ; false
| None -> printfn "Lychrel number -> %A" n ; true

for i in 190L..300L do
``Is Lychrel number`` i
```

190L is not Lychrel number -> 45254L
191L is not Lychrel number -> 191L
192L is not Lychrel number -> 6996L
193L is not Lychrel number -> 233332L
194L is not Lychrel number -> 2992L
195L is not Lychrel number -> 9339L
Lychrel number -> 196L
197L is not Lychrel number -> 881188L
198L is not Lychrel number -> 79497L
199L is not Lychrel number -> 3113L
200L is not Lychrel number -> 202L
201L is not Lychrel number -> 303L
202L is not Lychrel number -> 202L
203L is not Lychrel number -> 505L
204L is not Lychrel number -> 606L
205L is not Lychrel number -> 707L
206L is not Lychrel number -> 808L
207L is not Lychrel number -> 909L
208L is not Lychrel number -> 1111L
209L is not Lychrel number -> 1111L
210L is not Lychrel number -> 222L
211L is not Lychrel number -> 323L
212L is not Lychrel number -> 212L
213L is not Lychrel number -> 525L
214L is not Lychrel number -> 626L
215L is not Lychrel number -> 727L
216L is not Lychrel number -> 828L
217L is not Lychrel number -> 929L
218L is not Lychrel number -> 1331L
219L is not Lychrel number -> 2442L
220L is not Lychrel number -> 242L
221L is not Lychrel number -> 343L
222L is not Lychrel number -> 222L
223L is not Lychrel number -> 545L
224L is not Lychrel number -> 646L
225L is not Lychrel number -> 747L
226L is not Lychrel number -> 848L
227L is not Lychrel number -> 949L
228L is not Lychrel number -> 1551L
229L is not Lychrel number -> 2662L
230L is not Lychrel number -> 262L
231L is not Lychrel number -> 363L
232L is not Lychrel number -> 232L
233L is not Lychrel number -> 565L
234L is not Lychrel number -> 666L
235L is not Lychrel number -> 767L
236L is not Lychrel number -> 868L
237L is not Lychrel number -> 969L
238L is not Lychrel number -> 1771L
239L is not Lychrel number -> 2882L
240L is not Lychrel number -> 282L
241L is not Lychrel number -> 383L
242L is not Lychrel number -> 242L
243L is not Lychrel number -> 585L
244L is not Lychrel number -> 686L
245L is not Lychrel number -> 787L
246L is not Lychrel number -> 888L
247L is not Lychrel number -> 989L
248L is not Lychrel number -> 1991L
249L is not Lychrel number -> 5115L
250L is not Lychrel number -> 505L
251L is not Lychrel number -> 707L
252L is not Lychrel number -> 252L
253L is not Lychrel number -> 1111L
254L is not Lychrel number -> 4444L
255L is not Lychrel number -> 6666L
256L is not Lychrel number -> 8888L
257L is not Lychrel number -> 11011L
258L is not Lychrel number -> 1221L
259L is not Lychrel number -> 2332L
260L is not Lychrel number -> 545L
261L is not Lychrel number -> 747L
262L is not Lychrel number -> 262L
263L is not Lychrel number -> 2662L
264L is not Lychrel number -> 4884L
265L is not Lychrel number -> 45254L
266L is not Lychrel number -> 88555588L
267L is not Lychrel number -> 13431L
268L is not Lychrel number -> 1441L
269L is not Lychrel number -> 2552L
270L is not Lychrel number -> 585L
271L is not Lychrel number -> 787L
272L is not Lychrel number -> 272L
273L is not Lychrel number -> 5115L
274L is not Lychrel number -> 9559L
275L is not Lychrel number -> 44044L
276L is not Lychrel number -> 8836886388L
277L is not Lychrel number -> 15851L
278L is not Lychrel number -> 1661L
279L is not Lychrel number -> 2772L
280L is not Lychrel number -> 2662L
281L is not Lychrel number -> 45254L
282L is not Lychrel number -> 282L
283L is not Lychrel number -> 2552L
284L is not Lychrel number -> 4774L
285L is not Lychrel number -> 6996L
286L is not Lychrel number -> 8813200023188L
287L is not Lychrel number -> 233332L
288L is not Lychrel number -> 1881L
289L is not Lychrel number -> 2992L
290L is not Lychrel number -> 2552L
291L is not Lychrel number -> 6996L
292L is not Lychrel number -> 292L
293L is not Lychrel number -> 2992L
294L is not Lychrel number -> 9339L
Lychrel number -> 295L
296L is not Lychrel number -> 881188L
297L is not Lychrel number -> 79497L
298L is not Lychrel number -> 3113L
299L is not Lychrel number -> 5335L
300L is not Lychrel number -> 303L

4. Francesco said

```l n | n == (read . reverse . show) n = [show n, "<-- Lychrel num"]
| otherwise                      = show n : l (s n)
where s n = n + (read . reverse . show) n```
5. programmingpraxis said

Somebody asked how to compute Lychrel numbers in Python at Stack Overflow today, and I wrote this program:

```def rev(n, r=0):
if n == 0: return r
return rev(n // 10, r*10 + n%10)

def lychrel(n, bound=1000):
r = rev(n); chain = [n]
while bound > 0:
n += r; r = rev(n)
chain.append(n)
if n == r: return chain
bound -= 1
return [chain[0]]

>>> lychrel(196)
[196]
>>> lychrel(281)
[281, 463, 827, 1555, 7106, 13123, 45254]```
6. matthew said

I’ve been getting in to monad programming lately, so here’s a solution that defines a “bounded computation” monad and then uses that to limit the length of sequence we look at. It’s a bit longer than Francesco’s solution above (but it does terminate for input eg. of 196):

```import Data.Maybe

-- Monad to represent bounded computations
-- Includes an operation count
data BoundedComp a = B (Int -> Maybe(a,Int))

B f >>= g = B(\n-> apply (f n) g) where
apply Nothing _ = Nothing
apply (Just(x,n)) g = h n where B h = g x
return x = B(\n -> Just(x,n))

-- Check count and abort if necessary
tick :: () -> BoundedComp ()
tick() = B(\n -> if n == 0 then Nothing else Just((),n-1))

-- Run computation and return result, if there is one
evalBoundedComp :: BoundedComp a -> Int -> Maybe a
evalBoundedComp (B f) = fmap fst . f

-- Is n a palindrome?
ispal :: Integer -> Bool
ispal n = show n == reverse(show n)

-- Next in Lychrel sequence
next :: Integer -> Integer
next n = n + read(reverse(show n))

-- Extend Lychrel sequence in BoundedComp
try :: [Integer] -> BoundedComp [Integer]
try s = do {
tick();
let n' = next (head s)
in if ispal n' then return (n':s)
else try (n':s)
}

lychrel :: Int -> Integer -> (Integer, Maybe [Integer])
lychrel count n = (n, fmap reverse (evalBoundedComp (try [n]) count))

main :: IO()
main =
print (map fst (filter (isNothing . snd) (map (lychrel 100) [1..1000]))) >>
mapM_ print (map (lychrel 100) [190..200])
```
7. eu90h said

Here’s one in Racket:
(define string-reverse (compose list->string reverse string->list))
(define (string-palindrome? s) (equal? (string-reverse s) s))
(define (f n) (+ n (string->number (string-reverse (number->string n)))))

(define (lychrel? n [tolerance 10000])
(let loop ([n n] [result (list n)] [i 1])
(if (>= i tolerance)
#t
(if (string-palindrome? (number->string n))
result
(let ([y (f n)]) (loop y (append result (list y)) (+ i 1)))))))

8. euler90h said

Apologies, I forgot to enclose that in source code tags!

9. matthew said

Here’s another Haskell solution – to save some effort, perform all calculations on lists of digits, rather than the numbers themselves. We just need some conversions and an add with carry function (smallest digit comes first in the list representation):

```tolist :: Integer -> [Int]
tolist = reverse . fmap (read . return) . show

fromlist :: [Int] -> Integer
fromlist = read . (>>=id) . fmap show . reverse

adc :: [Int] -> [Int] -> Int -> [Int]
adc [] [] 0 = []
adc [] [] c = [c]
adc (n:s) (m:t) c = n' : adc s t c' where (c',n') = quotRem (n+m+c) 10

next :: [Int] -> [Int]
next n = adc n (reverse n) 0

lychrel :: Int -> Integer -> [Integer]
lychrel count n = map fromlist (loop count [tolist n]) where
loop 0 s = [last s]
loop m s = if n' == reverse n' then reverse (n':s)
else loop (m-1) (n':s)
where n' = next (head s)

main :: IO()
main = print (map head (filter (null . tail) (map (lychrel 100) [1..1000])))
```
10. Mayur Lokare said

#include
int main()
{
int num,rev=0,num1,val=0;
printf(“Enter the number\n”);
scanf(“%d”,&num);
num1 = num;
while(1)
{
for(;num1;val = val*10+num1%10,num1/=10);
if(num==val)
{
printf(“we get the num -> %d\n”,num);
break;
}
printf(“num become -> %d\n”,num);
num1 = num+val;
num = num1;
val=0;
}
}

O/P:
Enter the number
281
num become -> 281
num become -> 463
num become -> 827
num become -> 1555
num become -> 7106
num become -> 13123

Enter the number
261
num become -> 261
num become -> 423
we get the num -> 747

Enter the number
731
num become -> 731
we get the num -> 868

you can enter any number you will get it’s corresponding palindrome number