אלגוריתם 196

שיעור 20 מתוך 20 בקורס חידות מתמטיות של Coddy.

אם ניקח את 38, נהפוך את הסדר ונחבר, נקבל 38 + 83 = 121, שהוא מספר פלינדרומי.

לא כל המספרים יוצרים פלינדרומים במהירות כזאת. לדוגמה,

37 + 73 = 110
110 + 11 = 121

כלומר, ל־37 נדרשו שתי איטרציות כדי להגיע לפלינדרום.

דוגמה נוספת, החל מ־249:

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

מניחים שמספרים פלינדרומיים כגון 11, 343, נעשים פלינדרומיים באפס איטרציות.

קחו כל מספר שלם חיובי, הפכו את סדר הספרות וחברו אותו למספר המקורי. זוהי פעולת תהליך ההיפוך והחיבור. כעת חזרו על התהליך עם הסכום שהתקבל, עד שמתקבל מספר פלינדרומי. תהליך זה יוצר במהירות מספרים פלינדרומיים עבור רוב המספרים השלמים.

מספר שאינו יוצר פלינדרום לעולם באמצעות תהליך ההיפוך והחיבור נקרא מספר ליכְרֶל. המספרים הראשונים שלא ידוע כי הם יוצרים פלינדרומים, המכונים „מספרי ליכְרֶל מועמדים”, הם 196, 295, 394. [https://mathworld.wolfram.com/196-Algorithm.html]

אתגר

בינוני

אף על פי שאיש עדיין לא הוכיח זאת, מספרים מסוימים במערכת הספרתית בבסיס 10, כמו 196, לעולם אינם יוצרים פלינדרום. לצורך האתגר הזה, נניח שמספר הוא מספר ליכרל עד שיוכח אחרת. כל מספר קטן מעשרת אלפים יהפוך לפלינדרום בתוך פחות מחמישים איטרציות, או שעד כה איש, על אף כל כוח המחשוב הקיים, לא הצליח להביא אותו לידי פלינדרום.

כתבו פונקציה isLychrel שמקבלת מספר שלם חיובי הקטן מ־10000 ומחזירה את מספר האיטרציות הדרושות כדי להפוך לפלינדרום.

החזירו ‎-1 במקרה שעברו יותר מחמישים איטרציות.

נסו בעצמכם

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