Die Mathe-Redaktion - 22.11.2017 06:18 - Registrieren/Login
Auswahl
Schwarzes Brett
Wartet darauf, dass Fragensteller die Antwort(en) liest2017-11-22 00:56 bb <
Matheformeln mit MathML
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden oder den Newsletter bestellen.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 424 Gäste und 3 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 

Antworte auf:  Primzahltest von blindmessenger
Forum:  Zahlentheorie, moderiert von: Wauzi

[Zur Forum-Gliederung] [Wie man Fragen beantwortet]

  Alle registrierten Mitglieder können Mitteilungen schreiben.
Benutzername:
Passwort:
Nachricht-Icon:                     
                    
                  
Nachricht:


 
 


Eingabehilfen (JavaScript): [Link extern intern] [$$] [MathML?]
[fed-Bereich] [LaTeX-inline] [LaTeX-display] [hide-Bereich] [Quelltext [num.]][?]
 Zeige Vorschau      Schreibe im fedgeoFormeleditor oder mit Latex.

Wähle Smilies für Deine Nachricht: :-) :-( :-D ;-) :-0 8-) :-? :-P :-|
Optionen: Deaktiviere HTML in dieser Nachricht
Deaktiviere Smilies in dieser Nachricht
Zeige die Signatur (Kann in 'Mein Profil' editiert werden.)
    [Abbrechen]
 
Beachte bitte die [Forumregeln]


Themenübersicht
juergen007
Aktiv
Dabei seit: 17.08.2006
Mitteilungen: 2075
Herkunft: Braunschweig
 Beitrag No.13, eingetragen 2017-11-20 13:13    [Diesen Beitrag zitieren]

Hi,
2 Matrizen sind noch kein Matratze oder;)
Mal ernsthaft:

Aus deinem Artikel arxiv.org/abs/1608.00862.
Deine Single matrizen sind offenbar Primitivwurzeln zu 2 wie in oeis.org/A001122 : Primes with primitive root 2.
Inverted mirrormatritzen sind, denke ich nach oeis.org/A139035 Primes of the form 4*k+3 with primitive root -2.
Ungerade nicht primes braucht man nicht zu betrachten. Sie haben keinen "Rang"
Ich schau mir das nochmal an.


Gruss
Jürgen




MartinN
Aktiv
Dabei seit: 05.08.2016
Mitteilungen: 759
Herkunft: Bayern
 Beitrag No.12, eingetragen 2017-11-11 00:33    [Diesen Beitrag zitieren]

Allgemein suchst du doch Formeln der Form:
<math>B^{\frac{an+b}{c}} \equiv k \mod n; B,a,b,c,k \in \IZ; n \in \IN</math>

Und diese sollen nur für prime n gültig sein.

Nun könnte man sich mal überlegen, ob jede solche Formel, wenn sie eine prime Lösung <math>n = p</math> besitzt, dann auch zusammengesetzte ("pseudoprime" ?) Lösungen besitzen muss...

Denn dann wäre es aussichtslos überhaupt eine Formel dieser Art zu finden, die nur Primzahlen als Lösungen besitzt ;)
Aber dazu mach ich mir morgen oder so mal Gedanken :D


blindmessenger
Aktiv
Dabei seit: 02.08.2016
Mitteilungen: 668
Herkunft: NRW
 Beitrag No.11, eingetragen 2017-11-10 23:27    [Diesen Beitrag zitieren]

Auch bei den letzten Tests ergeben sich "Pseudos"...

Für den Test 2 ist das 476971...

