Archiv verlassen und diese Seite im Standarddesign anzeigen : Suche Matheprogramm für sehr lange Zahlen
Fussabtreter
2004-04-03, 19:10:40
Kann mir da jemand helfen?
Die Aufgabe lautet 991*n^2+1=q n€N
Wobei q=Quadratzahl ist (1,4,9,16 usw.)
Nicht mal der Ti-92 von Texas Instruments bekommt das gebacken.
2. Aufagabe:
Und dann gibt es noch ein Problem:
Ist ein Rechteck durch n Geraden in Teilgebiete zerlegt, so lässt es sich mit 2 Farben so färben, dass benachbarte Gebiete verschiedene Farben haben.
Es sollen nur 2 Farben verwendet werden.
Kann es jemand wiederlegen? Oder beweisen?
Thx for help!
Stone2001
2004-04-03, 19:28:14
Original geschrieben von Fussabtreter
Kann mir da jemand hlefen?
Die Aufgabe lautet 991*n^2+1=q n€N
Wobei q=Quadratzahl ist (1,4,9,16 usw.)
Nicht mal der Ti-92 von Texas Instruments bekommt das gebacken.
hmm, reichen 64 bit Integer nicht aus?
Ich würde das Problem per Brute-Force lösen lassen (sofern überhaupt lösbar).
Original geschrieben von Fussabtreter
2. Aufagabe:
Und dann gibt es noch ein Problem:
Es sollen nur 2 Farben verwendet werden.
Kann es jemand wiederlegen? Oder beweisen?
Thx for help!
Interessantes Problem. Ich würde mal spontan sagen, das es möglich ist. (Ein Beweis per Induktion ist dann sicherlich möglich, vielleicht komme ich nachher mal dazu den zu probieren...)
Fussabtreter
2004-04-03, 19:59:32
Zu Problem 2
Ich würd nach probieren sagen das es immer möglich ist.
Dachte auch schon an Induktion leider bekomm ich die Gleichung nicht ganz zusammen.
Zu Problem 1.
Der Ti-92 kommt nach ner halben Stunde nicht zum Ergebnis.
Unser Leher meinte, dass wir im Inet nach Programmen suchen sollen, die so viele Stellen rechnen können.
Stone2001
2004-04-03, 20:01:59
Original geschrieben von Fussabtreter
Zu Problem 2
Ich würd nach probieren sagen das es immer möglich ist.
Dachte auch schon an Induktion leider bekomm ich die Gleichung nicht ganz zusammen.
Zu Problem 1.
Der Ti-92 kommt nach ner halben Stunde nicht zum Ergebnis.
Unser Leher meinte, dass wir im Inet nach Programmen suchen sollen, die so viele Stellen rechnen können.
zu 2.) Kommt mir bekannt vor ;)
zu 1.) 64bit Integer sollten eigentlich fürs erste reichen. (Leider meint Java gerade die ganze Zeit, das long und int nur 32 bit groß sind ??? )
Fussabtreter
2004-04-03, 20:04:39
Sry zu 1
Kann nicht programmieren oder sonster was in die Richtung...
Stone2001
2004-04-03, 20:37:56
Zu 1.)
Ja, es ist lösbar! Und 64 bit reichen aus!
n : 24637357
q : 601536365705939960
Ist eine korrekte Lösung!
Ich liebe "Brute-Force"!
Fussabtreter
2004-04-03, 22:58:44
q ist aber laut Ti-92 keine Quadratzahl!
Sliver21
2004-04-03, 23:18:40
Stimmt, q ist keine Quadratzahl.
q^0,5 ~ 775587754,9999999580962956280814
Stone2001, anscheinend läuft dein Bruteforce-Programm nicht genau genug.
Stone2001
2004-04-03, 23:20:28
Original geschrieben von Fussabtreter
q ist aber laut Ti-92 keine Quadratzahl!
Wirklich? Wenn ich diese Zahl in meinen Taschenrechner eingebe, dann bekomme ich genau 775587755 als Antwort!
OK, ich habs gereade nochmal mit den Windows-Calc nochmals gegen geprüft. Und ich muß sagen, da war die Rechengenauigkeit wohl etwas zu klein. Denn wenn ich obige Zahl quadriere, bekomme ich eine um 65 größere Zahl!
Tja, das selbe ist den Primzahlsuchern auch schon passiert. Oops.
EDIT: Ich glaube, dann werden die dreisig anderen Werte wohl auch nicht ganz stimmen.
Stone2001
2004-04-03, 23:48:07
OK, ich hab den Algorithmus gerade nochmal ein wenig angepasst. Und jetzt liefert er mir unter 2^31 -1 keine korrekte Lösung. :(
Frank
2004-04-04, 00:08:04
Original geschrieben von Fussabtreter Suche Matheprogramm für sehr lange Zahlen
Dann würd ich spontan eines aus der Palette Mathematica, Maple oder Matlab nehmen. Spontan davon Maple - dürfte man am einfachsten als Uni...usw - Lizenz bekommen.
Aqualon
2004-04-04, 03:51:09
package mathetest;
import java.math.*;
import java.util.*;
import java.io.*;
public class GleichungBruteForce {
//Main-Methode
public static void main(String[] args) {
long k1 = 991;
long k2 = 1;
BigInteger big = new BigInteger(1024, new Random());
BigInteger big_q = new BigInteger(1024, new Random());
BigInteger big_n = new BigInteger(30, new Random());
BigDecimal big_d = new BigDecimal(0);
//Näherungswert für sqrt(991)
big_d=big_d.valueOf(314801524,7);
big_d=big_d.add(big_d.valueOf(773943876,16));
big_d=big_d.add(big_d.valueOf(143704559,16));
System.out.println("Anfangswert n: " + big_n);
while(true) {
big = big_n;
big = big.pow(2);
big = big.multiply(big.valueOf(k1));
big = big.add(big.valueOf(k2));
//Umwandeln von big_n in BigDecimal-Wert
BigDecimal big_n_d = new BigDecimal(big_n);
for (big_q = big_d.multiply(big_n_d).toBigInteger(); big_q.equals(big_q); big_q=big_q.add(big.valueOf(k2))) {
if (big_q.pow(2).compareTo(big) == 0) {
System.out.println("q:" + big);
System.out.println("n:" + big_n);
System.exit(0);
}
if (big_q.pow(2).compareTo(big) == 1) {
System.out.println("break");
break;
}
}
big_n = big_n.add(big_n.valueOf(k2));
}
}
}
big_n ist dabei n, big_q ist sqrt(q) und big ist das Ergebnis der Gleichung 991*n^2+1
Edit2: Quellcode nochmal abgändert, Problem der quadratischen Annäherung per BigDecimal gelöst.
Aqua
Fussabtreter
2004-04-04, 14:22:26
Mal dumm frag?
Wie bekomm ich den Script zum laufen?
Wenn ich mich recht erinnere ist die Zahl größer Quadmillionen
Weiß aber nicht mehr genau.
Aqualon
2004-04-04, 16:23:31
EDIT: Hab das Problem der Annäherung gelöst, jetzt heisst es nur noch warten ;)
Hab den Code nochmal geändert, aber ich hab grundsätzlich ein großes Problem damit.
Die Feststellung, ob big eine Quadratzahl ist, dauert eindeutig zu lange. Wurzelziehen aus BigInteger-Werten ist nicht möglich, deswegen mache ich die for-Schleife mit der Annäherung von big_q² an big. Problem dabei ist, dass der Minimal-Wert mit dem ich die Schleife anfangen kann 31*big_n ist.
Der wirklich brauchbare Anfangswert wäre sqrt(991)*big_n, was aber nicht möglich ist, da ich nur Integer-Werte verarbeiten kann. Das Ergebnis ist, dass er pro big_n viel zu lange benötigt, um die quadratische Annäherung durchzuführen. In der Form ist das Programm also praktisch nahezu unbrauchbar.
Ich bräuchte also eine Möglichkeit big_q am Anfang der Schleife auf einen Wert möglichst nahe an sqrt(991)*big_n zu bringen. Aber leider fällt mir da momentan keine Möglichkeit ein.
@Fussabtreter: Das Programm ist in Java geschrieben und kann mit einem aktuellen JDK übersetzt und ausgeführt werden. Wenn ich eine bessere Möglichkeit zur quadratischen Annäherung habe, kann ich auch die class-Datei hochladen, dann wird nur die JRE (Java Runtime Environment) benötigt.
Aqua
HellHorse
2004-04-04, 16:37:49
Mein Java Bruteforce Vorschlag.
public class Bigmath {
public static void main(String[] args) {
boolean found = false;
long sqrtq = 1l;
long q = 1l;
long n = 0l;
long nsquare = 1l;
long border = 3037000500l;
long leftside;
long diff;
long time = System.currentTimeMillis();
while (Math.max(sqrtq, n) <= border) {
leftside = 991l*nsquare+1l;
diff = leftside - q;
if (diff > 0l) {
++n;
nsquare = n * n;
} else if (diff < 0l) {
++sqrtq;
q = sqrtq * sqrtq;
} else {
found = true;
break;
}
}
time = System.currentTimeMillis() - time;
if (found) {
System.out.println("found solution n: "+n+" q: "+q);
} else {
System.out.println("no solution found");
}
System.out.println("time used: "+time+" ms");
}
}
Verwendet longs statt BigInteger.
Hat bis jetzt ausser n = 0 und q = 1 nichts schlaues geliefert (läuft seit morgens um acht).
Mal schauen, ob der gcc an longlong Freude hat.
Wenn ich mich recht erinnere ist die Zahl größer Quadmillionen
long geht bis 9.22337204 × 10^18, würde das reichen?
Der Code, den ich vorher gepostet habe, war ziemlich doof. Hoffentlich ist's jetzt besser.
Fussabtreter
2004-04-04, 16:48:16
Schonmal ein großen Dank an euch für die Mühe :up:
Ein mist das unser Mathelehrer ein Doktortitel hat.
Der macht öfter mal sowas mit uns und freut sich wenn es keiner schafft...
Er meinte zu dieser Aufgabe nur. Schaut mal Internet nach nem Matheprogramm dann geht das ganz schnell....
Die Zahl hat glaub ich 24 Stellen (weiß es aber nicht genau)
Hat denn jemand ne Idee für das 2 Farben-Problem?
Aqualon
2004-04-04, 16:55:33
Original geschrieben von Fussabtreter
Die Zahl hat glaub ich 24 Stellen (weiß es aber nicht genau)
Hat n 24 Stellen oder q? Falls n so groß ist, kann ich den Startwert für das Programm um einiges nach oben setzen.
Aqua
q = 379516400906811930638014896080
Eine Pellsche Gleichung.
ups
q = 379516400906811930638014896080^2 = 144032698557259999607886110560755362973171476419973199366400
Frank
2004-04-04, 16:59:19
Original geschrieben von Fussabtreter
Ein mist das unser Mathelehrer ein Doktortitel hat.
Der macht öfter mal sowas mit uns und freut sich wenn es keiner schafft...das erklärt jetzt einiges. Hab mal die Aufgabe mir grad angeschaut und eines ist klar: reines BruteForce kann kaum die Lösung sein. Ich lass mir grad ein paar Grundaussagen von Zahlentheorie durch den Kopf wandern ... letztendlich stinkt das ja schon förmlich danach.
edit:
Original geschrieben von Gast
Eine Pellsche Gleichung. ahhh
danke :)
Sliver21
2004-04-04, 17:17:10
Schau mal, hier ist ein ähnliches Problem: http://www.wissenschaft-online.de/abo/spektrum/archiv/5330
Aqualon
2004-04-04, 17:40:45
Und wie löst man nun so Pellsche Gleichungen? BruteForce ist in dem Zahlenbereich wirklich keine Lösung.
Aqua
Original geschrieben von Aqualon
Und wie löst man nun so Pellsche Gleichungen?mit der Kettenbruchentwicklung von sqrt(991)
Fussabtreter
2004-04-04, 18:41:39
danke "Gast" für die Lösung
Aber so richtig zurecht komm ich mit dem Text nicht.
Kannst du mal bitte erklären mit welchen Hilfsmittel du das gerechnet und eingegeben hast. Würde mich echt mal interessieren.
Stone2001
2004-04-04, 18:50:24
Original geschrieben von Gast
q = 379516400906811930638014896080
Eine Pellsche Gleichung.
Ich glaube, jetzt überlassen wir dieses Problem den Zahlentheoretikern ;) !
http://www.ams.org/notices/200202/fea-lenstra.pdf
Fussabtreter
2004-04-04, 19:34:23
Ach du **** Glaub unser Mathe Lehrer dreht ein bissel am Rad.
Sowas kann man doch niemals ohne Hilfe lösen..."sucht nach nem Matheprogramm....."
Aber danke Gast für die Infos
aber kannst du die Formel die du genommen hast mal in kurzform posten
Original geschrieben von Fussabtreter
aber kannst du die Formel die du genommen hast mal in kurzform posten ich kenne keine Formel, nur einen Algorithmus. Kurz und nicht ganz korrekt:
Kettenbruchentwicklung: sqrt(991) = [a0, |a1,...a_r,2*a0|] (das zwischen || ist die Periode).
der Zähler und Nenner von [a0, a1,...a_r,2*a0] sind dann das Lösungspaar.
Fussabtreter
2004-04-04, 20:09:05
Achso nagut trotzdem danke...
Hast du beruflich bzw. im Studium mit Mathe zu tun?
Aqualon
2004-04-04, 20:51:08
Original geschrieben von Stone2001
Ich glaube, jetzt überlassen wir dieses Problem den Zahlentheoretikern ;) !
Wo rohe Kräfte sinnlos walten, fällt mir da gerade zu meinem Programm ein ;)
Das Problem ist mir jetzt auch eindeutig zu hoch.
Aqua
Aqualon
2004-04-04, 20:54:11
Original geschrieben von Fussabtreter
Hat denn jemand ne Idee für das 2 Farben-Problem?
Dürfen sich die Geraden schneiden?
Aqua
Stone2001
2004-04-04, 22:35:33
Original geschrieben von Aqualon
Dürfen sich die Geraden schneiden?
Wenn sich die Geraden nicht schneiden dürfen, ist die ganze Aufgabe trivial! Dann hat man n parallele Geraden und dann kann, ganz einfach, die einzelnen Felder alternierend färben.
EDIT: Im Prinzip ist der Beweise nicht weiter wild. Ich gehe mal davon aus, das sich die Aufgabe per Induktion beweisen läßt. Der Induktionsanfang ist recht einfach. (Wir haben ein Rechteck und teilen das jetzt durch eine Gerade, die Färbung stellt kein Problem dar) Der Induktionsschluß dagegen ist 'etwas' heftig. Man muß jetzt, wenn wir bereists n Gerade haben und eine neue hinzufügen, alle Möglichkeiten durchgehen, wie die Gerade auf die n vorher treffen kann. (Also z.B. alle Geraden treffen sich in einem Punkt)
Original geschrieben von Aqualon
Wo rohe Kräfte sinnlos walten, fällt mir da gerade zu meinem Programm ein ;)
Das Problem ist mir jetzt auch eindeutig zu hoch.
Aqua
Unterschreib!
Brute-Force ist dort gut genug, wo die Zeit, die man braucht, einen besseren Algorithmus zu schreiben, die Zeit für die Berechnung übersteigt! (Darunter fallen die meisten einmaligen Berechnungen) Das sich das Problem, durch das treiben von Mathematik, recht einfach lösen läßt, sollte man halt vorher wissen.
Aqualon
2004-04-04, 23:08:10
...
Aqua
Edit: Mir ist gerade aufgefallen, dass es immer n+1 neue Felder gibt, also sind meine Überlegungen von eben hinfällig.
Stone2001
2004-04-04, 23:18:31
EDIT: Aussage nicht allgemeingültig, ziehe sie daher zurück!
Frank
2004-04-05, 01:18:28
Original geschrieben von Fussabtreter
Aber danke Gast für die Infos
aber kannst du die Formel die du genommen hast mal in kurzform posten Kurzform kaum - aber hier ein sehr gut verständliches PDF:
http://hometown.aol.com/jpr2718/pell.pdf
und hier mal für dein Beispiel ausgeführt:
http://rcswww.urz.tu-dresden.de/~fh468638/temp/PQAlgorithmus.doc
(Maple Worksheet)
http://rcswww.urz.tu-dresden.de/~fh468638/temp/PQ.mws
Fussabtreter
2004-04-05, 13:51:16
Supi thx Frank!
Jetzt wird es schon etwas klarer. Aber eins noch muss D (991 in dem Fall) immer zwischen 980 und 1005 liegen?
Zu Problem 2... mhh am liebste wäre mir ein Fall wo es net klappt da brauch ma dann nix beweisen :D
Ma Offtopic/ haben heute bei dem Lehrer Klausur geschrieben, nicht mal "der Beste" im Kurs hat es geschafft Zeitlich und Fachlich..../
On Topic werd morgen mal nen anderen Mathelehrer dazu fragen.
Das mit den 2 Farben geht immer. Das nennt man auch Binary Space Partitioning (-> BSP Trees), und der Beweis ist ganz einfach. Man betrachtet die Geraden als gerichtet, womit die Gerade die Ebene in einen Teil "rechts der Gerade" und einen "links der Gerade" teilt. Nun kann man für jeden Punkt der Ebene zählen wie oft er links einer Gerade (nur unterschiedliche Geraden) liegt. Ist die Anzahl gerade, nutzt man Farbe 1, ist sie ungerade, nimmt man Farbe 2. Da man bei angrenzenden Feldern immer eine Gerade überspringen muss, somit bei dieser Gerade von rechts nach links oder andersrum wechselt, muss dabei auch die Farbe wechseln.
Frank
2004-04-05, 16:15:47
Original geschrieben von Fussabtreter
Jetzt wird es schon etwas klarer. Aber eins noch muss D (991 in dem Fall) immer zwischen 980 und 1005 liegen?
Das waren lediglich ein paar Beispiele. Bei dem einen Fall mit dem Sonnengott war D ja glaub ich 61. Letztendlich also beliebig - darf halt bloß selbst keine Quadratzahl sein - logisch.
Fussabtreter
2004-04-07, 14:01:29
Hat schon jemand ne Gleichung für 2 gefunden.
Der Mathelehre wollte/konnte mir nicht weiter helfen....:(
vBulletin®, Copyright ©2000-2024, Jelsoft Enterprises Ltd.