Project Euler : 51–55

• Problem 52 ( Click to Read )

Without thinking much I first wrote a brute force algorithm and it gave answer within 2 seconds. But, a fact can reduce searching space. x and 6x will contain same digits, so number of digits in x and 6x should also be same. If x is n-digit number than 6x should also be n-digit number and thus for n-digit number find maximum value of x such that 6x is also n-digit. Example if x is 3-digit number, maximum value of 6x should be 999 thus, maximum value of x should be 999/6 and it reduces search space by huge amount.

def perm (m, n):
  hash1 = [0] * 10
  hash2 = [0] * 10
 
  for i in range (0, 10, 1):
    hash1[i] = 0
    hash2[i] = 0
  while (m):
    r = m % 10
    hash1[r] = hash1[r] + 1
    m = m // 10
 
  while (n):
    r = n % 10
    hash2[r] = hash2[r] + 1
    n = n // 10
  ans = 1
  for i in range (0, 10, 1):
    if (hash1[i] != hash2[i]):
      ans = 0
 
  return ans

loop = 1
for i in range (1, 11, 1):
  max = ((10 ** i) // 6) + 1
  min = (10 ** (i - 1)) + 1
  for j in range (min, max, 1):
    if (perm(j, 2 * j) and perm(j * 2, j * 3) and perm(j * 3, j * 4) and perm(j * 4, j * 5) and perm(j * 5, j * 6)):
      print(j)
      loop = 0
      break
    if (loop == 0):
      break

• Problem 55 ( Click to Read )

This is a nice problem. I have used brute force method and checked from 1 till 9999 every number if it can be converted into its palindrome before 50 iterations.

For each number, I calculated its reverse using rev function in code and added it to original number. Passed that sum to function palin to check if it is a palindrome. If yes, than it is not Lychrel number and if no, increase counter by 1. If total counting is below 50 repeat process, if not it is Lychrel number.

I wrote in C++ and took ‘long long int’ but it gave wrong result and than changed data type to ‘long long unsigned int’ and got accepted. It means if a number like 196 which takes more than 50 iterations might turn huge to be accommodated in few data types. you may use Python to make task simpler, no data type problem in that.

#include <iostream>
bool palin (long long unsigned int x)
{
  long long unsigned int n, m = 0ULL;
  n = x;
  while (n)
  {
    m = m * 10ULL + (n % 10ULL);
    n = n / 10ULL;
  }
  return (m == x);
}
long long unsigned int rev (long long unsigned int n)
{
  long long unsigned int m = 0ULL;
 
  while (n)
  {
    m = m * 10ULL + (n % 10ULL);
    n /= 10ULL;
  }
  return m;
}
int main()
{
  long long unsigned int i, x, n, sum = 0ULL, count;
  for (i=1ULL; i<10000ULL; i++)
  {
    n = i, count = 0ULL;
    while (count < 50ULL)
    {
      x = n + rev(n);
 
      if (palin(x))
        break;
      else
        n = x, count++;
    }
    if (count == 50ULL)
      sum++;
  }
  std::cout<<sum<<"\n";
  return 0;
}

You can find more Project Euler solutions on my Project Euler Publication.