Quersumme

Als Quersumme (oder Ziffernsumme) bezeichnet man üblicherweise die Summe der Ziffern der Darstellung einer Zahl im Dezimalsystem.

Verallgemeinert ist jedoch jedes Positionssystem möglich, weiterhin können in der verallgemeinerten gewichteten Quersumme die Stellen gewichtet werden.

Typen von Quersummen

Einfache (nichtalternierende) Quersumme

Die Quersumme von n = 36036 ist q = 3+6+0+3+6 = 18. Für 3 und 9 ist sie ein Teilbarkeitskriterium: Die Quersumme q einer dezimalen Zahl n ist genau dann durch 3 oder 9 teilbar, wenn n durch 3 oder 9 teilbar ist.

Alternierende Quersumme

Die alternierende Quersumme von n = 36036 ist q = 3-6+0-3+6 = 0. Für 11 ist sie ein Teilbarkeitskriterium: Die alternierende Quersumme q einer dezimalen Zahl n ist genau dann durch 11 teilbar, wenn n durch 11 teilbar ist.

Nichtalternierende n-Quersumme

Die nichtalternierende 2er-Quersumme von n = 36036 ist q = 3+60+36 = 99. Für 3, 9, 11, 33 und 99 ist sie ein Teilbarkeitskriterium: Die nichtalternierende 2er-Quersumme q einer dezimalen Zahl n ist genau dann durch diese Zahlen teilbar, wenn n durch diese teilbar ist.

Die nichtalternierende 3er-Quersumme von n = 36036 ist q = 36+036 = 72. Für 3, 9, 27, 37, 111, 333 und 999 ist sie ein Teilbarkeitskriterium: Die nichtalternierende 3er-Quersumme q einer dezimalen Zahl n ist genau dann durch diese Zahlen teilbar, wenn n durch diese teilbar ist.

Bemerkung: Die nichtalternierende n-Quersumme ist identisch zur nichtalternierende Quersumme zur Basis 10^n.

Alternierende n-Quersumme

Die alternierende 2er-Quersumme von n = 36036 ist q = 3-60+36 = -21. Für 101 ist sie ein Teilbarkeitskriterium: Die alternierende 2er-Quersumme q einer dezimalen Zahl n ist genau dann durch 101 teilbar, wenn n durch 101 teilbar ist.

Die alternierende 3er-Quersumme von n = 36036 ist 36-036 = 0. Für 7, 11, 13, 77, 91 und 143 ist sie ein Teilbarkeitskriterium: Die alternierende 3er-Quersumme q einer dezimalen Zahl n ist genau dann durch diese Zahlen teilbar, wenn n durch die Zahlen teilbar ist.

Bemerkung: Die alternierende n-Quersumme ist identisch zur alternierende Quersumme zur Basis 10^n.

Gewichtete Quersumme

Eine Verallgemeinerung sind gewichtete Quersummen, bei denen die Ziffern erst mit den Werten einer Zahlenfolge multipliziert und diese Ergebnisse dann addiert werden. Es wird dabei mit der niederwertigsten Ziffer begonnen (bei der einfachen Quersumme ist die Reihenfolge egal). Die Wichtungsfolge kann dabei periodisch oder nichtperiodisch sein. Ein Beispiel ist die periodische Folge 1, 3, 2, −1, −3, −2, ... Die gewichtete Quersumme der Zahl 422625 ist (bei der niedrigsten Stelle angefangen):

5·1 + 2·3 + 6·2 − 2·1 − 2·3 − 4·2 = 5 + 6 + 12 − 2 − 6 − 8 = 7

Die so gewichtete Quersumme liefert eine Teilbarkeitsregel für die Zahl 7. Auch für andere natürliche Zahlen kann man solche periodischen Folgen finden, z.B.

• für 11 die Folge +1, −1, ... Diese liefert die so genannte alternierende Quersumme
• für 13 die Folge 1, −3, −4, −1, 3, 4, ...

Für die meisten Teiler ist es jedoch nicht praktikabel, die Teilbarkeit mittels Quersummenbildung zu überprüfen, weil es nur wenige gut merkbare periodische Wichtungsfolgen gibt.

Möchte man eine entsprechende Teilbarkeitsregel für die natürliche Zahl m finden, so betrachtet man die Reste der 10-er Potenzen bei der Division mit m. Die Reste entsprechen den gesuchten Gewichten.

Beispiel: m = 7

1 $\equiv$ 1 mod 7

10 $\equiv$ 3 mod 7

100 $\equiv$ 2 mod 7

1000 $\equiv$ −1 mod 7

10000 $\equiv$ −3 mod 7

100000 $\equiv$ −2 mod 7

1000000 $\equiv$ 1 mod 7 (ab hier wiederholen sich die Reste)

Die Wichtungsfolge lautet also 1, 3, 2, −1, −3, −2, ...

Prüfziffer von ISBN–-Nummern

