Motivation:
Im Fitness-Studio macht es mehr Spaß, eine Übung 1 + 2 + 3 + 4 + 3 + 2 + 1 Mal durchzuführen, als sie 16 Mal durchzuführen. Das ist die selbe Gesamtanzahl, sieht aber zunächst weniger aus und ist leichter zählbar.
Zur Abwechslung kann man 16 Wiederholungen auch in 5 + 6 + 5 aufteilen.

Zerlegen in Summenturm aufeinanderfolgender Zahlen

Hier einige Beispiele:

13 = 4 + 5 + 4
14 = 2 + 3 + 4 + 3 + 2
16 = 5 + 6 + 5
16 = 1 + 2 + 3 + 4 + 3 + 2 + 1
19 = 6 + 7 + 6
19 = 3 + 4 + 5 + 4 + 3 
1963 = 654 + 655 + 654 
2016 = 181 + 182 + ... + 185 + 186 + 185 + ... + 182 + 181 

Weitere Beispiele finden Sie mit Hilfe des folgenden Formulars.


Hinweis: Sie können den Text in dieser Ausgabeliste markieren und mit STRG+C kopieren.

Hinweis:
Ist w eine Quadratzahl, also w = k^2, dann gibt es immer die Lösung w = 1 + ... + k + ... + 1.
Ist w von der Form 3 n + 1, so gibt es die Lösung w = n + (n+1) + n.
Ist w von der Form 5 n + 4, so gibt es die Lösung w = n + (n+1) + (n+2) + (n+1) + n.
Wenn 4*w-1 eine Primzahl ist, gibt es keine Darstellung als auf-/absteigende Summe.
Z.B. gibt es für w=8 keine Darstellung, weil 4*8-1 = 31 eine Primzahl ist.

Algorithmus, theoretischer Hintergrund:
Sei w die gewünschte Summe. Wir wollen sie in Summanden von n bis (n+k) aufteilen.
w = n + (n+1) + ... + (n+k-1) + (n+k) + (n+k-1) + ... + (n+1) + n bedeutet
w = n*(2k+1) + k*k.
Das Programm prüft alle k, beginnend von 1 und solange k^2 < w ist, ob (w-k^2)=0 mod (2k+1) ist.
Falls ja, ist eine Lösung gefunden mit n = (w-k^2)/(2k+1).

Wegen 4 w - 1 = (2k+1)*(4n+2k-1) könnte man auch nach Teilern von 4w-1 suchen.
Der kleinere Teiler wäre 2k+1.
Ist also 4w-1 = a*b mit a <= b, dann ist k=(a-1)/2, n=(b+1-2k)/4.
Sofern n ganzzahlig ist, ist das eine Lösung.
Falls 4w-1 viele kleine Primfaktoren enthält, wäre das eine schnellere Lösung.


Vergleiche auch OEIS, Folge A095808.

Zurück zur Hauptseite
f.d.I.v.: Alfred Heiligenbrunner; letzte Änderung: