Millionär durch Primzahlenformel?
-
Wer hat denn in diesem Thread recht:
-
Primzahl schrieb:
Wer hat denn in diesem Thread recht:
Kann man so nicht sagen. Da fehlt die genaue Definition von "Formel". Ich würde jedenfalls nicht behaupten, dass Formel != Algorithmus ist, ohne erstmal zu definieren, was ich eigentlich mit "Formel" meine.
Man kann ja schreiben (als "Formel"):
wobei $$\pi(k)$$ die Anzahl der Primzahlen kleiner oder gleich k ist. Das ist natürlich ziemlich sinnlos.
-
Du meinst mit "wieviel Geld ist damit zu machen" oder mit "Formel != Algorithmus"?
-
Blue-Tiger schrieb:
Du meinst mit "wieviel Geld ist damit zu machen" oder mit "Formel != Algorithmus"?
Eigentlich meine ich den ganzen Thread.
Der Link der auf das letzte Posting leitet war etwas unglücklich gewählt.
-
Christoph schrieb:
Primzahl schrieb:
Wer hat denn in diesem Thread recht:
Kann man so nicht sagen. Da fehlt die genaue Definition von "Formel". Ich würde jedenfalls nicht behaupten, dass Formel != Algorithmus ist, ohne erstmal zu definieren, was ich eigentlich mit "Formel" meine.
Man kann ja schreiben (als "Formel"):
wobei $$\pi(k)$$ die Anzahl der Primzahlen kleiner oder gleich k ist. Das ist natürlich ziemlich sinnlos.
Wie wärs mit: Eine Formel ist ein Algorithmus mit O(1)?
-
Mr.Fister schrieb:
Wie wärs mit: Eine Formel ist ein Algorithmus mit O(1)?
Das wäre auf jeden Fall eine mögliche Definition.
Andererseits möchte man vielleicht auch sowas als "Formel" zulassen:
\begin{align*}\text{L\"osung} = x^2\end{align*}
Wenn x eine natürliche Zahl ist, die im Computer explizit dargestellt wird, dann ist x^2 nicht in O(1) implementierbar.edit: OK, hängt davon ab, welche Operationen man mit dem Groß-O zählt. Du zählst primitive Rechenoperationen wohl als O(1), dann gilt mein Beispiel natürlich nicht.
-
Mr.Fister schrieb:
Wie wärs mit: Eine Formel ist ein Algorithmus mit O(1)?
Ungünstig. Dann kann man nämlich keine Reihenentwicklungen oder so verwenden.
-
Der gesuchte Begriff heißt effizienter Algorithmus.
-
Was heißt effizient?
-
effizient ist polynomiell
-
was soll denn überhaupt eingabe und ausgabe sein
Vorschlag Eingabe: Primzahl, Ausgabe: nächsthöhere Primzahl und das effizient
-
oder noch besser
Eingabe: n
Ausgabe: n-te Primzahlund das O(1)
ach keine ahnung
sorry für spam
-
_ schrieb:
oder noch besser
Eingabe: n
Ausgabe: n-te PrimzahlJa, genau so.
Ich geb 51233 ein und bekomme die 51233. Primzahl.
Zur Definition was eine Formel ist würde ich sagen:
Eine Formel enthält keine Schleifen.Damit kann man einen Algorithmus sehr gut von einer Schleife abgerenzen.
-
Das ist eine sinnlose Definition:
- Sie sagt nur, was eine Formel _nicht_ sein soll. Ist ein Weihnachtsgeschenk eine Formel? Mist, eine Schleife dran, aber du verstehst worauf ich hinauswill?
- Man kann jeden Algorithmus ohne Schleifen formulieren.
- Viele Dinge, die man als Laie eindeutig als Formel bezeichnen würde, enthalten bei geeigneter Interpretation des Begriffs Schleifen. Was ist 3 plus 4? Naja, man zählt viermal eins zu 3 dazu und bekommt 7. Was ist 3 mal 4? Was ist 3 hoch 4? Was ist mit durch unendliche Reihen definierten Funktionen wie der Sinusfunktion?
-
Bashar schrieb:
- Man kann jeden Algorithmus ohne Schleifen formulieren.
Gut, dann ist die Definition eines Algorithmus eben, daß er aus Schleifen mit Bedinungen und somit Abzweigungen besteht.
-
Primzahl schrieb:
Bashar schrieb:
- Man kann jeden Algorithmus ohne Schleifen formulieren.
Gut, dann ist die Definition eines Algorithmus eben, daß er aus Schleifen mit Bedinungen und somit Abzweigungen besteht.
Gram-Schmidt-Orthonormalisierung enthält keine Schleifen mit Bedingungen. Ist aber ganz klar ein Algorithmus
-
Ok, der Primzahltest liegt in P. Dann muss man nur noch eine obere Schranke des Suchraums festlegen, der hoffentlich polynomiell von der Eingabegroesse (n-te Primzahl) abgeleitet werden kann und probiert dann alle durch ... tatatata polynomieller Algorithmus fuer die n-te Primzahl.
-
knivil schrieb:
Dann muss man nur noch eine obere Schranke des Suchraums festlegen, der hoffentlich polynomiell von der Eingabegroesse (n-te Primzahl) abgeleitet werden kann
Sicher? Zwischen 0 und x liegen etwa x/ln(x) primzahlen. ist da die inverse noch polynomiell?
