Überlegungen zu Fakultäten und Primzahlen

01.08.2006, 22:02

akechi90

Überlegungen zu Fakultäten und Primzahlen

Ich bin im Laufe meiner Nachforschungen über Primzahlen über ein weiteres Problem gestolpert, sprich: eine neue Frage, die ich mir gestellt habe:

Gibt es unendlich viele Zahlen $\begin{eqnarray*} n \in \mathbb N \end{eqnarray*}$ , die folgende Teilungseigenschaft erfüllen:
$\begin{eqnarray*} n | \sum_{k=1}^{n-1}~k! \end{eqnarray*}$
Bisher konnte ich nur die Lösungen $\begin{eqnarray*} n=3 \end{eqnarray*}$ und $\begin{eqnarray*} n=9 \end{eqnarray*}$ finden.
Dennoch vermute ich, dass unendlich viele Zahlen die Forderung erfüllen.
Außerdem habe ich bereit herausgefunden, dass eine Zahl nur dann die Forderung erfüllen kann, wenn sie eine Primzahl ist oder wenn alle ihre Primfaktoren die Forderung erfüllen.

Im Übrigen bin ich auf einen weiteren "Primzahlgenerator" gestoßen, welcher für relativ viele Einsetzungen eine Primzahl liefert.
Sei p eine Primzahl.
Wann gilt folgendes:
$\begin{eqnarray*} ( \sum_{k=1}^{p-1}~k!) + p \end{eqnarray*}$ ist eine Primzahl.
Bisher ist es auf einige Primzahlen zugetroffen.

Nur kann ich meine Theorien einfach nicht überprüfen, solange ich kein gescheites Programm mit Primfaktorzerlegung und exaktem Ausrechnen von Fakultäten (Ungefähr 1000 Stellen wärn nicht schlecht) habe.
Gibt's da irgendwo geeignete Freeware, ich habe nämlich nicht viel Geld.

EDIT: Was die erste Vermutung angeht, habe ich nun auch die 11 gefunden. Ich vermute, dass die Vermutung für alle Potenzen einer Primzahl zutrifft, die die Bedingung erfüllen.

01.08.2006, 22:38

Dual Space

Auf diesen Beitrag antworten »

RE: Überlegungen zu Fakultäten und Primzahlen

Zitat:

Original von akechi90
Was die erste Vermutung angeht, habe ich nun auch die 11 gefunden. Ich vermute, dass die Vermutung für alle Potenzen einer Primzahl zutrifft, die die Bedingung erfüllen.

n=5?

01.08.2006, 22:45

akechi90

Auf diesen Beitrag antworten »

Ich habe erwähnt, dass es für Potenzen von allen denjenigen Primzahlen zutrifft, welche die Teilbarkeitsregel erfüllen.

01.08.2006, 22:51

Dual Space

Auf diesen Beitrag antworten »

Achso ... hab ich überlesen! Augenzwinkern

01.08.2006, 22:56

akechi90

Auf diesen Beitrag antworten »

Übrigens bin ich auch auf den relativ guten Primzahlgenerator $\begin{eqnarray*} (p-1)! + p \end{eqnarray*}$ für Einsetzungen von $\begin{eqnarray*} p \in \mathbb P \end{eqnarray*}$ gestoßen, da er Zahlen generiert, die nie durch die Zahlen 1 - p teilbar sind.

01.08.2006, 23:15

Auf diesen Beitrag antworten »

Zitat:

Original von akechi90
Ich vermute, dass die Vermutung für alle Potenzen einer Primzahl zutrifft, die die Bedingung erfüllen.

$\begin{eqnarray*} \sum_{k=1}^{3^m-1}~k! \equiv \sum_{k=1}^{8}~k! = 46233 \equiv 9\mod 27 \end{eqnarray*}$ für alle $\begin{eqnarray*} m\geq 3 \end{eqnarray*}$ , d.h.

$\begin{eqnarray*} \sum_{k=1}^{3^m-1}~k! \not\equiv 0\mod 3^m \end{eqnarray*}$ für alle diese $\begin{eqnarray*} m \end{eqnarray*}$

