Zahlenfolgen - Rekursive vs Explizite

10.10.2019, 17:53	MasterWizz	Auf diesen Beitrag antworten »
Zahlenfolgen - Rekursive vs Explizite Hey Leute Ich habe eine grundlegende Frage zur Darstellung von Zahlenfolgen. Ich weiß bereits, dass manche rekursive Zahlenfolgen keine explizite Gestalt haben. (1) Aber gilt das auch anders rum? Gibt es explizite Zahlenfolgen, die keine rekursive Darstellung haben? (2) Gibt es nachweislich Zahlenfolgen, die weder eine explizite, noch eine rekursive Darstellung haben? Liebe Grüße
10.10.2019, 18:03	Elvis	Auf diesen Beitrag antworten »
Primzahlen ? explizit ? bitte die kleinste hinschreiben, die mehr als eine Quintillion Ziffern hat rekursiv ? bitte die rekursive Definition aufschreiben, die es erlaubt, aus allen kleineren die nächstgrößere Primzahl zu berechnen
10.10.2019, 18:56	MasterWizz	Auf diesen Beitrag antworten »
Ja super! Primzahlen sind ein schönes Beispiel für eine Zahlenfolge, von der es keine Darstellung in expliziter und rekursiver Form gibt. Ist das eigentlich bewiesen oder kann es vielleicht sogar eine Darstellung geben, die wir nur nicht kennen? Und was würde eine Formel für alle Primzahlen für die Kryptographie bedeuten? Aber ich schweife ab haha. Wie siehts mit (1) aus? Falls eine explizite Darstellung bekannt ist. Kann daraus immer die zugehörige Darstellung gewonnen werden? EDIT: Glückwunsch zu 11k Beiträgen! Und vielen Dank für deine massive Hingabe in diesem Forum
10.10.2019, 19:29	Elvis	Auf diesen Beitrag antworten »
Es gibt Formeln für alle Primzahlen, das sind die ganzzahligen Primzahlpolynome in n Variablen vom Grad m. Hier ist ein Beispiel : http://www.aladin24.de/prim/ Das hilft nur nichts, weil beim einsetzen von Zahlen für die Variablen meistens negative Zahlen herauskommen, aber positive Ergebnisse sind Primzahlen und alle Primzahlen werden dargestellt. Wir haben also nur ein unlösbares Problem in natürlichen Zahlen durch ein unlösbares Problem in ganzen Zahlen ersetzt (trotzdem haben wir uns 197x gefreut, als wir das Spielzeug bekommen haben).
10.10.2019, 19:40	MasterWizz	Auf diesen Beitrag antworten »
Haha genial, wusste ich nicht! Also ist es theoretisch möglich alle Primzahlen damit zu berechnen, nur praktisch gibts Probleme. Nur noch mal kurz auf meine erste Frage zurück zu kommen: Falls eine explizite Darstellung bekannt ist. Kann daraus immer die zugehörige rekursive Darstellung gewonnen werden?
10.10.2019, 19:58	Elvis	Auf diesen Beitrag antworten »
Ich weiß es nicht. Ich müsste mal wieder ein paar Kapitel Berechenbarkeitstheorie lesen ...
Anzeige

10.10.2019, 20:06	MasterWizz	Auf diesen Beitrag antworten »
Kein Problem, jetzt hab ich einen Begriff nach dem ich suchen kann Vielen Dank für deine Zeit und deine Hilfe!

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »