Skip to main content

Lychrel number

In mathematics, Lychrel numbers are a class of numbers that possess an interesting property when subjected to a certain iterative process. The process involves taking a number, reversing its digits, and adding the original number to its reverse. If the resulting sum is a palindrome (a number that reads the same forwards and backwards), then the original number is not a Lychrel number. However, if the process continues indefinitely without producing a palindrome, the number is considered a Lychrel number.

Problem Statement

The task at hand is to determine whether a given number is a Lychrel number or not. To do this, we apply the reversal and addition process iteratively up to a certain limit (in this case, 25 times) and check if a palindrome is formed. If no palindrome is formed within the limit, the number is considered a Lychrel number.

Example

Let's take the number 196 as an example to illustrate the process:

  1. 196 + 691 = 887 (not a palindrome)
  2. 887 + 788 = 1675 (not a palindrome)
  3. 1675 + 5761 = 7436 (not a palindrome)
  4. 7436 + 6347 = 13783 (not a palindrome)
  5. 13783 + 38731 = 52514 (not a palindrome)
  6. 52514 + 41525 = 94039 (not a palindrome)
  7. 94039 + 93049 = 187088 (not a palindrome)
  8. 187088 + 880781 = 1067869 (not a palindrome)
  9. 1067869 + 9687601 = 10755470 (not a palindrome)

The process continues indefinitely without forming a palindrome. Hence, 196 is a Lychrel number.

Pseudocode and Algorithm

reverse(number):
    result = 0
    while number > 0:
      result = (result * 10) + (number % 10)
      number = number / 10
    return result
  
is_palindrome(number):
if number is equal to reverse(number):
	return 1
else:
	return 0

is_lychrel(number):
limit = 25
for i from 0 to limit:
	number = number + reverse(number)
	if is_palindrome(number) == 1:
	return 0
return 1

lychrel(number):
if is_lychrel(number) == 1:
	print number, "is a Lychrel number"
else:
	print number, "is not a Lychrel number"
  
main():
lychrel(196)
lychrel(57)
lychrel(788)
lychrel(56)
lychrel(887)
  

Code Solution

Here given code implementation process.

//C Program
//Check Lychrel number
#include <stdio.h>

//Reverse the given number
long reverse(long number)
{

  long result = 0;

  while(number>0)
  {
    if(result==0)
    {
      result=number%10;
    }
    else
    {
      result=(result*10)+(number%10);
    }
    number/=10;
  }
  return result;
}


int is_palindrome(long number) 
{ 
  //Check if a reversal form of given number are equal or not ?
  if(number == reverse(number))
  {
    //when yes
    return 1;
  }
  else
  {
    //when no
    return 0;
  }

}
// This function are determine whether given number is lychrel or not
int is_lychrel(long number) 
{ 
  //use to control execution 
  int limit = 25;

  for (int i = 0; i < limit; i++) 
  { 
    number = number + reverse(number); 

    if (is_palindrome(number)==1) 
    { //When result is form of palindrome
      return 0; 
    }
  } 

  return 1; 
} 
// This method are used to handle request of lychrel number
// Basically this are displaying status of lychrel number
void lychrel(long number)
{
  if(is_lychrel(number)==1)
  {
    printf("%ld is lychrel number\n",number );
  }
  else
  {
    printf("%ld is not lychrel number\n", number);
  }
}



int main() {

  // Test Case
  lychrel(196);
  lychrel(57);
  lychrel(788);
  lychrel(56);
  lychrel(887);
  return 0;
}

Output

196 is lychrel number
57 is not lychrel number
788 is lychrel number
56 is not lychrel number
887 is lychrel number
/*
 C++ Program
 Determine whether number is Lychrel number
*/
#include<iostream>

using namespace std;

class MyNumber {
    public:

        //Reverse the given number
        long reverse(long number) {
            long result = 0;
            while (number > 0) {
                if (result == 0) {
                    result = number % 10;
                } else {
                    result = (result *10) + (number % 10);
                }
                number /= 10;
            }
            return result;
        }
    bool is_palindrome(long number) {
        //Check if a reversal form of given number are equal or not ?

        if (number == this->reverse(number)) {
            return true;
        } else {
            return false;
        }
    }
    // This function are determine whether given number is lychrel or not
    bool is_lychrel(long number) {
        //use to control execution 
        int limit = 25;
        for (int i = 0; i < limit; i++) {
            number = number + this->reverse(number);
            if (this->is_palindrome(number) == true) {
                return false;
            }
        }
        return true;
    }
    // This method are used to handle request of lychrel number
    // Basically this are displaying status of lychrel number
    void lychrel(long number) {
        if (this->is_lychrel(number) == true) {
            cout << number << " is lychrel number\n";
        } else {
            cout << number << " is not lychrel number\n";
        }
    }
};
int main() {
    MyNumber obj ;
    // Test Case
    obj.lychrel(196);
    obj.lychrel(57);
    obj.lychrel(788);
    obj.lychrel(56);
    obj.lychrel(887);
    return 0;
}

