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

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: