Wir alle wissen, dass man durch Berechnen der einfachen Quersumme ermitteln kann, ob eine Zahl durch 3 teilbar ist. Dieses Prinzip kann man vom Grundsatz her auf alle Zahlen anwenden, wenn man die einzelnen Stellen zusätzlich bewertet. Wie ich in meiner Lösung begonnen habe, hat
1 / 81 den Rest 1
10 / 81 den Rest 10
100 / 81 den Rest 19
... die Reste 28, 37, 46, 55, 64, 73
und 1000000000 / 81 wieder den Rest 1
und so weiter (ab hier wiederholen sich die Reste periodisch).
Um zu ermitteln, ob eine große Zahl durch 81 teilbar ist, berechne ich eine "bewertete" Quersumme, indem ich jede Ziffer mit dem dem Stellenwert entsprechenden Divisionsrest multipliziere:
abcdefghiabcdefghiabcdefghi (Buchstaben zur Hilfestellung)
123456789333334444455555555
/ 81 hat den gleichen Rest wie
(
(a) (1 + 3 + 4 ) * 73 +
(b) (2 + 3 + 5 ) * 64 +
(c) (3 + 3 + 5 ) * 55 +
(d) (4 + 3 + 5 ) * 46 +
(e) (5 + 3 + 5 ) * 37 +
(f) (6 + 4 + 5 ) * 28 +
(g) (7 + 4 + 5 ) * 19 +
(h) (8 + 4 + 5 ) * 10 +
(i) (9 + 4 + 5 ) * 1
) / 81
Ist also diese "bewertete" Quersumme durch 81 teilbar, so ist auch die große Zahl durch 81 teilbar.
Der zweite Schritt war meine Feststellung, dass die Berwertungsfaktoren für zwei Benachbarte stellen sich stets um 9 unterscheiden. Dadurch kam ich auf die Überlegung (dass ich eine gerade bzw. durch 4 teilbare Anzahl Stellen brauche, setze ich, weil schon begründet, voraus):
Ein Palindrom mit gerader Stellenzahl kann ich ausdrücken durch
x = a0*1000000....1 + a1*100000...10 + a2*10000...100 + a3*1000...1000 + a4*100...10000 + ... Daher die Betrachtung von Zahlen mit je 2 1en und ihren Verschiebungen:
Wenn ich eine Zahl 11000...0 habe, hat die irgendenen Rest bei Division durch 81.
Verschiebe ich nun eine 1 nach rechts und eine 1 nach links, ändert sich meine bewertete Quersumme für die eine Ziffer um ein Delta von + 9, für die andere Ziffer um eine Delta von -9. Das heißt, diese bleibt identisch. Beispiel:
11000 / 81 hat den gleichen Rest wie ( 37 + 28 ) / 81, nämlich 65
Verschiebung:
100100 / 81 hat den gleichen Rest wie ( 46 + 19 ) / 81, nämlich 65
Das kann ich so lange wiederholen, bis eine 1 ganz rechts steht, und immer muss der Rest identisch bleiben (da ich ihn mit einer 1 durch Verschiebung um eine Stelle um 9 erhöhe und mit der anderen um 9 erniedrige).
Nun kenne ich noch nicht die Länge meines Palindroms, muss meine Zahlen mit den Einserpärchen noch einmal genauer betrachten.
11 / 81 hat den Rest 10 + 1 = 11
110 / 81 hat den Rest 19 + 10 = 29
1100 / 81 hat den Rest 28 + 19 = 47
... (Reste 65, 2, 20, 38, 56, 74)
Wie ganz oben setzt bei 9 Nullen wieder eine Periode ein.
11000000000 / 81 hat den Rest 11
DANN kommt meine Feststellung: Alle diese Reste haben keinen Faktor 3 (also keinen mit 81 gemeinsamen Faktor). ERST JETZT kommt meine Schlussfolgerung, dass bei Konstruktion des Palindrums nach dem Schema
x = a0*1000000....1 + a1*100000...10 + a2*10000...100 + a3*1000...1000 + a4*100...10000 + ...
diese Zahl bei divisision durch 81 den Rest
Rest(x/81) = Rest( ( a0*Rest(1000000....1/81) + a1*Rest(100000...10) + a2*Rest(10000...100) + a3*Rest(1000...1000) + a4*Rest(100...10000) + ... )/81 )
= Rest( (a0 + a1 + a2 + a3 + a4 + ...) * Rest (1000000....1/81) )/81 )
haben muss.
Rest (1000000....1/81) hat, wie festgestellt, keinen gemeinsamen Faktor mit 81, darum muss
(a0 + a1 + a2 + a3 + a4 + ...)
für mein konstruiertes Palindrom durch 81 teilbar sein.
Der Rest wie in meiner Lösung
