Die Mathe-Redaktion - 22.06.2018 13:29 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
ListenpunktSchwätz / Top 15
ListenpunktWerde Mathe-Millionär!
ListenpunktAnmeldung MPCT Juli
ListenpunktFormeleditor fedgeo
Schwarzes Brett
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. Mitglieder können den Matheplanet-Newsletter bestellen, der etwa alle 2 Monate erscheint.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 529 Gäste und 21 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 MATHML in dieser Nachricht. Wenn Dein Text $-Zeichen enthält, die nicht LaTeX-Formeln begrenzen.
Deaktiviere Smilies in dieser Nachricht
Zeige die Signatur (Kann in 'Mein Profil' editiert werden.)
    [Abbrechen]
 
Beachte bitte die [Forumregeln]


Themenübersicht
blindmessenger
Aktiv
Dabei seit: 02.08.2016
Mitteilungen: 823
Herkunft: NRW
 Beitrag No.20, eingetragen 2018-03-09 12:33    [Diesen Beitrag zitieren]

Edit: Falscher Thread...



juergen007
Aktiv
Dabei seit: 17.08.2006
Mitteilungen: 2739
Herkunft: Braunschweig
 Beitrag No.19, eingetragen 2017-12-04 00:58    [Diesen Beitrag zitieren]
\(\begingroup\)
Ich bleibe hier mal bei diesem Thema, auch für meinen eigenen Einstieg.

Der kleine Satz des Fermat hat 2 äquivalente Aussagen:

1. <math>\displaystyle a^{p-1}\equiv 1{\pmod {p}</math> oder  
2. <math>\displaystyle a^{p}\equiv a{\pmod {p}</math>.

z.B.:<math>\displaystyle 5^2 =25 \equiv 1 \pmod {3}</math> und <math>5^3 = 125 \equiv 5 \pmod {3}</math> (wundert mich bisschen da ja <math>5^3 = 125 \equiv 2 \pmod {3}</math>...lass es aber so stehen)


Der kleine Satz des Fermat gilt nur für Primzahlexponenten!
Er kann mit Induktion über a bewiesen werden. Siehe wiki.
Die Basis kann jede ganze Zahl sein, auch negative.

Bsp:

<math>\displaystyle -3^{10} = 59049 \equiv 1 \pmod {11}</math> und <math>\displaystyle -3^{11} = -177147 \equiv -3 \pmod {11} (= 8 \pmod {11})</math>.

Als nächstes nehme ich eine höhere Primzahl, was der Taschenrechner hergab:
<math>\displaystyle a=2, p=n=101, 2^{100} = 1267650600228229401496703205376, \equiv 1 \pmod {101}</math> und <math>\displaystyle 2^{101} = 2535301200456458802993406410752 \equiv 2 \pmod {101}</math>.

Das ist klar da: <math>\displaystyle 2^{101} = 2 \cdot 2^{100}</math>.

Andere Basis 3:
<math>\displaystyle a = 3, p = 7, 3^{6} = 729 \equiv 1 \pmod {7}</math> oder <math>\displaystyle 3^{7} = 2187 \equiv 3 \pmod {7}</math>.

Das ist klar, da <math>\displaystyle 3^7 = 2187 = 3 \cdot 3^6</math>.
 
Hier also wie immer bei primen Exponenten: <math>\displaystyle a^{p} = x \equiv a \pmod {p}</math>, und <math>\displaystyle a^{p-1} = x \equiv 1 \pmod {p}</math>.
So, das war für Rechenliebhaber;)
aber:
<math>\displaystyle a^{p-1} = x \equiv 1 \pmod {p}</math> gilt auch für wenige andere Exponenten z.B. 341 zur Basis 2, obwohl 341 =11*31 composite ist.
Die Zahl <math>\displaystyle 2^{341-1}-1</math> ist durch 341 teilbar, obwohl 341 = 11 * 31 zusammengesetzt werden kann.
Man könnte jetzt 2^341 explzit ausrechnen.
Das habe ich gemacht:
2^341 = 4479489484355608421114884561136888556243290994469299069799978201927583742360321890761754986543214231552
Kann ich auf Wunsch auh für andere Basen und Exponenten berechnen.
Und diese Zahl ist modulo 341 = 2. Also ist 341 eine Fermatsche Pseudoprimzahl der Basis 2.
$c = $a->modPow($b, $c);  // C = A hoch B mod C.
Nochmal: 2 hoch 341 mod 341 = 2, 341 is Prim or pseudoprim, base 2   // C = A hoch B mod  C
Oder 2 hoch 340 = 2239744742177804210557442280568444278121645497234649534899989100963791871180160945380877493271607115776  mod 341 = 1.

Fazit: Die kleine Fermatformel gilt für alle Primzahlen aber eben auch für andere. Sie ist notwendig aber nicht hinreichend.
So, das ist nichts neues aber ich wollts mal verifizieren.
Danke

\(\endgroup\)

blindmessenger
Aktiv
Dabei seit: 02.08.2016
Mitteilungen: 823
Herkunft: NRW
 Beitrag No.18, eingetragen 2017-12-03 11:48    [Diesen Beitrag zitieren]
\(\begingroup\)
Man kann das auch noch etwas aufbohren indem zu diesem hier

Zahlen $k$ der Form

$k \ mod \ 4=3$

$2^{\frac{k-1}{2}} \ mod \ k=1$, $3^{\frac{k-1}{2}} \ mod \ k=1$ und $5^{\frac{k-1}{2}} \ mod \ k=1$

$2^{\lfloor log_2(k+1)\rfloor} \ mod \ k\ne 1$

eine Art Komplementärcode dazu nimmt:

Zahlen $k$ der Form

$k \ mod \ 4=1$

$((2k-1) \cdot 2^{\frac{k-1}{2}}) \ mod \ k=1$, $((2k-1) \cdot 3^{\frac{k-1}{2}}) \ mod \ k=1$ und $((2k-1) \cdot 5^{\frac{k-1}{2}}) \ mod \ k=1$

$2^{\lfloor log_2(k+1)\rfloor} \ mod \ k\ne 1$

Damit werden dann 1/8 der Primzahlen erwischt:

is(n) = (n%4==1 &&(2*n-1)* Mod(2, n)^(n\2)==1 &&(2*n-1)* Mod(3, n)^(n\2)==1 &&(2*n-1)* Mod(5, n)^(n\2)==1 && Mod(2, n)^logint(n+1, 2)!=1)||(n%4==3 &&Mod(2, n)^(n\2)==1 &&Mod(3, n)^(n\2)==1 && Mod(5, n)^(n\2)==1 && Mod(2, n)^logint(n+1, 2)!=1)
\(\endgroup\)

juergen007
Aktiv
Dabei seit: 17.08.2006
Mitteilungen: 2739
Herkunft: Braunschweig
 Beitrag No.17, eingetragen 2017-12-02 23:43    [Diesen Beitrag zitieren]
\(\begingroup\)
2017-12-02 22:13 - blindmessenger in Beitrag No. 16 schreibt:
de.wikipedia.org/wiki/Diskrete_Exponentialfunktion

Das habe ich auch erst nicht verstanden, aber ich denke das ist eine spezielle Power Mod Funktion...

Dein pari code:
Pari
is(n) = n%4==3 && Mod(2, n)^(n\2)==1 && Mod(3, n)^(n\2)==1 && Mod(5, n)^(n\2)==1 && Mod(2, n)^logint(n+1, 2)!=1


ja genau, in der php biginteger Bibliothek ist es die

function modPow($e, $n).

Das hilft dir jetztwohl auch nicht weiter, aber was ähnliches gibt es in vielen Sprachen...

PHP
<?php
	/**
	 * Performs modular exponentiation.
	 *
	 * Here's an example:
	 * <code>
	 * <?php
	 *    include('Math/BigInteger.php');
	 *
	 *    $a = new Math_BigInteger('10');
	 *    $b = new Math_BigInteger('20');
	 *    $c = new Math_BigInteger('30');
	 *
	 *    $c = $a->modPow($b, $c);
	 *
	 *    echo $c->toString(); // outputs 10
	 * ?>
	 * </code>
	 *
	 * @param Math_BigInteger $e
	 * @param Math_BigInteger $n
	 * @return Math_BigInteger
	 * @access public
	 * @internal The most naive approach to modular exponentiation has very unreasonable requirements, and
	 *     and although the approach involving repeated squaring does vastly better, it, too, is impractical
	 *     for our purposes.  The reason being that division - by far the most complicated and time-consuming
	 *     of the basic operations (eg. +,-,*,/) - occurs multiple times within it.
	 *
	 *     Modular reductions resolve this issue.  Although an individual modular reduction takes more time
	 *     then an individual division, when performed in succession (with the same modulo), they're a lot faster.
	 *
	 *     The two most commonly used modular reductions are Barrett and Montgomery reduction.  Montgomery reduction,
	 *     although faster, only works when the gcd of the modulo and of the base being used is 1.  In RSA, when the
	 *     base is a power of two, the modulo - a product of two primes - is always going to have a gcd of 1 (because
	 *     the product of two odd numbers is odd), but what about when RSA isn't used?
	 *
	 *     In contrast, Barrett reduction has no such constraint.  As such, some bigint implementations perform a
	 *     Barrett reduction after every operation in the modpow function.  Others perform Barrett reductions when the
	 *     modulo is even and Montgomery reductions when the modulo is odd.  BigInteger.java's modPow method, however,
	 *     uses a trick involving the Chinese Remainder Theorem to factor the even modulo into two numbers - one odd and
	 *     the other, a power of two - and recombine them, later.  This is the method that this modPow function uses.
	 *     {@link http://islab.oregonstate.edu/papers/j34monex.pdf Montgomery Reduction with Even Modulus} elaborates.
	 */
	function modPow($e, $n)
	{
		$n = $this->bitmask !== false && $this->bitmask->compare($n) < 0 ? $this->bitmask : $n->abs();
 
		if ($e->compare(new Math_BigInteger()) < 0) {
			$e = $e->abs();
 
			$temp = $this->modInverse($n);
			if ($temp === false) {
				return false;
			}
 
			return $this->_normalize($temp->modPow($e, $n));
		}
 
		switch ( MATH_BIGINTEGER_MODE ) {
			case MATH_BIGINTEGER_MODE_GMP:
				$temp = new Math_BigInteger();
				$temp->value = gmp_powm($this->value, $e->value, $n->value);
 
				return $this->_normalize($temp);
			case MATH_BIGINTEGER_MODE_BCMATH:
				$temp = new Math_BigInteger();
				$temp->value = bcpowmod($this->value, $e->value, $n->value, 0);
 
				return $this->_normalize($temp);
		}
 
		if ( empty($e->value) ) {
			$temp = new Math_BigInteger();
			$temp->value = array(1);
			return $this->_normalize($temp);
		}
 
		if ( $e->value == array(1) ) {
			list(, $temp) = $this->divide($n);
			return $this->_normalize($temp);
		}
 
		if ( $e->value == array(2) ) {
			$temp = new Math_BigInteger();
			$temp->value = $this->_square($this->value);
			list(, $temp) = $temp->divide($n);
			return $this->_normalize($temp);
		}
 
		return $this->_normalize($this->_slidingWindow($e, $n, MATH_BIGINTEGER_BARRETT));
 
		// is the modulo odd?
		if ( $n->value[0] & 1 ) {
			return $this->_normalize($this->_slidingWindow($e, $n, MATH_BIGINTEGER_MONTGOMERY));
		}
		// if it's not, it's even
 
		// find the lowest set bit (eg. the max pow of 2 that divides $n)
		for ($i = 0; $i < count($n->value); ++$i) {
			if ( $n->value[$i] ) {
				$temp = decbin($n->value[$i]);
				$j = strlen($temp) - strrpos($temp, '1') - 1;
				$j+= 26 * $i;
				break;
			}
		}
		// at this point, 2^$j * $n/(2^$j) == $n
 
		$mod1 = $n->copy();
		$mod1->_rshift($j);
		$mod2 = new Math_BigInteger();
		$mod2->value = array(1);
		$mod2->_lshift($j);
 
		$part1 = ( $mod1->value != array(1) ) ? $this->_slidingWindow($e, $mod1, MATH_BIGINTEGER_MONTGOMERY) : new Math_BigInteger();
		$part2 = $this->_slidingWindow($e, $mod2, MATH_BIGINTEGER_POWEROF2);
 
		$y1 = $mod2->modInverse($mod1);
		$y2 = $mod1->modInverse($mod2);
 
		$result = $part1->multiply($mod2);
		$result = $result->multiply($y1);
 
		$temp = $part2->multiply($mod1);
		$temp = $temp->multiply($y2);
 
		$result = $result->add($temp);
		list(, $result) = $result->divide($n);
 
		return $this->_normalize($result);
	}
 
 
\(\endgroup\)

blindmessenger
Aktiv
Dabei seit: 02.08.2016
Mitteilungen: 823
Herkunft: NRW
 Beitrag No.16, eingetragen 2017-12-02 22:13    [Diesen Beitrag zitieren]

de.wikipedia.org/wiki/Diskrete_Exponentialfunktion

Das habe ich auch erst nicht verstanden, aber ich denke das ist eine spezielle Power Mod Funktion...


juergen007
Aktiv
Dabei seit: 17.08.2006
Mitteilungen: 2739
Herkunft: Braunschweig
 Beitrag No.15, eingetragen 2017-12-02 21:13    [Diesen Beitrag zitieren]

war das nicht der Singularitätsbeweis von cyrix?
Das letzte meine ich aus a002326

oeis.org/A002326
 
"In other words, least m > 0 such that 2n+1 divides 2^m-1. "
ich bring da aber jetzt was durcheinander glaub ich und weiss auch nicht was du genau sagen willst.

ich weiss aber nicht, wie man dies fermatschen pseudoprimes der Basis 2 findet ohne irre exponenenten zu berechnen. oder in Tabellen zu schauen.
Grüsse




blindmessenger
Aktiv
Dabei seit: 02.08.2016
Mitteilungen: 823
Herkunft: NRW
 Beitrag No.14, eingetragen 2017-12-02 11:03    [Diesen Beitrag zitieren]
\(\begingroup\)
Ich habe nochmal ein bißchen rumgebastelt:

Zahlen $k$ der Form

$k \ mod \ 4=3$

$2^{\frac{k-1}{2}} \ mod \ k=1$, $3^{\frac{k-1}{2}} \ mod \ k=1$ und $5^{\frac{k-1}{2}} \ mod \ k=1$

$2^{\lfloor log_2(k+1)\rfloor} \ mod \ k\ne 1$

sind so gut wie prim...

Hier der Code:

(PARI) is(n) = n%4==3 && Mod(2, n)^(n\2)==1 && Mod(3, n)^(n\2)==1 && Mod(5, n)^(n\2)==1 && Mod(2, n)^logint(n+1, 2)!=1

Immerhin lassen sich hiermit ungefähr 1/16 der Primzahlen erfassen und die Wahrscheinlichkeit eine Pseudoprimzahl zu treffen liegt bei ca. 1:263 Mrd. Die ersten Pseudoprimzahlen (gleichzeitig Carmichael Zahlen) sind dann:

131314855918751, 23282264781147191, 70122000249565031, 104782993259720471, 583701149409931151, 870012810301712351,...

Auffällig bei den Zahlen ist, dass ausschließlich Primzahlen mit den Endungen 1 und 9 gefunden werden und dass die Pseudoprimzahlen  (die bis jetzt gefunden worden sind...) nur mit einer 1 am Ende auftreten. Das bedeutet, wenn man den Code erweitert und somit noch mit

$k \ mod \ 10\ne1$

einschränkt:

(PARI) is(n)=n%4==3 && n%10!=1&& Mod(2, n)^(n\2)==1 && Mod(3, n)^(n\2)==1 && Mod(5, n)^(n\2)==1 && Mod(2, n)^logint(n+1, 2)!=1

dann könnte man mal probieren ob überhaupt noch Pseudoprimzahlen gefunden werden... (Oder vielleicht beweisen, dass noch welche kommen müssen...)

Die Definition beruht auf einer Eigenschaften folgender Primzahlen $k$ oeis.org/A139035:

Es existiert ein kleinstes und ungerades $m$ der Form

$m=\frac{k-1}{2}$

so dass

$2^m \ mod \ k=1$
\(\endgroup\)

juergen007
Aktiv
Dabei seit: 17.08.2006
Mitteilungen: 2739
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: 885
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: 823
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
Senior
Dabei seit: 18.02.2016
Mitteilungen: 683
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: 2739
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: 823
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: 823
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: 885
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: 823
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
Senior
Dabei seit: 18.02.2016
Mitteilungen: 683
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: 823
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: 823
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
Senior
Dabei seit: 18.02.2016
Mitteilungen: 683
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: 823
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-2018 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]