196-algorithm

Lição 20 de 20 do curso Enigmas Matemáticos da Coddy.

Se pegarmos 38, invertermos e somarmos, 38 + 83 = 121, que é um palíndromo.

Nem todos os números produzem palíndromos tão rapidamente. Por exemplo,

37 + 73 = 110
110 + 11 = 121

Ou seja, o 37 levou duas iterações para chegar a um palíndromo.

Outro exemplo, começando com 249:

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

Números palíndromos como 11, 343, são considerados palíndromos em zero iterações.

Pegue qualquer número inteiro positivo, inverta os dígitos e some ao número original. Esta é a operação do processo de inverter e somar. Agora repita o procedimento com a soma obtida até que um número palíndromo seja alcançado. Este procedimento produz rapidamente números palíndromos para a maioria dos inteiros.

Um número que nunca forma um palíndromo através do processo de inverter e somar é chamado de número de Lychrel. Os primeiros números que não se sabe se produzem palíndromos, números "candidatos a Lychrel", são 196, 295, 394. [https://mathworld.wolfram.com/196-Algorithm.html]

Desafio

Médio

Embora ninguém tenha provado ainda, alguns números no sistema numérico de base 10, como 196, nunca produzem um palíndromo. Para o propósito deste desafio, assumiremos que um número é de Lychrel até que se prove o contrário. Para cada número abaixo de dez mil, ele irá (i) tornar-se um palíndromo em menos de cinquenta iterações, ou (ii) ninguém, com todo o poder computacional existente, conseguiu até agora mapeá-lo para um palíndromo.

Escreva uma função isLychrel que receba um número inteiro positivo menor que 10000 e retorne o número de iterações que leva para se tornar um palíndromo.

Retorne -1 caso passem mais de cinquenta iterações.

Experimente você mesmo

#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;
}