Lychrel Numbers
September 1, 2015
We begin with functions r and s, described above, and p? that determines if its argument is a palindrome:
(define (r n)
(let loop ((n n) (z 0))
(if (zero? n) z
(loop (quotient n 10)
(+ (* z 10) (modulo n 10))))))
(define (s n) (+ n (r n)))
(define (p? n) (= n (r n)))
Then we write the function that either returns the chain that proves its input is not a lychrel number or dies if it reaches the bound b, which defaults to 100:
(define (lychrel n . b)
(let ((b (if (null? b) 100 (car b))))
(let loop ((b b) (z n) (xs (list n)))
(if (zero? b) (list n #f)
(let ((x (s z)))
(if (p? x) (reverse (cons x xs))
(loop (- b 1) x (cons x xs))))))))
Here are some examples:
> (lychrel 281) (281 463 827 1555 7106 13123 45254) > (lychrel 196) (196 #f)
And here we compute the list of lychrel numbers less than a thousand:
> (do ((n 1 (+ n 1))) #f
(when (not (cadr (lychrel n 1000)))
(display n) (newline)))
196
295
394
493
592
689
691
788
790
879
887
978
986
We set a high bound because the claim that a number is a Lychrel number requires a rather high confidence, though chains ending in a palindrome after more than 100 steps are uncommon.
You can run the program at http://ideone.com/ndemYe.
Programming Praxis 
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 TrueIn 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)) }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`` i190L 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
Haskell:
l n | n == (read . reverse . show) n = [show n, "<-- Lychrel num"] | otherwise = show n : l (s n) where s n = n + (read . reverse . show) nSomebody 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]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)) instance Monad BoundedComp where 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])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)))))))
Apologies, I forgot to enclose that in source code tags!
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])))#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