Quadratzahlkriterium

Neue Frage »

montgrimpulo Auf diesen Beitrag antworten »
Quadratzahlkriterium
Meine Frage:
Gibt es eine Methode oder Kriterium zur Erkennung von ganzen Quadratzahlen ohne die Wurzel zu ziehen, oder eine Primzahlzerlegung durchzuführen? Wenn ja, welche oder welches ?

Meine Ideen:
Wir wissen, dass die Endziffer von ganzen Quadratzahlen nie 2 oder 3 oder 7 oder 8 sein kann.
Elvis Auf diesen Beitrag antworten »

Subtrahiere sukzessive die endliche Reihe 1+3+5+7+9+...+(2m+1) .
Wenn nicht 0 herauskommt, ist die gegebene Zahl n keine Quadratzahl. Wenn 0 herauskommt, ist n ein Quadrat.
Beispiel : 15,14,11,6,-1 . 16,15,12,7,0 . 15 ist kein Quadrat, 16 ist ein Quadrat.

Beweise durch vollständige Induktion:
montgrimpulo Auf diesen Beitrag antworten »
Quadratzahlkriterium
Antwort an Elvis:

Die beschriebene Methode erfordert [sqrt(n)] Rechenschritte.
Bei der Zahl 123456790123456790123456790123456787654320987654320987654320987654321
wären es zB
11111111111111111111111111111111111
Iterationen.

Gibt es vielleicht eine elegantere Methode ?
RavenOnJ Auf diesen Beitrag antworten »
RE: Quadratzahlkriterium
Zitat:
Original von montgrimpulo


Gibt es vielleicht eine elegantere Methode ?


Wie wäre es mit "divide and conquer?". Müsste mit logarithmischer Komplexität gehen.
HAL 9000 Auf diesen Beitrag antworten »

Man könnte auch schlicht das Heronverfahren in der Integer-Variante durchführen, d.h. .

Ein geeigneter Startwert wäre eine Zahl mit ungefähr der halben Stellenzahl. Bei n=123456790123456790123456790123456787654320987654320987654320987654321 mit 69 Stellen wäre das etwa mit den dann folgenden Iterationswerten





,

keine Änderung mehr. Und nun noch die Überprüfung von .
RavenOnJ Auf diesen Beitrag antworten »

Zitat:
Original von HAL 9000
Man könnte auch schlicht das Heronverfahren in der Integer-Variante durchführen, d.h. .

Ein geeigneter Startwert wäre eine Zahl mit ungefähr der halben Stellenzahl.


Genau so was hatte mir vorgeschwebt als ich von ,,divide and conquer" schrieb, eine Art Newton für ganze Zahlen. Das Heronverfahren war mir allerdings entfallen bzw. nicht in meinem Gedächtnis. Freude
 
 
HAL 9000 Auf diesen Beitrag antworten »

Das Heron-Verfahren ist ja auch Newton, angewandt speziell auf .
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »