196-algorithm

Lesson 20 of 20 in Coddy's Mathematical Riddles course.

If we take 38, reverse and add, 38 + 83 = 121, which is palindromic.

Not all numbers produce palindromes so quickly. For example,

37 + 73 = 110
110 + 11 = 121

That is, 37 took two iterations to arrive at a palindrome.

Another example, starting with 249:

249+942=1191
1191+1911=3102
3102+2013=5115.

Palindrome numbers such as 11, 343, are assumed to become palindrome in zero iterations.

Take any positive integer, reverse the digits, and add to the original number. This is the operation of the reverse-and-add process. Now repeat the procedure with the sum so obtained until a palindromic number is obtained. This procedure quickly produces palindromic numbers for most integers.

A number that never forms a palindrome through the reverse and add process is called a Lychrel number. The first few numbers not known to produce palindromes, "candidate Lychrel" numbers are 196, 295, 394. [https://mathworld.wolfram.com/196-Algorithm.html]

Challenge

Medium

Although no one has proved it yet, some numbers in base-10 numeral system, like 196, never produce a palindrome. For the purpose of this challenge, we shall assume that a number is Lychrel until proven otherwise. Every number below ten-thousand, it will either (i) become a palindrome in less than fifty iterations, or, (ii) no one, with all the computing power that exists, has managed so far to map it to a palindrome.

Write a function isLychrel that receives a positive integer smaller than 10000, and return the number of iterations it take to become palindrome.

return -1 in case more than fifty iterations passed.

Try it yourself

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include "solution.h"

int main() {
    int n;
    if (scanf("%d", &n) != 1) n = 0;
    int r = isLychrel(n);
    printf("%d\n", r);
    return 0;
}