Vier kwadraten
-
- Berichten: 632
Vier kwadraten
Lagrange: elk natuurlijk getal kan geschreven worden als de som van vier kwadraten. (of soms minder termen. 0^2 mag.)
Bestaat er een algoritme om die vier kwadraten te vinden? Zo ja, hoe werkt die?
Bestaat er een algoritme om die vier kwadraten te vinden? Zo ja, hoe werkt die?
- Berichten: 2.906
Re: Vier kwadraten
Gewoon: alle mogelijkheden één voor één uitproberen tot je het juiste viertal gevonden hebt.
Dit waarschijnlijk niet het beste of meest efficiënte algoritme, maar het is in elk geval duidelijk dat dit algoritme bestaat.
Dit waarschijnlijk niet het beste of meest efficiënte algoritme, maar het is in elk geval duidelijk dat dit algoritme bestaat.
- Berichten: 2.906
Re: Vier kwadraten
Hier heb je een voorbeeld in Java:
Code: Selecteer alles
static int[] run(int valueToTest) {
for(int i=0; i<Double.POSITIVE_INFINITY; i++) {
for(int j=0; j<=i; j++) {
for(int k=0; k<=j; k++) {
for(int l=0; l<=k; l++) {
if(i*i + j*j + k*k + l*l == valueToTest) {
return new int[] {i,j,k,l};
}
}
}
}
}
return null; /*this can never happen.*/
}
- Berichten: 4.320
Re: Vier kwadraten
Ik weet weinig tot van Java.
Maar het zoeken van een reeks kan gestopt worden als de wortel uit G wordt overschreden.
Dan wordt het algoritme eindig en vindt men ook alle mogelijkheden.
Een formule om ze te vinden lijkt niet nog niet gevonden,
wel een formule om het aantal mogelijkheden te bepalen.
https://de.wikipedia.org/wiki/Vier-Quadrate-Satz
Maar het zoeken van een reeks kan gestopt worden als de wortel uit G wordt overschreden.
Dan wordt het algoritme eindig en vindt men ook alle mogelijkheden.
Een formule om ze te vinden lijkt niet nog niet gevonden,
wel een formule om het aantal mogelijkheden te bepalen.
https://de.wikipedia.org/wiki/Vier-Quadrate-Satz
-
- Berichten: 463
Re: Vier kwadraten
Mogelijk heb je hier genoeg aan (= mogelijk is dit voldoende efficient):
Het is een combinatie van Math-E-Mad-X en tempelier, met daaraan toegevoegd:
- als i ≥ j ≥ k ≥ l, dan hebben elk ook een ondergrens waar we boven kunnen blijven
- de laatste variabele hoef je alleen te testen op al dan niet kwadraat zijn
- begin het zoeken steeds bij de grootste waarde, dan heb sneller succes
Mocht je aan 1 oplossing per n voldoende hebben, dan kan je vooraf eerst kwadraten uit n delen:
als n = k^2 * m
en m = a^2 + b^2 + c^2 + d^2
dan is
n = k^2 * m = k^2 * (a^2 + b^2 + c^2 + d^2) = (ka)^2 + (kb)^2 + (kc)^2 + (kd)^2
Code: Selecteer alles
Lagrange(n)
for(i=floor(sqrt(n)); i>=floor(sqrt(n/4)); i--)
m=n-i^2
for(j=floor(sqrt(m)); j>=floor(sqrt(m/3)); j--)
t=m-j^2
for(k=floor(sqrt(t)); k>=floor(sqrt(t/2)); k--)
if(issquare(t-k^2))
return/print (i, j, k, sqrt(t-k^2))
- als i ≥ j ≥ k ≥ l, dan hebben elk ook een ondergrens waar we boven kunnen blijven
- de laatste variabele hoef je alleen te testen op al dan niet kwadraat zijn
- begin het zoeken steeds bij de grootste waarde, dan heb sneller succes
Mocht je aan 1 oplossing per n voldoende hebben, dan kan je vooraf eerst kwadraten uit n delen:
als n = k^2 * m
en m = a^2 + b^2 + c^2 + d^2
dan is
n = k^2 * m = k^2 * (a^2 + b^2 + c^2 + d^2) = (ka)^2 + (kb)^2 + (kc)^2 + (kd)^2