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:
- 196 + 691 = 887 (not a palindrome)
- 887 + 788 = 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)
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."
- The
reverse
function has a time complexity of O(d) since it iterates through each digit of the input number once. - 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.
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