Problem des Monats März 2001

Diesmal gibt es ein Problem aus der Zahlentheorie. Die Lösung kann man durch Probieren mit kleinen Zahlen herausfinden, aber auch ein Beweis ist mit Elementarmathematik möglich.

Wir wollen natürliche Zahlen (ganze Zahlen  ≥ 1 )  als Summe aufeinander folgender natürlicher Zahlen darstellen, z.B.:

9 = 4 + 5

10 = 1 + 2 + 3 + 4

100 = 18 + 19 + 20 + 21 + 22

3000 = 999 + 1000 + 1001

Für welche natürlichen Zahlen geht das und für welche nicht?

Lösung

Durch Probieren (bis  20  reicht schon) kommt man schnell zu der Vermutung, dass sich alle natürlichen Zahlen  n  außer den Zweierpotenzen  n = 2^r  als solche Summen darstellen lassen:

1 (= 2⁰)  geht nicht

2 (= 2¹)  geht nicht

3 = 1 + 2

4 (= 2²)  geht nicht

5 = 2 + 3

6 = 1 + 2 + 3

7 = 3 + 4

8 (= 2³)  geht nicht

9 = 4 + 5

10 = 1 + 2 + 3 + 4

11 = 5 + 6

12 = 3 + 4 + 5

13 = 6 + 7

14 = 2 + 3 + 4 + 5

15 = 7 + 8

16 (= 2⁴)  geht nicht

17 = 8 + 9

18 = 3 + 4 + 5 + 6

19 = 9 + 10

20 = 2 + 3 + 4 + 5 + 6

...

Für ungerade Zahlen  n > 1  ist das ganz einfach, man kommt immer mit zwei Summanden aus:

n = (n-1)/2 + (n+1)/2

also z.B.  11 = 5 + 6 ,  101 = 50 + 51 ,  12345 = 6172 + 6173 .

Sei nun  n  gerade. Die Anzahl der aufeinander folgenden Summanden nennen wir  k . Ist  n  als eine solche Summe darstellbar, mit  m  als Startwert, so ist

n = m + (m+1) + . . . + (m+k-1) ,

das ergibt

n = k·m + (0 + 1 + . . . + (k-1)) = k·m + (k-1)·k/2 .

Also muss  n  von der Form sein:

n = (k+q)·k/2 ,  dabei ist  q = 2m - 1 .

Oder:

2n = (k+q)·k

Zweierpotenzen  n = 2^r  lassen sich so nicht darstellen, denn  2n = 2^r+1  hat keinen ungeraden Faktor, aber weil  q  ungerade ist, ist entweder  k + q  oder  k  ungerade.

Ist  n  keine Zweierpotenz, so muss man passende  k  und  q  finden. Für Nicht-Zweierpotenzen  n  kann man schreiben:

2n = 2ⁱ·u     ( u  ist das Produkt aller ungeraden Primfaktoren von  n )

Da  2ⁱ·u = (k+q)·k  gelten soll, fällt die Wahl leicht: Man nimmt für  k  die kleinere der beiden Zahlen  2ⁱ  und  u , und für  k + q  die größere; in mathematischer Schreibweise:

k = min {2ⁱ, u}      q = |2ⁱ - u|

Als Beispiel wählen wir  n = 94 . Dann ist  2n = 188 = 2²·47 , folglich  i = 2, u = 47  und damit  k = 4  (also gibt es  4  Summanden),  q = 43 . Aus dem Wert für  q  berechnet man den ersten Summanden  m = 22 . Ergebnis:

94 = 22 + 23 + 24 + 25

Dies ist die einzig mögliche derartige Zerlegung von  94 , aber im Allgemeinen ist die Darstellung nicht eindeutig, wie z.B.  n = 78  zeigt:

78 = 25 + 26 + 27

78 = 18 + 19 + 20 + 21

78 = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 + 11 + 12 

Zum Auffinden von Summanden gibt es noch einen anderen Weg:

n  muss (mindestens) einen ungeraden Teiler  w  haben, wenn  n  keine Zweierpotenz ist. Dann ist  n  die Summe von  w  aufeinander folgenden Summanden mit  n/w  als mittlerem Summanden.

Dazu muss man sich nur klar machen, dass die Addition des ersten und letzten, des zweiten und vorletzten (usw.) Summanden jeweils zum gleichen Ergebnis führt, nämlich  2·n/w .

Für  n = 2001  kann man z.B.  w = 3  wählen und erhält  n/w = 667 . Also ist

2001 = 666 + 667 + 668


Kategorie: Zahlen und Zahlsysteme, Berechnung von π