196-algorithm

Leçon 20 sur 20 du cours Énigmes mathématiques de Coddy.

Si nous prenons 38, que nous l'inversons et que nous l'ajoutons, 38 + 83 = 121, ce qui est un palindrome.

Tous les nombres ne produisent pas de palindromes aussi rapidement. Par exemple,

37 + 73 = 110
110 + 11 = 121

C'est-à-dire que 37 a nécessité deux itérations pour arriver à un palindrome.

Un autre exemple, en commençant par 249 :

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

Les nombres palindromes tels que 11, 343, sont supposés devenir des palindromes en zéro itération.

Prenez n'importe quel entier positif, inversez les chiffres et ajoutez-le au nombre d'origine. C'est l'opération du processus d'inversion et d'addition. Répétez maintenant la procédure avec la somme ainsi obtenue jusqu'à l'obtention d'un nombre palindrome. Cette procédure produit rapidement des nombres palindromes pour la plupart des entiers.

Un nombre qui ne forme jamais de palindrome par le processus d'inversion et d'addition est appelé un nombre de Lychrel. Les premiers nombres dont on ne sait pas s'ils produisent des palindromes, les nombres "candidats de Lychrel", sont 196, 295, 394. [https://mathworld.wolfram.com/196-Algorithm.html]

Défi

Moyen

Bien que personne ne l'ait encore prouvé, certains nombres dans le système de numération en base 10, comme 196, ne produisent jamais de palindrome. Pour les besoins de ce défi, nous supposerons qu'un nombre est de Lychrel jusqu'à preuve du contraire. Pour chaque nombre inférieur à dix mille, soit (i) il deviendra un palindrome en moins de cinquante itérations, soit (ii) personne, avec toute la puissance de calcul existante, n'a réussi jusqu'à présent à le transformer en palindrome.

Écrivez une fonction isLychrel qui reçoit un entier positif inférieur à 10000, et renvoie le nombre d'itérations nécessaires pour qu'il devienne un palindrome.

renvoyez -1 dans le cas où plus de cinquante itérations se sont écoulées.

Essayez vous-même

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