Output

196 is lychrel number
57 is not lychrel number
788 is lychrel number
56 is not lychrel number
887 is lychrel number
/*
  Java Program
  Determine whether number is Lychrel number
*/

public class MyNumber {

  //Reverse the given number
  public long reverse(long number)
  {

    long result = 0;

    while(number>0)
    {
      if(result==0)
      {
        result=number%10;
      }
      else
      {
        result=(result*10)+(number%10);
      }
      number/=10;
    }
    return result;
  }


  public boolean is_palindrome(long number) 
  { 
    //Check if a reversal form of given number are equal or not ?
    if(number == reverse(number))
    {
      //when yes
      return true;
    }
    else
    {
      //when no
      return false;
    }

  }
  // This function are determine whether given number is lychrel or not
  public boolean is_lychrel(long number) 
  { 
    //use to control execution 
    int limit = 25;

    for (int i = 0; i < limit; i++) 
    { 
      number = number + reverse(number); 

      if (is_palindrome(number) == true) 
      { //When result is form of palindrome
        return false; 
      }
    } 

    return true; 
  } 
  // This method are used to handle request of lychrel number
  // Basically this are displaying status of lychrel number
  public void lychrel(long number)
  {
    if(is_lychrel(number)==true)
    {
      System.out.print(number+" is lychrel number\n" );
    }
    else
    {
      System.out.print(number+" is not lychrel number\n" );
    }
  }



  public static void main(String[] args) {

    MyNumber obj = new MyNumber();
      // Test Case
      obj.lychrel(196);
      obj.lychrel(57);
      obj.lychrel(788);
      obj.lychrel(56);
      obj.lychrel(887);
  }
}

Output

196 is lychrel number
57 is not lychrel number
788 is lychrel number
56 is not lychrel number
887 is lychrel number
/*
  C# Program
  Determine whether number is Lychrel number
*/
using System;
public class MyNumber {

    //Reverse the given number
    public long reverse(long number) {

        long result = 0;

        while (number > 0) {
            if (result == 0) {
                result = number % 10;
            } else {
                result = (result * 10) + (number % 10);
            }
            number /= 10;
        }
        return result;
    }


    public Boolean is_palindrome(long number) {
        //Check if a reversal form of given number are equal or not ?
        if (number == reverse(number)) {
            //when yes
            return true;
        } else {
            //when no
            return false;
        }

    }
    // This function are determine whether given number is lychrel or not
    public Boolean is_lychrel(long number) {
        //use to control execution 
        int limit = 25;

        for (int i = 0; i < limit; i++) {
            number = number + reverse(number);

            if (is_palindrome(number) == true) { //When result is form of palindrome
                return false;
            }
        }

        return true;
    }
    // This method are used to handle request of lychrel number
    // Basically this are displaying status of lychrel number
    public void lychrel(long number) {
        if (is_lychrel(number) == true) {
            Console.Write(number + " is lychrel number\n");
        } else {
            Console.Write(number + " is not lychrel number\n");
        }
    }



    public static void Main(String[] args) {

        MyNumber obj = new MyNumber();
        // Test Case
        obj.lychrel(196);
        obj.lychrel(57);
        obj.lychrel(788);
        obj.lychrel(56);
        obj.lychrel(887);
    }
}

Output

196 is lychrel number
57 is not lychrel number
788 is lychrel number
56 is not lychrel number
887 is lychrel number
# Python 3 Program
# Determine whether number is Lychrel number
class MyNumber :
    #Reverse the given number
    def reverse(self, number) :
        result = 0
        while (number > 0) :
            if (result == 0) :
                result = number % 10
            else :
                result = (result * 10) + (number % 10)
            
            number = int(number / 10)
        
        return result
    
    def is_palindrome(self, number) :
        #Check if a reversal form of given number are equal or not ?

        if (number == self.reverse(number)) :
            return True
        else :
            return False
        
    
    # This function are determine whether given number is lychrel or not
    def is_lychrel(self, number) :
        limit = 25
        i = 0
        while (i < limit) :
            number = number + self.reverse(number)
            if (self.is_palindrome(number) == True) :
                return False
            
            i += 1
        
        return True
    
    # Basically this are displaying status of lychrel number

    # This method are used to handle request of lychrel number
    def lychrel(self, number) :
        if (self.is_lychrel(number) == True) :
            print(number ," is lychrel number")
        else :
            print(number ," is not lychrel number")
        
    

def main() :
    obj = MyNumber()
    #Test Case
    obj.lychrel(196)
    obj.lychrel(57)
    obj.lychrel(788)
    obj.lychrel(56)
    obj.lychrel(887)


