Algoritmo 196

Lezione 20 di 20 del corso Indovinelli matematici di Coddy.

Se prendiamo 38, invertiamo le cifre e le sommiamo, 38 + 83 = 121, che è palindromo.

Non tutti i numeri producono palindromi così rapidamente. Per esempio,

37 + 73 = 110
110 + 11 = 121

Cioè, 37 ha richiesto due iterazioni per arrivare a un palindromo.

Un altro esempio, partendo da 249:

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

Si presume che i numeri palindromi come 11, 343 diventino palindromi in zero iterazioni.

Prendi un qualsiasi intero positivo, invertine le cifre e sommalo al numero originale. Questa è l'operazione del processo di inversione e addizione. Ora ripeti la procedura con la somma ottenuta, finché non si ottiene un numero palindromo. Questa procedura produce rapidamente numeri palindromi per la maggior parte degli interi.

Un numero che non forma mai un palindromo tramite il processo di inversione e addizione è chiamato numero di Lychrel. I primi numeri per i quali non è noto se producano palindromi, i «candidati numeri di Lychrel», sono 196, 295, 394. [https://mathworld.wolfram.com/196-Algorithm.html]

Sfida

Medio

Sebbene nessuno lo abbia ancora dimostrato, alcuni numeri nel sistema numerico in base 10, come 196, non producono mai un palindromo. Ai fini di questa sfida, supporremo che un numero sia di Lychrel finché non viene dimostrato il contrario. Ogni numero inferiore a diecimila o (i) diventerà un palindromo in meno di cinquanta iterazioni oppure (ii) nessuno, con tutta la potenza di calcolo disponibile, è finora riuscito a trasformarlo in un palindromo.

Scrivi una funzione isLychrel che riceva un intero positivo minore di 10000 e restituisca il numero di iterazioni necessarie per diventare un palindromo.

restituisci -1 se sono trascorse più di cinquanta iterazioni.

Provalo tu

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