Die mit den Faktoren (1,2,3,4,5,6,7,8,9,10) gewichtete Quersumme einer ISBN-Nummer ist modulo 11 immer 0 (die Ziffer 'X' hat dabei den Zahlenwert von 10 und kann in der letzten Ziffer auftreten). Dies wird erreicht, indem die ersten 9 Ziffern das Produkt beschreiben und eine 10. Ziffer (Prüfziffer) so angehängt wird, das obige Forderung erfüllt ist.

Fight Club
von Chuck Palahniuk, Fred Kinzel, Werner Schmitz
Broschiert - Goldmann
Erscheinungsdatum: Dezember 2004
ISBN: 344254210-3

3*1 + 4*2 + 4*3 + 2*4 + 5*5 + 4*6 + 2*7 + 1*8 + 0*9 + 3*10 MOD 11 = 132 MOD 11 = 0

Die ISBN ist gültig.

Quersummensatz

• Sei folgendes gegeben:
  • Wir benutzen ein Zahlensystem mit der Basis n+1 (wobei $n\in \mathbb {N}$).
  • t ist ein Teiler von n (wobei $t\in \mathbb {N}$).
  • Wir haben eine natürliche Zahl a gegeben.
• Dann gilt:
  • Die Zahl a ist durch t teilbar genau dann, wenn ihre Quersumme (in diesem Zahlensystem) durch t teilbar ist.

Beispielsweise ist im Dezimalsystem n=9. Damit ist t ∈ {1,3,9}. Folglich kann man die Quersummenregelung zur Überprüfung der Teilbarkeit durch 3 und durch 9 anwenden.

Im Hexadezimalsystem ist n=15. Damit ist t ∈ {1,3,5,15}. Somit kann man die Quersummenregelung im Hexadezimalsystem zur Überprüfung der Teilbarkeit durch 3, durch 5 und durch 15 anwenden.

Wiederholbarkeit

Hat die Quersumme einer Zahl k mehr als eine Stelle, lässt sich der Vorgang so oft wiederholen, bis das Ergebnis nur noch eine Stelle im jeweiligen Zahlensystem hat. Für die so erzeugten einstelligen (oder "iterierten") Quersummen qs(k,t) gilt (t sei immer noch die Basis des Zahlensystems - 1):

$qs(k,t)=\left\{{\begin{matrix}0,&{\mbox{wenn }}k=0\\t,&{\mbox{wenn }}k\;\operatorname {mod} \;t=0\\k\;\operatorname {mod} \;t,&{\mbox{wenn }}k\;\operatorname {mod} \;t\neq 0\end{matrix}}\right.$

Beispiel:
k sei 4582
Basis sei 10, dann ist t=9;
4582 => 4 + 5 + 8 + 2 = 19 19 => 1 + 9 = 10 10 => 1 + 0 = 1
d.h. qs(4582,9)=1 und es ist: 1 = 4582 mod 9.

Insbesondere ist also eine positive natürliche Zahl genau dann durch 9 teilbar, wenn ihre iterierte Quersumme 9 ist.

Siehe auch: Hash-Funktion und die dort genannten Verfahren.

Zu klären:

• Ist die Wiederholbarkeit auch bei periodisch gewichteten Quersummen gegeben?
• Ist die Wiederholbarkeit auch bei nicht periodisch gewichteten Quersummen gegeben?

Berechnung

Algorithmen zur Quersummenberechnung (in Python-Schreibweise):

1) Berechnung einer einfachen Quersumme:

Beispiel: EinfachQuerSumme(9979,10)= 34

 def EinfachQuerSumme(Zahl, Basis):
    Quer=0
    while Zahl:
        Quer= Quer + (Zahl % Basis)
        Zahl=     int(Zahl / Basis)
    print Quer

2) Wiederholte Berechnung der Quersumme und Reduktion auf eine Ziffer:

Beispiel: WiederholQuerSumme(9979,10)= 7

def WiederholQuerSumme ( Zahl, Basis ):
   while Zahl >= Basis:
       Quer = 0
       while Zahl:
           Quer = Quer + (Zahl % Basis) 
           Zahl =    int (Zahl / Basis)
       Zahl = Quer
   print Zahl

3) Berechnung der alternierenden Quersumme:

Beispiel: AlternierendeQuerSumme(9979,10)= 2

def AlternierendeQuerSumme ( Zahl, Basis ):
   while Zahl >= Basis:
       Quer = 0
       while Zahl:
           Quer =     (Zahl % Basis) - Quer
           Zahl = int (Zahl / Basis)
       if Quer < 0:
           Zahl = -Quer
       else:
           Zahl =  Quer
   print Zahl

Weblinks

• http://www.jonelo.de/java/bigal_de.html
  Freies und plattformunabhängiges Programm, u. a. zur Berechnung von Quersummen (mit Java-Quelltext)
• http://www.madeasy.de/2/prgquer.htm
  • Quersummenprogramm in Visual Basic
• http://www.madeasy.de/7/prgquer.htm
  • Quersummenprogramm in Gambas (Computer)