Darstellungen als Summe aus Quadraten

02.02.2025, 19:33

Marcus.Bergk

Darstellungen als Summe aus Quadraten

Für ein Schulprojekt in Informatik/Mathe hab ich die Anzahl der Darstellungen einer ganzen positiven Zahl als Summe aus 2 bzw 3 ganzzahligen Quadraten gewählt. Die Null und gleiche Zahlen dürfen vorkommen. Für die Programmierung würde ich Python verwenden.

Für die Darstellung aus 2 Quadraten:
Gegeben ist eine Zahl N > 0.
N kann dann als Summe aus zwei Quadratzahlen dargestellt werden wenn in der Primfaktorzerlegung von N keine Primzahl p = 3 (mod 4) mit einem ungeraden Exponenten vorkommt.
Ansonsten lässt die Anzahl der möglichen Darstellungen aus der Primfaktorisierung mit der Formel 4 * (e_{1}+1) ... * (e_{n}+1) berechnen, wobei e_{n} für die Exponenten der Primzahlen p = 1 (mod 4) stehen. Für den Fall N = 10 heißt das 10 = 2 * 5^1 woraus folgt 4 * (1 + 1) = 8. Und die sind (1, 3), (1, -3), (-1, 3), (-1, -3) und jeweils in umgekehrter Reihenfolge.
Sollte N eine Zweierpotenz 2^k sein, dann ist das Ergebnis 4. Genauso auch für Primpotenzen p^2k mit p = 3 (mod 4) und k > 0.

Was ich bisher grob durchgerechnet hab, zeigt mir dass ich offensichtlich N nicht unbedingt von vornherein faktorisieren muss. Sondern wenn N = 3 (mod 4) ist, ist das Ergebnis 0. Oder hab ich hier etwas übersehen?

Für die Darstellung aus 3 Quadraten:
Hier gehe ich ähnlich vor wie für den Fall oben.
N = x^2 + y^2 + z^2, also N - x^2 = y^2 + z^2.
Wenn ich für 0 <= x <= sqrt(N) dann D = N - x^2 = y^2 + z^2 nach obigem Vorgehen berechne, addiere ich die einzelnen Ergebnisse für D zusammen und komme auf die Anzahl der Darstellungen als Summe aus 3 Quadratzahlen.
Wie es scheint, muss ich die Summe aber immer noch mit 2 multiplizieren, da ich für z.B. N = 75 auf 28 komme, es müssten aber 56 sein. Auch bei z.B. 51 komme ich im Ergebnis auf 24, obwohl es 48 sein müssten.

Kann man das so erstmal stehenlassen? Oder sind meine Überlegungen grundlegend falsch?

Vielen dank schonmal für eure Hilfe!

02.02.2025, 20:01

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Marcus.Bergk
wenn N = 3 (mod 4) ist, ist das Ergebnis 0. Oder hab ich hier etwas übersehen?

Das ist richtig. Die Umkehrung ist aber selbst für ungerade $\begin{eqnarray*} N \end{eqnarray*}$ nicht richtig:

D.h., aus $\begin{eqnarray*} N\equiv 1\bmod 4 \end{eqnarray*}$ kann nicht geschlossen werden, dass $\begin{eqnarray*} N \end{eqnarray*}$ als Summe zweier Quadratzahlen darstellbar ist - einfachstes Beispiel $\begin{eqnarray*} N=21=3\cdot 7 \end{eqnarray*}$ .

----------------------------------------------------------------------------------------------------

Was die Anzahl der Zerlegungen betrifft, kommt es natürlich drauf an, was genau du da zählen willst - beispielsweise bei zwei Summanden:

Willst du für $\begin{eqnarray*} N>0 \end{eqnarray*}$ die Anzahl aller Paare nichtnegativer Zahlen $\begin{eqnarray*} (x,y) \end{eqnarray*}$ mit $\begin{eqnarray*} N=x^2+y^2 \end{eqnarray*}$ bestimmen, oder nur die mit $\begin{eqnarray*} x\leq y \end{eqnarray*}$ ?

Man kann auch nicht oberflächlich sagen, dass die erstere Anzahl doppelt so groß wie die zweite ist, denn im Fall $\begin{eqnarray*} x=y \end{eqnarray*}$ darf man ein Paar nicht doppelt zählen - Beispiel:

$\begin{eqnarray*} N=50 \end{eqnarray*}$ hat 3 Lösungen gemäß erster Interpretation, aber nur 2 gemäß zweiter Interpretation.

Wobei man bei zwei Summanden noch relativ einfach ineinander umrechnen kann - bei drei Summanden $\begin{eqnarray*} N=x^2+y^2+z^2 \end{eqnarray*}$ ist das schon verzwickter...

Ob es überhaupt mit 3 Summanden funktioniert, darüber gibt der Drei-Quadrate-Satz Auskunft, aber das hast du ja inzwischen sicher auch in Erfahrung gebracht. Den Fall könnte man also im Skript extra behandeln, ohne unnötigen Suchaufwand.

02.02.2025, 20:48

Marcus.Bergk

Auf diesen Beitrag antworten »

Danke HAL9000!

Was den Divisionsrest angeht, hätte ich zunächst geprüft, ob bei Division durch 4 der Rest 3 bleibt. Bei geraden Zahlen müsste ich dafür alle Vorkommen von Faktor 2 entfernen und dann den ungeraden Rest prüfen. Für den Fall = 1 (mod 4) bleibt mir nichts übrig als zu faktorisieren.

Was die Zahlenpaare x und y angeht, kann auch x = y sein. Und da es sich um Quadrate handelt können x und y auch negativ werden. Deswegen hatte ich am Anfang geschrieben "Die Null und gleiche Zahlen dürfen vorkommen." Im Nachhinein war das sicher unvollständig, weil ja x und y auch negativ sein können.
Dazu auch das Beispiel mit N = 10. Für den Fall N = 9 = 3^2 bleiben demnach nur (0, 3), (0, -3), (3, 0), (-3, 0). Als Beispiel dass auch die Null vorkommt.

Zum Thema Summe aus 3 Quadratzahlen... Interessant zu sehen dass es da auch diese Ausnahme 4^a * (8b+7) gibt.

Und nochmal zum Biespiel 50: Hier komme ich auf 5^2 + 5^2 und 1^2 + 7^2.
Demnach sind die Paare (5, 5), (5, -5), (-5, 5), (-5, -5) und (1, 7), (1, -7), (-1, 7), (-1, -7), (7, 1), (7, -1), (-7, 1), (-7, -1). Also insgesamt 12. Wenn ich von der Grundformel 4 * (e1+1) * ... * (en+1) ausgehe, da 50 = 2 * 5^2 ist, berechne ich 4 * (2 + 1) = 12, da 5 der einzige Primfaktor p = 1 (mod 4) ist und der Exponent 2 ist.

Ich hoffe dass ich jetzt nicht an dir vorbeirede verwirrt

02.02.2025, 21:16

HAL 9000

Auf diesen Beitrag antworten »

Ah Ok, wusste nicht, dass du auch negative x,y einbeziehen willst. Das erhöht natürlich nochmal die Anzahl der Paare, aber auch nur dann genau um den Faktor 4, wenn N keine Quadratzahl ist...

Die ganzen Faktorisierungsbemühungen, und dann daraus die Anzahl der Zerlegungen zu berechnen, ist ja vor allem dann nötig, wenn $\begin{eqnarray*} N \end{eqnarray*}$ ziemlich groß ist (also ich sag mal 10 Dezimalstellen und mehr). Darunter könnte man ja sogar alles simpel mit Bruteforce abklappern, aber das ist vermutlich eine zu primitive, unerwünschte Vorgehensweise für euer Python-Projekt. Augenzwinkern

02.02.2025, 21:36

Marcus.Bergk

Auf diesen Beitrag antworten »

Über brute-force geht es bestimmt auch. Evtl könnte man das mit einer Hash-Tabelle bzw. Dictionary in Python bewerkstelligen. Ich wollte es aber mit einer Benutzereingabe koppeln wodurch Zahlen bis 2^32 möglich sind, evtl auch höher. Zumindest ist das der Plan. Bei Python muss ich mir keine Gedanken zu Überläufen machen. Ich kann mir aber vorstellen dass die Ergebnisse riesig werden. Wahrscheinlich ist bei Eingabe N = 10^10 die Zahl der Darstellungen als Summe aus 2 oder 3 Quadraten schon wesentlich größer als N selbst.

Ich versuche das mal in Python zu fassen. Ich hoffe das klappt Freude

03.02.2025, 10:28

Marcus.Bergk

Auf diesen Beitrag antworten »

Ich hab mal was programmiert. Mit Faktorisierung...

Für die Zweierpotenzen:

code:
1: 2: 3: 4:	def potenz2(n): # return n and not (n & (n - 1))

Für die Summe aus 2 Quadratzahlen:

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:

def summe2quadrate(n):
    #
    assert n == int(n) and n > 0

    if potenz2(n):          # Zweierpotenz?
        return 4

    while (n & 1) == 0:     # solange n gerade
        n >>= 1             # Faktor 2 entfernen

    if n % 4 == 3:          # vorzeitiges Abbruchkriterium
        return 0

    maxprim = math.isqrt(n)
    anzahl = 4
    for p in range(3, maxprim + 1, 2):  # ungerade Zahlen als Primfaktoren
        e = 0
        while n % p == 0:
            e += 1
            n //= p
        rest = p % 4
        if rest == 3 and (e & 1):       # wie vorzeitiges Abbruchkriterium
            return 0
        elif rest == 1:
            anzahl *= e + 1

    if n > 1:
        if n % 4 == 3:
            return 0
        else:
            anzahl *= 2

    return anzahl

Für die Summe aus 3 Quadratzahlen:

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:

def summe3quadrate(n):
    #
    assert n == int(n) and n > 0

    max_x = math.isqrt(n)
    grenze = int(max_x * max_x == n)    # bei Quadratzahlen die Wurzel ausschließen
    anzahl = 0
    for x in range(0, max_x+1-grenze):  # Obergrenze anpassen
        D = n - x*x
        anzahl += summe2quadrate(D)

    return anzahl << 1

Das funktioniert alles soweit, aber ich war überrascht. Die Ergebnisse werden nicht so groß wie ich dachte. Und bei Eingaben über 10^8 braucht Python schon fast mehrere Sekunden.

03.02.2025, 12:38

HAL 9000

Auf diesen Beitrag antworten »

Ich weiß nicht, inwieweit du gängige Python-Bibliotheken nutzen willst bzw. überhaupt darfst:

Z.B. bietet sympy.ntheory.factorint(n) direkt die Primfaktorzerlegung von $\begin{eqnarray*} n \end{eqnarray*}$ , und ist anscheinend auch für größere $\begin{eqnarray*} n \end{eqnarray*}$ noch ziemlich performant, im Vergleich zur eher simplen Herangehensweise "teste alle ungeraden Faktoren kleiner $\begin{eqnarray*} \sqrt{n} \end{eqnarray*}$ ".

P.S.: Deinen Code für die 3 Quadrate halte ich für falsch im Fall, dass der erste Summand gleich Null ist: Denn $\begin{eqnarray*} \pm 0 \end{eqnarray*}$ sind nicht zwei Varianten, sondern nur eine!

03.02.2025, 15:21

Marcus.Bergk

Auf diesen Beitrag antworten »

SymPy wäre tatsächlich eine Option und lässt sich bestimmt auch nutzen. Mein erster Gedanke war nur wegen der allgemeinen Nutzbarkeit auf externe Bibliotheken zu verzichten.

Bei den 3 Quadraten schaue ich nochmal drüber. Meine bisherigen Ergebnisse schienen richtig zu sein. Zumindest wenn ich sie mit oeis abgleiche. Oder ich hab für die Probe die falschen Zahlen gewählt.

03.02.2025, 15:50

HAL 9000

Auf diesen Beitrag antworten »

summe3quadrate(1) liefert bei dir Wert 8 - richtig wäre aber 6 :

$\begin{eqnarray*} (\pm 1)^2 + 0 + 0 = 0 + (\pm 1)^2 + 0 = 0 + 0 + (\pm 1)^2 \end{eqnarray*}$

03.02.2025, 16:08

Marcus.Bergk

Auf diesen Beitrag antworten »

Stimmt

da muss ich nochmal ran.

Vielen Dank!

03.02.2025, 17:58

HAL 9000

Auf diesen Beitrag antworten »

Basierend auf deinem Code sowie sympy wäre meine Variante

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:

import sympy

def summe2quadrate(n):
    if n < 0:
        return 0
    if n == 0:
        return 1
    while n & 1 == 0:
        n >>= 1
    if n % 4 == 3:
        return 0
    pf_dict = sympy.ntheory.factorint(n) 
    anzahl = 4
    for p in pf_dict:
        if p % 4 == 1:
            anzahl *= pf_dict[p]+1
        else:
            if pf_dict[p] & 1:
                return 0
    return anzahl

def summe3quadrate(n):
    if n > 0:
        while n & 3 == 0:
            n >>= 2
    if n & 7 == 7:
        return 0        
    anzahl = summe2quadrate(n)
    m = 0
    while n > 0:
        n -= (m << 1) + 1
        anzahl += summe2quadrate(n) << 1
        m += 1
    return anzahl

04.02.2025, 09:33

Marcus.Bergk

Auf diesen Beitrag antworten »

Wow

vielen Dank!!

Das muss ich gleich mal probieren

Neue Frage »

Antworten »

Darstellungen als Summe aus Quadraten

Verwandte Themen