01.08.2006, 23:25

akechi90

Auf diesen Beitrag antworten »

Du hast jetzt aber auf der linken Seite $\begin{eqnarray*} m=2 \end{eqnarray*}$ gesetzt.
Und dann hast du die Summe modulo $\begin{eqnarray*} 3^3 \end{eqnarray*}$ untersucht, obwohl du sie modulo $\begin{eqnarray*} 3^2 \end{eqnarray*}$ hättest nehmen sollen...
Für 9 ist die Vermutung schon überprüft, und ich bin mir ihrer Richtigkeit bewusst.
Außerdem lautet die Teilbarkeitsregel im Fall $\begin{eqnarray*} n=9 \end{eqnarray*}$ :
$\begin{eqnarray*} 9 | \sum_{k=1}^{8}~k! \end{eqnarray*}$

Und die trifft zu!

EDIT: Sorry, jetzt seh ich deine Überlegung. OK, ich vergesse meinen Widerspruch! Hammer

01.08.2006, 23:28

Auf diesen Beitrag antworten »

Zitat:

Original von akechi90
Du hast jetzt aber auf der linken Seite $\begin{eqnarray*} m=2 \end{eqnarray*}$ gesetzt.

Du solltest mich besser kennen: unglücklich

$\begin{eqnarray*} k! \end{eqnarray*}$ ist für $\begin{eqnarray*} k\geq 9 \end{eqnarray*}$ durch $\begin{eqnarray*} 3\cdot 6\cdot 9 \end{eqnarray*}$ , also auch durch 27 teilbar, also kann man alle diese Summanden weglassen...

Mal off-topic: Du bist recht sprunghaft, hüpfst von einer Idee zur nächsten - OK, ein Privileg der Jugend. Hast du denn aber auch mal Durchhaltevermögen und stehst ein Problem bis zum Ende durch, z.B. das hier ?

01.08.2006, 23:38

akechi90

Auf diesen Beitrag antworten »

Ja, so bin ich halt ^^

Aber das Zahltheoretische Problem mit den rationalen Lösungen ist schon geklärt.

Nur das Primzahlproblem, das in der HöMa behandelt werden sollte, hat keine Antwort mehr bekommen, und seitdem bearbeite ich die Aufgabe mit meinem Rektor, der auch sehr begabt in Mathematik ist.

Na ja, ich hab halt auch sehr viele Ideen, und die muss ich irgendwo loswerden, wo sie anerkannt werden.

02.08.2006, 00:29

rain

Auf diesen Beitrag antworten »

werden du und dein math. können denn im unterricht nicht bewundert und anerkannt von mitschülern + lehrer?

02.08.2006, 08:13

Auf diesen Beitrag antworten »

Zitat:

Original von akechi90
Außerdem habe ich bereit herausgefunden, dass eine Zahl nur dann die Forderung erfüllen kann, wenn sie eine Primzahl ist oder wenn alle ihre Primfaktoren die Forderung erfüllen.

Das kann man auch genauer und erweiterter ausdrücken:

Zitat:

Sei

$\begin{eqnarray*} A(n) = \begin{cases} 1 & \;\mbox{falls}\; n \,\Big| \,\sum\limits_{k=1}^{n-1} ~ k!\\ 0 & \;\mbox{sonst} \end{cases} \end{eqnarray*}$

Dann ist $\begin{eqnarray*} A(n) \end{eqnarray*}$ eine zahlentheoretisch multiplikative Funktion, d.h., für teilerfremde $\begin{eqnarray*} u,v \end{eqnarray*}$ gilt $\begin{eqnarray*} A(uv)=A(u)A(v) \end{eqnarray*}$ .

Beispiel: Wie oben festgestellt, ist $\begin{eqnarray*} A(3)=A(11)=1 \end{eqnarray*}$ . Daher folgt auch $\begin{eqnarray*} A(33)=A(3)A(11)=1 \end{eqnarray*}$ .

Der Beweis der Aussage ist ziemlich einfach, und damit ist dann auch klar, dass nicht nur Primzahlen diese Eigenschaft haben.

Bleibt noch die Untersuchung von $\begin{eqnarray*} A(n) \end{eqnarray*}$ für Primzahlpotenzen, und da trifft zumindest folgendes zu:

Zitat:

Ist $\begin{eqnarray*} p \end{eqnarray*}$ Primzahl und $\begin{eqnarray*} A(p^r)=0 \end{eqnarray*}$ , dann gilt $\begin{eqnarray*} A(p^s)=0 \end{eqnarray*}$ für alle $\begin{eqnarray*} s\geq r \end{eqnarray*}$ .

Unmittelbare Folgerung ist natürlich, dass mit $\begin{eqnarray*} A(p^r)=1 \end{eqnarray*}$ dann auch $\begin{eqnarray*} A(p^s)=1 \end{eqnarray*}$ für alle $\begin{eqnarray*} s\leq r \end{eqnarray*}$ gilt.

EDIT: Es sieht so aus, als wären p=3 und p=11 die einzigen Primzahlen mit A(p)=1, zumindest ist A(p)=0 für alle Primzahlen 11<p<300000. In der Konsequenz wäre dann A(n)=1 nur für n=1,3,9,11,33,99 zutreffend.

02.08.2006, 12:59

akechi90

Auf diesen Beitrag antworten »

Wow!

Leider kann ich nicht so große Zahlen auf die Eigenschaft überprüfen.

Außerdem werd ich in der Schule von den Mitschülern nicht bewundert, die nehmen mich wegen meiner Begabung gar nicht ernst...

@ Arthur Dent: Übrigens, tut mir leid, dass ich die anderen zwei Sachen nicht zuende gemacht habe. Ich werde wahrscheinlich noch heute den Hauptansatz für den Beweis für meine erste Primzahlvermutung in der HöMa posten. Habe erst gestern Nacht die Erleuchtung gehabt!

03.08.2006, 10:30

Auf diesen Beitrag antworten »

RE: Überlegungen zu Fakultäten und Primzahlen

Zitat:

Original von akechi90
Leider kann ich nicht so große Zahlen auf die Eigenschaft überprüfen.

Doch, das kannst du auch - das ist alles nur eine Frage der Organisation der Berechnung:

Wir benötigen $\begin{eqnarray*} f(n) = \sum\limits_{k=1}^{n-1} k! \mod n \end{eqnarray*}$ .

Für $\begin{eqnarray*} g(n,m) = \frac{1}{m!}\sum_{k=m}^{n-1} ~ k! \mod n \end{eqnarray*}$ gilt $\begin{eqnarray*} f(n)=g(n,1) \end{eqnarray*}$ , wobei man $\begin{eqnarray*} g \end{eqnarray*}$ über die Rekursion

$\begin{eqnarray*} g(n,n)=0,\qquad g(n,m-1) = (m\cdot g(n,m)+1)\mod n\;\mbox{für}\;m=n,n-1,\ldots,2 \end{eqnarray*}$

in den Griff kriegt.

Und aus der konkreten Programmierperspektive: Ist $\begin{eqnarray*} n \end{eqnarray*}$ eine 32-Bit-Zahl, dann sind auch sämtliche $\begin{eqnarray*} f(n),g(n,m) \end{eqnarray*}$ nur 32 Bit groß, lediglich das Zwischenresultat $\begin{eqnarray*} m\cdot g(n,m)+1 \end{eqnarray*}$ geht mal kurz in den 64-Bit-Bereich.

Jedenfalls hat die Überprüfung aller Primzahlen kleiner 300000 mit dieser Methode ca. 140 Sekunden (3GHz-P4) gedauert.

EDIT: Mit einer Multithreading-Variante und aktiviertem Hyperthreading sogar nur 75 Sekunden - nahezu perfekte Skalierung aufgrund der wenigen Daten... Big Laugh

Neue Frage »

Antworten »

Überlegungen zu Fakultäten und Primzahlen

Verwandte Themen