Quersumme

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

Verallgemeinert ist jedoch jedes Stellenwertsystem 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: Eine dezimal dargestellte Zahl n ist genau dann durch 3 oder 9 teilbar, wenn ihre Quersumme q durch 3 bzw. 9 teilbar ist.

Einstellige Quersumme

Von der einfachen Quersumme wird weiter so lange die Quersumme gebildet, bis nur noch eine einstellige Zahl übrig bleibt.

z.B. 93 -> 9+3 -> 12 -> 1+2 -> 3

Alternierende Quersumme

Die alternierende Quersumme von n = 36036 ist a-qs = 3 - 6 + 0 - 3 + 6 = 0. Für 11 ist sie ein Teilbarkeitskriterium: Eine dezimal dargestellte Zahl n ist genau dann durch 11 teilbar, wenn ihre alternierende Quersumme a-qs durch 11 teilbar ist, oder diese gleich 0 ist.

Die alternierende Quersumme wird gebildet, indem man von einer beliebig langen Zahl (deren Ziffern man bei der Berechnung der alternierenden Quersumme von links nach rechts liest) folgende Additionen bildet:

1) Man addiert zur ersten Ziffer die dritte, fünfte, siebte ... etc.!
2) Man addiert zur zweiten Ziffer die vierte, sechste, achte ... etc.!

Nun subtrahiert man die zweite Zahl von der ersten Zahl und erhält die alternierende Quersumme!

Beispiel: 2536874
1) 2 + 3 + 8 + 4 = 17
2) 5 + 6 + 7 = 18

17 - 18 = -1 --> Die Zahl ist also nicht durch 11 teilbar

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 q = 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.

Kann vllt mal irgedjmd ne andere Zahl als 36036 angeben? Ist zwar einfach mit zu rechnen allerdings bringt mich dieses Bsp nicht viel...

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, dass obige Forderung erfüllt ist.

Beispiel

Für die ISBN 3442542103 ist

$(3\cdot 1+4\cdot 2+4\cdot 3+2\cdot 4+5\cdot 5+4\cdot 6+2\cdot 7+1\cdot 8+0\cdot 9+3\cdot 10)\mod 11\;=\;132\mod 11\;=\;0$,

also ist dies eine gültige ISBN.

Quersummensatz

• Sei folgendes gegeben:
  • Wir benutzen ein Stellenwertsystem mit der Grundzahl 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 Stellenwertsystem) durch t teilbar ist.

Beispielsweise ist im Dezimalsystem die Grundzahl 10, also 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.

Iterierte Quersumme

Ist die Quersumme einer Zahl k eine mehrstellige Zahl, lässt sich der Vorgang so oft wiederholen, bis das Ergebnis nur noch eine Stelle im jeweiligen Zahlensystem hat. Für die so erzeugten (stets einstelligen) iterierten Quersummen $\operatorname {qs} (k,t)$ gilt (t sei wie oben wieder die Basis des Zahlensystems - 1):

$\operatorname {qs} (k,t)={\begin{cases}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{cases}}$

Beispiel im Dezimalsystem:

$\operatorname {qs} (4582,9)=\operatorname {qs} (4+5+8+2,9)=\operatorname {qs} (19,9)=\operatorname {qs} (10,9)=1$,

und es ist

$4582\mod 9=1$.

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.

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

1a) Berechnung einer einfachen Quersumme, rekursiv, Java:

public static int quer(int s){
  if (s<10) return s;
  return(quer(s/10))+s%10;
}

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

alternativ ohne while-Schleife und Basis >1 Zahl ist zur Basis 10. 10= 10 dezimal und nicht 3 zur Basis 3

def WiederholQuerSumme(Zahl,Basis):
   if (Zahl>=Basis)&(Basis>1):
      Zahl = (Zahl-Basis)%(Basis-1)+1
   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
• http://www.dbr-software.de/delphi/quersum.php
  Quersummenprogramm in Delphi