:-(


Primentus
Aktiv
Dabei seit: 18.02.2016
Mitteilungen: 495
Herkunft: Deutschland
 Beitrag No.10, eingetragen 2017-11-10 22:36    [Diesen Beitrag zitieren]

2017-11-09 22:51 - blindmessenger in Beitrag No. 5 schreibt:
Immerhin ist es eine Pseudoprimzahl mit einer 5 am Ende die man dann schnell aussortieren kann...

Aber ich fürchte es werden wohl auch noch andere auftauchen mit anderen Endungen...

Kann das aber im Moment nicht überprüfen...

Ich hab mir mal alle Zahlen bis 1.000.000 angeschaut.
Ja - dabei treten neben der 74665 tatsächlich noch folgende weitere Nicht-Primzahlen auf:
252601, 253241, 280601, 390937, 635401, 818201, 976873

Wie man sieht sind es hier andere Endziffern - in dem Fall welche, die für Primzahlen typisch wären.

LG Primentus


juergen007
Aktiv
Dabei seit: 17.08.2006
Mitteilungen: 2075
Herkunft: Braunschweig
 Beitrag No.9, eingetragen 2017-11-10 20:29    [Diesen Beitrag zitieren]

wg. des <math>\frac{n-1}{4}</math> im Exponent muessen in brauchbaren n die  2n-1 Zahlen ja auch 8k+1 Zahlen sein.
also <math>p=41 \Rightarrow 2p-1=81  \equiv 1 \mod 8, *2^{10} = 82944 \mod 41 \equiv 1</math>
Und auch  <math>p=41 \equiv 1 \mod 8, 2^{10} \equiv -1 \mod 41</math>.
Interessant sind die Kommentare in oeis.org/A070179

mehr konnt ich mich auch noch nicht damit beschaeftigen, und was ist so interessant grade an dieser Primreihe? Oder an der nach deiner Formel?
Man muss sich nochmal in deine Mirror philosofie denken.
Gruessli
J




[Die Antwort wurde nach Beitrag No.7 begonnen.]


blindmessenger
Aktiv
Dabei seit: 02.08.2016
Mitteilungen: 668
Herkunft: NRW
 Beitrag No.8, eingetragen 2017-11-10 20:28    [Diesen Beitrag zitieren]

Man soll ja nie aufgeben... ;-)

Aus weiteren Musterüberlegungen ergibt sich folgendes:

Muster 1:



Muster 2:



Aus diesen beiden Mustern lassen sich zwei Tests entwickeln, weil beide Muster immer Primzahlen abbilden.

Die Muster können über 4 immer gleich angeordnete teilbare Zahlen erkannt und somit berechnet werden... (Die Zahlen auf die die Pfeile zeigen...)

Test 1 (Beispiel 13):

<math>(2^{n-1})\mod\ n=1</math>

<math>((2n-1)\cdot(2^\frac{n-1}{2}))\mod\ n=1</math>

<math>(4 \cdot \lceil \frac{1}{4}n}\rceil}-2)\mod\ n=1</math>

<math>(2^{(\frac{n+1}{2})}+\lfloor \frac{3}{4}n \rfloor \cdot2^{ \frac{n+1}{2}+1)})\mod\ n=1</math>


Test 2 (Beispiel 19):

<math>(2^{n-1})\mod\ n=1</math>

<math>((2n-1)\cdot(2^\frac{n-1}{2}))\mod\ n=1</math>

<math>(4 \cdot \lceil \frac{3}{4}n}\rceil}-2)\mod\ n=1</math>

<math>(2^{(\frac{n+1}{2})}+\lfloor \frac{1}{4}n \rfloor \cdot2^{ \frac{n+1}{2}+1)})\mod\ n=1</math>

Fermatsche Pseudoprimzahlen bis 30000 habe ich überprüft...




blindmessenger
Aktiv
Dabei seit: 02.08.2016
Mitteilungen: 668
Herkunft: NRW
 Beitrag No.7, eingetragen 2017-11-10 15:49    [Diesen Beitrag zitieren]

Ja das habe ich mich die ganze Zeit schon gefragt...

Gut erklärt...


MartinN
Aktiv
Dabei seit: 05.08.2016
Mitteilungen: 759
Herkunft: Bayern
 Beitrag No.6, eingetragen 2017-11-10 14:21    [Diesen Beitrag zitieren]

Wenn du Modulo n rechnest, dann kannst du auch das 2n streichen ;)
Denn die 2er Potenz ist wegen dem positiven Exponenten entweder irrational (dann wird der Rest bei Division durch eine ganze Zahl eh nie ganzzahlig) oder ganzzahlig (dann aber auch 2n mal eine ganze Zahl immer durch n teilbar).

Somit lässt sich deine Formel reduzieren zu:
<math>2^\frac{n-1}{4} \equiv -1 \mod n</math>


Diese Formel kommt auch in der von dir zitierten Folge vor... die alle Primzahlen p der Form 8k+1 enthält, welche dieser Formel genügen ^^
(warum 8k+1 und nicht "nur" 4k+1 weiß ich aber nicht :S)


blindmessenger
Aktiv
Dabei seit: 02.08.2016
Mitteilungen: 668
Herkunft: NRW
 Beitrag No.5, eingetragen 2017-11-09 22:51    [Diesen Beitrag zitieren]

Immerhin ist es eine Pseudoprimzahl mit einer 5 am Ende die man dann schnell aussortieren kann...

Aber ich fürchte es werden wohl auch noch andere auftauchen mit anderen Endungen...

Kann das aber im Moment nicht überprüfen...


Primentus
Aktiv
Dabei seit: 18.02.2016
Mitteilungen: 495
Herkunft: Deutschland
 Beitrag No.4, eingetragen 2017-11-09 22:47    [Diesen Beitrag zitieren]

Oh, sorry - tatsächlich. Das hätte ich nicht für möglich gehalten, dass da auch Nicht-Primzahlen auftauchen. Die ersten 47 Zahlen waren alle "astrein" und ich hatte nur bis 20000 gerechnet.

Ja, das sind natürlich immer keine Beweise, wenn man nur endlich viele Zahlen betrachtet. Trotzdem bin ich etwas überrascht.

LG Primentus


blindmessenger
Aktiv
Dabei seit: 02.08.2016
Mitteilungen: 668
Herkunft: NRW
 Beitrag No.3, eingetragen 2017-11-09 22:15    [Diesen Beitrag zitieren]

So... Man sollte die Leute auch mal zu ende rechnen lassen... ;-)

Es hat sich gezeigt, dass sich doch Pseudo-Primzahlen darunter befinden... :-(

Die erste ist 74665...


blindmessenger
Aktiv
Dabei seit: 02.08.2016
Mitteilungen: 668
Herkunft: NRW
 Beitrag No.2, eingetragen 2017-11-09 19:08    [Diesen Beitrag zitieren]

Hallo Primemtus,
Danke für die Berechnung...

Ja, das ist schon interessant...

Vielleicht lassen sich noch mehr solcher markanten Punkte in den Mustern finden...


Primentus
Aktiv
Dabei seit: 18.02.2016
Mitteilungen: 495
Herkunft: Deutschland
 Beitrag No.1, eingetragen 2017-11-08 23:01    [Diesen Beitrag zitieren]

Hallo blindmessenger,

zu Deinem Muster kann ich nichts sagen, aber:

2017-11-08 22:23 - blindmessenger im Themenstart schreibt:
<math>(2n-1)\cdot(2^\frac{n-1}{4})\mod\ n=1</math>

Ich habe die Vermutung, dass man mit dieser Formel auf folgende Primzahlen stößt:

oeis.org/A070179

Ja, diese Formel erzeugt offensichtlich alle Primzahlen dieser OEIS-Folge und zwar lückenlos und ohne andere Primzahlen zu erzeugen. Habe alle 47 Werte überprüft, und die Folge geht natürlich noch weiter.

LG Primentus


blindmessenger
Aktiv
Dabei seit: 02.08.2016
Mitteilungen: 668
Herkunft: NRW
 Themenstart: 2017-11-08 22:23    [Diesen Beitrag zitieren]

Hallo,
durch meine ganzen Collatzdurchmusterungen bin ich auf eine vielleicht interessante Formel gestoßen.

Ich hatte ja mal von Matrixpattern geschrieben:

LinkMatrix Pattern

Bei bestimmten Mustern den sogenannten Primzahlen Rang 2

oeis.org/A115591

gibt es zwei verschiedene Muster... Einmal die Spiegelmatrizen:

<math>
IP(M_O(17))=
\begin{pmatrix}
fr&fr&fr&fr&fr&fr&fr&\textcolor{red}{15}\\
\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}\\
\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}\\
\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}\\
\textcolor{red}{1}&fr&fr&fr&fr&fr&fr&fr\\
\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}\\
fr&\textcolor{red}{3}&fr&fr&fr&fr&fr&fr\\
fr&fr&\textcolor{red}{7}&fr&fr&fr&fr&fr\\
\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}\\
fr&fr&fr&fr&fr&fr&\textcolor{red}{143}&fr\\
fr&fr&fr&fr&fr&\textcolor{red}{79}&fr&fr\\
\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}\\
fr&fr&fr&fr&\textcolor{red}{47}&fr&fr&fr\\
\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}\\
\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}\\
\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}\\
fr&fr&fr&\textcolor{red}{31}&fr&fr&fr&fr\\
\end{pmatrix}
</math>

Und einmal die invertierten Spiegelmatrizen:

<math>
\setcounter{MaxMatrixCols}{12}
IP(M_O(23))=
\begin{pmatrix}
fr&fr&fr&fr&fr&fr&fr&fr&fr&fr&\textcolor{red}{89}\\
fr&fr&\textcolor{red}{1}&fr&fr&fr&fr&fr&fr&fr&fr\\
\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}\\
\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}\\
fr&fr&fr&fr&fr&\textcolor{red}{25}&fr&fr&fr&fr&fr\\
\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}\\
fr&fr&fr&\textcolor{red}{9}&fr&fr&fr&fr&fr&fr&fr\\
\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}\\
\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}\\
\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}\\
\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}\\
\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}\\
fr&fr&fr&fr&fr&fr&fr&fr&fr&\textcolor{red}{1113}&fr\\
fr&fr&fr&fr&fr&fr&fr&fr&\textcolor{red}{601}&fr&fr\\
fr&\textcolor{red}{5}&fr&fr&fr&fr&fr&fr&fr&fr&fr\\
fr&fr&fr&fr&fr&fr&fr&\textcolor{red}{345}&fr&fr&fr\\
\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}\\
\textcolor{red}{3}&fr&fr&fr&fr&fr&fr&fr&fr&fr&fr\\
\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}\\
fr&fr&fr&fr&fr&fr&\textcolor{red}{217}&fr&fr&fr&fr\\
fr&fr&fr&fr&\textcolor{red}{57}&fr&fr&fr&fr&fr&fr\\
\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}\\
\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}&\textcolor{blue}{fr}\\
\end{pmatrix}
</math>

Rang 2 Muster sind immer Primzahlen.

Nun habe ich mir mal überlegt ob man nicht markante Punkte in diesen Mustern einfach berechnen kann und somit auch Primzahlen besser berechnen kann.

Es zeigt sich folgendes:

Aus dem Muster Rang 2 ergibt sich folgende notwendige Bedingung:

<math>2^\frac{n-1}{2}\mod\ n=1</math>

Leider trifft das auch auf Zahlen zu die keine Primzahlen sind. Z.B. auf ein Teil der fermatschen Pseudoprimzahlen:

341,561,...

Nun gibt es aber noch einen weiteren markanten Punkt der Muster Rang 2.

Wenn ein Rang 2 Muster also nicht invertiert spiegelsymmetrisch ist, sondern normal spiegelsymmetrisch, dann ist hierfür eine weitere notwendige Bedingung:

<math>(2n-1)\cdot(2^\frac{n-1}{4})\mod\ n=1</math>

Ich habe die Vermutung, dass man mit dieser Formel auf folgende Primzahlen stößt:

oeis.org/A070179

Mag jemand etwas dazu schreiben?


 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2017 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]