Home » Problem sets » Project Euler » Projust Euler 55 – Lychrel Numbers

Projust Euler 55 – Lychrel Numbers

This isn’t too difficult a problem, but it’s made simpler with a few helper functions. Most problems thus far could all be written in main(), but this problem requires a lot of string processing (at least the way I’m going about it). As for the problem description:

First, there are palindromic numbers, which are, as the name implies, numbers that are palindromes (read the same forward and backwards). For example, 7337. Then take 349. If we reverse it, and add the reverse to itself, we may or may not get a palindrome. If we don’t, we simply repeat the process:

349 + 943 = 1292

1292 + 2921 = 4213

4213 + 3124 = 7337

So 349 produces a palindrome in 3 iterations. It is thought that some numbers never produce a palindrome with this process, called Lychrel numbers. Because there still isn’t a method for detecting whether a number is Lychrel or not, we’ll assume that a number is Lychrel if it doesn’t produce a palindrome in 50 iterations. The problem description was also nice enough to provide another piece of information, telling us that 10677 is the first number that requires 50+ iterations to terminate, ending at a number that is 28 digits long, so we know what kind of numbers we may be dealing with. The question is, how many numbers are not Lychrel below 10000?

Since the numbers quickly overflow the basic data types, I thought we’d do most of the problem with strings. First we need a function to convert to string, and a function to reverse such a string.

string toString(int n){
   string out = "";
   stringstream nss;
   nss << n;
   return out=nss.str();
} // I guess this wasn't as necessary, since I just ended up using the sstream library

string reverse(string str){
   string out = "";
   for(int i = str.length()-1 ; i >= 0; i--){
   out+=str[i];
   }
   return out;
}

As mentioned, the process quickly overflows even a long long. So I wrote a function to add strings as numbers, and in the case that overflow would occur, adding is done by taking a number in two parts: the lower 18 digits and the upper digits. Two 19 digit numbers could overflow a long long, so I stopped at 18. By the problem description, the largest number we’re dealing with is around ~28 digits, so this method will safely  deal with all numbers we’ll come across in this problem. I should mention this isn’t the most pretty looking thing:

string addAsNum(string a, string b){
   string out = "";
   string templ, tempu;
   stringstream lss, uss;
   int carry = 0;
   unsigned long long au, al, bu, bl;
   if(a.length() > 18){ // is a number is greater than 18 digits, we'll have to split it into lower and upper
      stringstream(a.substr(a.length()-18, 18)) >> al;
      a.erase(a.length()-18, 18);
      stringstream(a) >> au;
   } else {
      stringstream(a) >> al;
      au = 0;
   }
   if(b.length() > 18){
      stringstream(b.substr(b.length()-18, 18)) >> bl;
      b.erase(b.length()-18, 18);
      stringstream(b) >> bu;
   } else {
      stringstream(b) >> bl;
      bu = 0;
   }
   lss << (al+bl); // add the lowers, and if that turns out to be greater than 18 digits, we'll have a carry
   templ = lss.str();
   if(templ.length() > 18){
      carry = 1;
      templ.erase(0,1);
   }
   if(carry) uss << (au+bu+1);
   else uss << (au+bu);

   tempu = uss.str();
   if(tempu == "0") tempu = "";
   return out = tempu+templ; // then simply concatenate the upper and lower
}

The rest is pretty straightforward. A function tests if a number is Lychrel or not by repeating the reverse and add process, stopping either when we get a palindrome, or when we have repeated the process 50 times. The main loop calls this function on all numbers < 10000.

bool isLychrel(int n){
   int iterations = 0;
   string temp = toString(n);
   while(iterations < 50){
      temp = addAsNum(temp, reverse(temp));
      if(isPalindrome(temp)){
         return false;
      }
      iterations++;
   }
   return true;
}

int main() {
   clock_t t1 = clock(), t2;
   int count = 0;
   for(int i = 1; i < 10000; i++){
      if(isLychrel(i)) count++;
   }
   t2 = clock();
   cout << "Ans: " << count << endl;
   cout << ((float)t2 - (float)t1)/CLOCKS_PER_SEC << endl;
   return 0;
}

Final Answer: 249

Advertisements

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