Das Kefk Network Wiki befindet sich im Testbetrieb.

Quersumme

Aus Kefk.

Wechseln zu: Navigation, Suche

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

Verallgemeinert können Quersummen jedoch in jedem Stellenwertsystem gebildet werden, siehe dazu den Abschnitt Quersummensatz. Sie umfassen neben der Summe von Ziffern auch

  • die alternierende Quersumme (wechselndes Addieren und Subtrahieren von Ziffern)
  • Operationen auf Zifferpaaren, -tripeln usw. sowie
  • stellenweise gewichtete Verfahren

Inhaltsverzeichnis

Typen von Quersummen

Quersumme (im üblichen Sinne)

Die Quersumme ist die Summe aller Ziffern einer Zahl. So ist für eine Zahl n = 36036 die Quersumme q(n) = 3 + 6 + 0 + 3 + 6 = 18. Für die Teilbarkeit einer Zahl durch 3 oder 9 kann stellvertretend ihre Quersumme herangezogen werden: Eine dezimal dargestellte Zahl n ist genau dann durch 3 oder 9 teilbar, wenn ihre Quersumme q(n) ohne Rest durch 3 bzw. 9 teilbar ist. Generell lässt n bei der Division durch 3 oder 9 denselben Rest wie die Quersumme q(n):

q(n) \equiv n\mod 9

(oder anders ausgedrückt: Die Differenz einer Zahl und ihrer Quersumme ist immer durch 9 teilbar).

Diese Eigenschaft bildet die Grundlage der Neunerprobe.

Einstellige (oder iterierte) Quersumme

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

z.B. 

q(93) = 9+3 = 12; q(12) = 1+2 = 3

Alternierende Quersumme

Die alternierende Quersumme (auch Querdifferenz, Paarquersumme oder Wechselsumme genannt)[2] erhält man, indem man bei einer Zahl, beginnend mit der am weitesten rechts stehenden Ziffer, die Ziffern abwechselnd subtrahiert und addiert. So ist für die Zahl n = 36036 die alternierende Quersumme aqs(n) = 6 - 3 + 0 - 6 + 3 = 0.

Gleichwertig dazu ist das folgende Verfahren (die Zählung der Ziffern soll wieder rechts beginnen):

  1. Man addiert zur ersten Ziffer die dritte, fünfte, siebte usw.
  2. Man addiert zur zweiten Ziffer die vierte, sechste, achte usw.
  3. Subtrahiert man nun von der ersten Summe die zweite, so erhält man die alternierende Quersumme.

Für die Teilbarkeit einer Zahl n durch 11 kann stellvertretend ihre alternierende Quersumme aqs(n) herangezogen werden: Eine dezimal dargestellte Zahl n ist genau dann durch 11 teilbar, wenn ihre alternierende Quersumme aqs(n) ohne Rest durch 11 teilbar ist.

Wiederholte Anwendung der alternierenden Quersumme liefert den Rest der Zahl bei Division durch 11, wobei negative Werte durch Addition von 11 zu normalisieren sind. Eine aqs von 11 zieht eine weitere Bildung einer aqs nach sich, die 0 liefert (also den Rest der Division von 11 durch 11).

Beispiel: 

n = 2536874
4 + 8 + 3 + 2 = 17
7 + 6 + 5     = 18

17 - 18 = -1; -1 + 11 = 10

daraus folgt: Die Zahl 2536874 lässt bei Division durch 11 den Rest 10, 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, 143 und 1001 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, 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

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.

Allgemein gilt, dass die Quersumme qn der Darstellung einer Zahl a im Stellenwertsystem mit der Basis n den Rest modulo n − 1 unverändert lässt, also

q_n(a)\equiv a \mod (n-1),

und die alternierende Quersumme aqsn der Darstellung im Stellenwertsystem mit der Basis n den Rest modulo n + 1 unverändert lässt, also

aqs_n(a)\equiv a \mod (n+1).

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 \ne 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)
    return 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;
}

1c) Berechnung einer einfachen Quersumme im Berechnungsmodell einer Registermaschine (RM = (P,1,2)): 

1 LOAD 1
2 MOD #10
3 ADD 2
4 STORE 2
5 LOAD 1
6 DIV #10
7 STORE 1
8 JZERO 10
9 GOTO 2
10 END

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
   return 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
   return 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
   return Zahl

Quellen

  1. ↑ Hans Schubart: Einführung in die klassische und moderne Zahlentheorie Vieweg, Braunschweig 1974. ISBN 3-528-03313-4. S 47.
  2. ↑ Herrmann Engesser (Bearbeiter): Der kleine Duden Mathematik. Bibliographisches Institut, Mannheim, Wien, Zürich (1986). ISBN 3-411-02180-2. S 364, Stichwort "Quersumme"

Weblinks

Wikipedia
 Dieses Dokument entstammt in seiner ersten oder einer späteren Version der deutschsprachigen Wikipedia. Es ist dort zu finden unter dem Stichwort Quersumme, die Liste der bisherigen Autoren befindet sich in der Versionsliste; die Originalfassung kann dort auch bearbeitet werden. Alle Texte der Wikipedia und ihre Derivate stehen unter der GNU-Lizenz für freie Dokumentation.
Von „http://www.kefk.org/wiki/Quersumme“
Persönliche Werkzeuge
Andere Sprachen