Funktionen

[Gunnar Bittersmann]

@@Gunnar Bittersmann:

nuqneH

Nächster Teil der Hausaufgabe: Terminiert der Algorithmus für alle ganzen Zahlen z? Warum?

Hehe, macht hier niemand Hausaufgaben?

Sei z eine N-Stellige natürliche Zahl, in Ziffern: [latex]z = z_{N-1} z_{N-2} \ldots z_1 z_0[/latex]

u ist die Zahl mit den Ziffern von z in umgekehrter Reihenfolge: [latex]u = z_0 z_1 \ldots z_{N-2} z_{N-1}[/latex]

Der Algorithmus generiert die Glieder der arithmetischen Folge [latex]p_n = z + n u, \quad n \in \mathbb N[/latex] und terminiert, wenn [latex]p_n[/latex] ein Palindrom ist.

Die Frage ist nun: Gibt es für jedes z ein n derart, dass [latex]p_n[/latex] ein Palindrom ist, der Algorithmus also terminiert?

Ja. Beweis:

Für [latex]n = 10^N[/latex] ist [latex]p_n = 10^N u + z = z_0 z_1 \ldots z_{N-2} z_{N-1} z_{N-1} z_{N-2} \ldots z_1 z_0[/latex] ein Palindrom.

Anmerkung: Es ist hier irrelevant, ob der Algorithmus schon früher terminiert. Wichtig war zu zeigen, dass es für jedes z ein n gibt, bei dem er spätestens terminiert.

Qapla'