Quadratzahlkriterium |
30.12.2015, 22:02 | montgrimpulo | Auf diesen Beitrag antworten » | ||
Quadratzahlkriterium 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. |
||||
31.12.2015, 12:11 | 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: |
||||
02.01.2016, 23:58 | 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 ? |
||||
03.01.2016, 18:08 | RavenOnJ | Auf diesen Beitrag antworten » | ||
RE: Quadratzahlkriterium
Wie wäre es mit "divide and conquer?". Müsste mit logarithmischer Komplexität gehen. |
||||
04.01.2016, 10:25 | 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 . |
||||
04.01.2016, 14:20 | RavenOnJ | Auf diesen Beitrag antworten » | ||
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. |
||||
Anzeige | ||||
|
||||
04.01.2016, 14:42 | HAL 9000 | Auf diesen Beitrag antworten » | ||
Das Heron-Verfahren ist ja auch Newton, angewandt speziell auf . |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|