if __name__ == "__main__":
    main()

Output

196 is lychrel number
57 is not lychrel number
788 is lychrel number
56 is not lychrel number
887 is lychrel number
# Ruby Program
# Determine whether number is Lychrel number
class MyNumber 
    #Reverse the given number
    def reverse(number) 
        result = 0
        while (number > 0) 
            if (result == 0) 
                result = number % 10
            else 
                result = (result * 10) + (number % 10)
            end
            number = (number / 10).to_i 
        end
        return result
    end
    def is_palindrome(number) 
        #Check if a reversal form of given number are equal or not ?

        if (number == self.reverse(number)) 
            return true
        else 
            return false
        end
    end
    # This function are determine whether given number is lychrel or not
    def is_lychrel(number) 
        limit = 25
        i = 0
        while (i < limit) 
            number = number + self.reverse(number)
            if (self.is_palindrome(number) == true) 
                return false
            end
            i += 1
        end
        return true
    end
    # Basically this are displaying status of lychrel number

    # This method are used to handle request of lychrel number
    def lychrel(number) 
        if (self.is_lychrel(number) == true) 
            print(number ," is lychrel number\n")
        else 
            print(number ," is not lychrel number\n")
        end
    end
end
def main() 
    obj = MyNumber.new()
    #Test Case
    obj.lychrel(196)
    obj.lychrel(57)
    obj.lychrel(788)
    obj.lychrel(56)
    obj.lychrel(887)
end
main()

Output

196 is lychrel number
57 is not lychrel number
788 is lychrel number
56 is not lychrel number
887 is lychrel number
/*
 Scala Program
 Determine whether number is Lychrel number
*/
class MyNumber {
    //Reverse the given number
    def reverse(num : Long): Long = {
        var result: Long = 0;
        var number: Long = num;
        while (number > 0) {
            if (result == 0) {
                result = number % 10;
            } else {
                result = (result * 10) + (number % 10);
            }
            number = number/10;
        }
        return result;
    }
    def is_palindrome(number: Long): Boolean = {
        //Check if a reversal form of given number are equal or not?

        if (number == this.reverse(number)) {
            return true;
        } else {
            return false;
        }
    }
    // This function are determine whether given number is lychrel or not
    def is_lychrel(num : Long): Boolean = {
        var limit: Int = 25;
        var i: Int = 0;
        var number: Long = num;
        while (i < limit) {
            number = number + this.reverse(number);
            if (this.is_palindrome(number) == true) {
                return false;
            }
            i += 1;
        }
        return true;
    }
    // This method are used to handle request of lychrel number
    // Basically this are displaying status of lychrel number
    def lychrel(number: Long): Unit = {
        if (this.is_lychrel(number) == true) {
            print( s"$number is lychrel number\n");
        } else {
            print( s"$number is not lychrel number\n");
        }
    }
}
object Main {
    def main(args: Array[String]): Unit = {
        var obj: MyNumber = new MyNumber();
        //Test Case
        obj.lychrel(196);
        obj.lychrel(57);
        obj.lychrel(788);
        obj.lychrel(56);
        obj.lychrel(887);
    }
}

Output

196 is lychrel number
57 is not lychrel number
788 is lychrel number
56 is not lychrel number
887 is lychrel number
/*
  Swift 4 Program
  Determine whether number is Lychrel number
*/
class MyNumber {
    //Reverse the given number
    func reverse(_ num: Int) -> Int {
        var result: Int = 0;
       var number : Int = num;
        while (number > 0) {
            if (result == 0) {
                result = number % 10;
            } else {
                result = (result * 10) + (number % 10);
            }
            number /= 10;
        }
        return result;
    }
    func is_palindrome(_ number: Int) -> Bool {
        //Check if a reversal form of given number are equal or not?

        if (number == self.reverse(number)) {
            return true;
        } else {
            return false;
        }
    }
    // This function are determine whether given number is lychrel or not
    func is_lychrel(_ num: Int) -> Bool {
        let limit : Int = 25;
        var number : Int = num;
        var i: Int = 0;
        while (i < limit) {
            number = number + self.reverse(number);
            if (self.is_palindrome(number) == true) {
                return false;
            }
            i += 1;
        }
        return true;
    }
    // This method are used to handle request of lychrel number
    // Basically this are displaying status of lychrel number
    func lychrel(_ number: Int) {
        if (self.is_lychrel(number) == true) {
            print(number ," is lychrel number");
        } else {
            print(number ," is not lychrel number");
        }
    }
}
func main() {
    let obj: MyNumber = MyNumber();
    //Test Case
    obj.lychrel(196);
    obj.lychrel(57);
    obj.lychrel(788);
    obj.lychrel(56);
    obj.lychrel(887);
}
main();

Output

196  is lychrel number
57  is not lychrel number
788  is lychrel number
56  is not lychrel number
887  is lychrel number
<?php
/*
  Php Program
  Determine whether number is Lychrel number
*/
class MyNumber {
    //Reverse the given number

    public  function reverse($number) {
        $result = 0;
        while ($number > 0) {
            if ($result == 0) {
                $result = $number % 10;
            } else {
                $result = ($result *10) + ($number % 10);
            }
            $number = intval($number/10);
        }
        return $result;
    }
    public  function is_palindrome($number) {
        //Check if a reversal form of given number are equal or not ?

        if ($number == $this->reverse($number)) {
            return true;
        } else {
            return false;
        }
    }
    // This function are determine whether given number is lychrel or not

    public  function is_lychrel($number) {
        //use to control execution 
        $limit = 25;
        for ($i = 0; $i < $limit; $i++) {
            $number = $number + $this->reverse($number);
            if ($this->is_palindrome($number) == true) {
                return false;
            }
        }
        return true;
    }
    // This method are used to handle request of lychrel number
    // Basically this are displaying status of lychrel number

    public  function lychrel($number) {
        if ($this->is_lychrel($number) == true) {
            echo($number ." is lychrel number\n");
        } else {
            echo($number ." is not lychrel number\n");
        }
    }
};

function main() {
    $obj = new MyNumber();
    // Test Case

    $obj->lychrel(196);
    $obj->lychrel(57);
    $obj->lychrel(788);
    $obj->lychrel(56);
    $obj->lychrel(887);
}
main();

Output

196 is lychrel number
57 is not lychrel number
788 is lychrel number
56 is not lychrel number
887 is lychrel number
/*
 Node Js Program
 Determine whether number is Lychrel number
*/
class MyNumber {
    //Reverse the given number
    reverse(number) {
        var result = 0;
        while (number > 0) {
            if (result == 0) {
                result = number % 10;
            } else {
                result = (result *10) + (number % 10);
            }
            number = parseInt(number / 10);
        }
        return result;
    }
    is_palindrome(number) {
        //Check if a reversal form of given number are equal or not ?

        if (number == this.reverse(number)) {
            return true;
        } else {
            return false;
        }
    }
    // This function are determine whether given number is lychrel or not
    is_lychrel(number) {
        //use to control execution 
        var limit = 25;
        for (var i = 0; i < limit; i++) {
            number = number + this.reverse(number);
            if (this.is_palindrome(number) == true) {
                return false;
            }
        }
        return true;
    }
    // This method are used to handle request of lychrel number
    // Basically this are displaying status of lychrel number
    lychrel(number) {
        if (this.is_lychrel(number) == true) {
            process.stdout.write(number + " is lychrel number\n");
        } else {
            process.stdout.write(number + " is not lychrel number\n");
        }
    }
}

function main(args) {
    var obj = new MyNumber();
    // Test Case
    obj.lychrel(196);
    obj.lychrel(57);
    obj.lychrel(788);
    obj.lychrel(56);
    obj.lychrel(887)
}
main();

Output

196 is lychrel number
57 is not lychrel number
788 is lychrel number
56 is not lychrel number
887 is lychrel number

Resultant Output Explanation

The given code applies the Lychrel test on five numbers: 196, 57, 788, 56, and 887.

  • 196: As shown in the example above, 196 is a Lychrel number.
  • 57: When we apply the process to 57, it reaches a palindrome on the second iteration itself:
    57 + 75 = 132 (not a palindrome)
    132 + 231 = 363 (a palindrome)
  • 788: is lychrel number.
    788 + 887 = 1675 (not a palindrome)
    1675 + 5761 = 7436 (not a palindrome)
    7436 + 6347 = 13783 (not a palindrome)
    13783 + 38731 = 52514 (not a palindrome)
    52514 + 41525 = 94039 (not a palindrome)
    94039 + 93049 = 187088 (not a palindrome)
    187088 + 880781 = 1067869 (not a palindrome)
    1067869 + 9687601 = 10755470 (not a palindrome)
  • 56: Similar to 57, 56 forms a palindrome on the first iteration (56 + 65 = 121), so it is not a Lychrel number.
  • 887: For 887, the process continues indefinitely without forming a palindrome, making it a Lychrel number.

Time Complexity

The time complexity of the provided code is primarily determined by the is_lychrel function, which iterates a fixed number of times (25 in this case). Let's assume the number of digits in the input number is "d."

  1. The reverse function has a time complexity of O(d) since it iterates through each digit of the input number once.
  2. The is_palindrome function also has a time complexity of O(d) for the same reason as above.

Considering these, the overall time complexity of the is_lychrel function is O(d) per iteration, and since the number of iterations is fixed (25 in this case), the time complexity of the entire program is O(25 * d) or simply O(d), where "d" is the number of digits in the input number.





Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment