Gleichung

Hallo hat einer ne Idee wie man das nachfolgend programmiertechnisch lösen könnte. Es geht mit Schleifen, aber die Laufzeit wäre ja extrem hoch.

Bestimme zwei natürliche Zahlen p und q, so dass p^2+q2 = 24642122;

Maxi

öhm... umformen?
p^2=diezahl-q2

Das ist schon klar. P und q sind aber unbekannte. Wenn man eine Schleife bis 24642122 laufen lässt und jede Zahl überprüft die p ergibt dauert das ewig

Maxi

kA obs da einen anderen weg gibt... du kannst musst ja sowieso erstmal nur bis wurzel(diezahl) gehen, dadrüber gehts sowieso nicht mehr

Help Please schrieb:

Hallo hat einer ne Idee wie man das nachfolgend programmiertechnisch lösen könnte. Es geht mit Schleifen, aber die Laufzeit wäre ja extrem hoch.

nö, nicht extrem.
wir konstruieren die quadratzahlen als summer ungerader zahlen. und lassen beim hochlaufen von p einfach q entgegenlaufen.
macht bei der initialisierung wohl einmal sqrt für q. und dann ca 5000 schleifendurchläufe, die innen nur vier += und -= haben und zwei sprünge.

aber es fühlt sich irgendwire an, als inge es noch schneller. hab ich da nicht mal sowas gelesen? ich denk drüber nach.

Das System ist im Reellen nicht eindeutig, also gibts eine Abhängigkeitsgleichung zwischen p und q, in diesem Fall

q = sqrt(2462122 - p^2)

Damit ist q < sqrt(2462122). Also lässt man q von floor(sqrt(2462122)) = 1569 nach unten laufen, bis 2462122 - q^2 eine Quadratzahl ist. In diesem Fall haben wir Glück und gleich das erste Paar passt, also ist

19^2 + 1569^2 = 24642122

Ok. Danke für die Hilfe

http://www.alpertron.com.ar/4SQUARES.HTM
(sorry, ist ein wenig viel, für ein so einfach aussehenden problem. vielleicht doch die schleife nehmen).

Und was ist wenn ich alle Zahlen (z.B. 3479 und 3541 sind ja auch Lösungen) ermitteln will. Dann ist die letzte Lösung ja nicht so komfortabel.
@volkars2: wie meinst du das. Kannst du dich vielleicht ein bischen anders ausdrücken?

Help Please schrieb:

Und was ist wenn ich alle Zahlen (z.B. 3479 und 3541 sind ja auch Lösungen) ermitteln will. Dann ist die letzte Lösung ja nicht so komfortabel.
@volkars2: wie meinst du das. Kannst du dich vielleicht ein bischen anders ausdrücken?

int n=2462122;
int dp=1;
int p=1;
while(p<n){
   cout<<p<<'\n;
   dp+=2;
   p+=dp;
}

das hier gibt die quadratzahlen bis sqrt(n) aus.
ohne multiplikationen.

und dann dachte ich an sowas wie

//ungetestet, nur so reingetippt, hoffentlich ist die idee erkennbar. 
int n=2462122;
int p=1;
int dp=1;
int q=sqrt(n);
int dq=q*q-(q-1)*(q-1)+2;//der deutlichkeit halber so, geht viel schneller//
//aber wir haben die binomischen formeln vergessen
while(p<n){
   do{
      dq-=2;
      q-=dq;
   }while(p+q>n);
   if(p+q==n)
      cout<<p<<' '<<q<<'\n;
   dp+=2;
   p+=dp;
}