www.wikidata.de-de.nina.az

Fastprimzahl Eine n displaystyle n oder auch n displaystyle n ter Ordnung ist eine natürliche Zahl deren Primfaktorzerle

Fastprimzahl

Eine -Fastprimzahl oder auch Fastprimzahl -ter Ordnung ist eine natürliche Zahl, deren Primfaktorzerlegung aus genau Primzahlen besteht, wobei mehrfache Primteiler entsprechend oft gezählt werden. Da alle natürlichen Zahlen größer eins aus Primfaktoren zusammengesetzt sind, ist jede natürliche Zahl zugleich auch eine Fastprimzahl. Fastprimzahlen zweiter Ordnung (also die Produkte von genau zwei Primzahlen) nennt man auch Semiprimzahlen.

Fastprimzahlen bewegen sich zwischen den Polen der unteilbaren Primzahlen und der maximal teilbaren hochzusammengesetzten Zahlen und schließen dabei beide mit ein.

Der Norweger Viggo Brun führte den Begriff um 1915 zur Verallgemeinerung von Primzahlen ein, um einen neuen Ansatz für ungelöste Primzahlprobleme zu finden.

Definition Bearbeiten

Sei und mit Primzahlen . Dann heißt Fastprimzahl -ter Ordnung, wobei gilt. Die Zahlenfolge für ein festes wird auch mit bezeichnet. Die Wohldefiniertheit folgt aus der Eindeutigkeit der Primfaktorzerlegung für alle natürlichen Zahlen.

Dieses Konzept kann problemlos auf die ganzen Zahlen und beliebige ZPE-Ringe verallgemeinert werden.

Beispiele und Werte Bearbeiten

Beispiele:

  • ist eine Fastprimzahl erster Ordnung („Primzahl“).
  • ist eine Fastprimzahl zweiter Ordnung („Semiprimzahl“).
  • ist eine Fastprimzahl vierter Ordnung.
  • ist eine Fastprimzahl zehnter Ordnung.
  • ist eine Fastprimzahl zwanzigster Ordnung.
Die ersten zwölf Fastprimzahlen erster bis zwanzigster Ordnung
01. Ordnung 2 3 5 7 11 13 17 19 23 29 31 37 … Folge A000040 in OEIS
02. Ordnung 4 6 9 10 14 15 21 22 25 26 33 34 … Folge A001358 in OEIS
03. Ordnung 8 12 18 20 27 28 30 42 44 45 50 52 … Folge A014612 in OEIS
04. Ordnung 16 24 36 40 54 56 60 81 84 88 90 100 … Folge A014613 in OEIS
05. Ordnung 32 48 72 80 108 112 120 162 168 176 180 200 … Folge A014614 in OEIS
06. Ordnung 64 96 144 160 216 224 240 324 336 352 360 400 … Folge A046306 in OEIS
07. Ordnung 128 192 288 320 432 448 480 648 672 704 720 800 … Folge A046308 in OEIS
08. Ordnung 256 384 576 640 864 896 960 1296 1344 1408 1440 1600 … Folge A046310 in OEIS
09. Ordnung 512 768 1152 1280 1728 1792 1920 2592 2688 2816 2880 3200 … Folge A046312 in OEIS
10. Ordnung 1024 1536 2304 2560 3456 3584 3840 5184 5376 5632 5760 6400 … Folge A046314 in OEIS
11. Ordnung 2048 3072 4608 5120 6912 7168 7680 10368 10752 11264 11520 12800 … Folge A069272 in OEIS
12. Ordnung 4096 6144 9216 10240 13824 14336 15360 20736 21504 22528 23040 25600 … Folge A069273 in OEIS
13. Ordnung 8192 12288 18432 20480 27648 28672 30720 41472 43008 45056 46080 51200 … Folge A069274 in OEIS
14. Ordnung 16384 24576 36864 40960 55296 57344 61440 82944 86016 90112 92160 102400 … Folge A069275 in OEIS
15. Ordnung 32768 49152 73728 81920 110592 114688 122880 165888 172032 180224 184320 204800 … Folge A069276 in OEIS
16. Ordnung 65536 98304 147456 163840 221184 229376 245760 331776 344064 360448 368640 409600 … Folge A069277 in OEIS
17. Ordnung 131072 196608 294912 327680 442368 458752 491520 663552 688128 720896 737280 819200 … Folge A069278 in OEIS
18. Ordnung 262144 393216 589824 655360 884736 917504 983040 1327104 1376256 1441792 1474560 1638400 … Folge A069279 in OEIS
19. Ordnung 524288 786432 1179648 1310720 1769472 1835008 1966080 2654208 2752512 2883584 2949120 3276800 … Folge A069280 in OEIS
20. Ordnung 1048576 1572864 2359296 2621440 3538944 3670016 3932160 5308416 5505024 5767168 5898240 6553600 … Folge A069281 in OEIS

Eigenschaften Bearbeiten

  • Jede Primzahl ist eine Fastprimzahl der Ordnung 1, jede zusammengesetzte Zahl ist eine Fastprimzahl der Ordnung 2 oder höher. Fastprimzahlen dritter Ordnung, sofern diese aus 3 verschiedenen Primfaktoren bestehen, nennt man auch sphenische Zahlen.
  • Die Vereinigung der bilden eine Zerlegung der natürlichen Zahlen.
  • Jede Fastprimzahl -ter Ordnung ist das Produkt von Fastprimzahlen der Ordnungen mit , z. B.: Das Produkt der 3-Fastprimzahl 12 und der 4-Fastprimzahl 40 ergibt die 7-Fastprimzahl 480. Für gibt es solcher möglichen Zerlegungen, wobei die Stirling-Zahlen zweiter Art bezeichnet.
  • Da es für die Null keine mögliche Primfaktorzerlegung gibt, ist sie keine Fastprimzahl -ter Ordnung.
  • Der Eins wird das leere Produkt als Primfaktorzerlegung zugewiesen. Entsprechend kann sie definitionskonform als Fastprimzahl 0-ter Ordnung bezeichnet werden.
  • Sei die Anzahl der positiven ganzen Zahlen kleiner gleich mit genau Primteilern (die nicht unbedingt verschieden sein müssen). Dann gilt:
  • Jede genügend große gerade Zahl lässt sich als die Summe einer Primzahl und einer Fastprimzahl zweiter Ordnung darstellen.
    Diese Aussage hat Ähnlichkeit mit der Goldbachschen Vermutung, wurde 1978 von Chen Jingrun bewiesen und nennt sich Satz von Chen.
  • Es gibt unendlich viele Primzahlen, sodass eine 2-Fastprimzahl ist.
    Diese Aussage hat Ähnlichkeit mit der Vermutung über Primzahlzwillinge und wurde ebenfalls von Chen bewiesen.

Anwendungen Bearbeiten

Fastprimzahlen zweiter Ordnung, also Produkte zweier Primzahlen, finden in der Kryptographie Anwendung.

Weblinks Bearbeiten

Literatur Bearbeiten

  • Władysław Narkiewicz: The Development of Prime Number Theory. From Euclid to Hardy and Littlewood. Springer, Berlin u. a. 2000, ISBN 3-540-66289-8.
  • Hans Riesel: Prime Numbers and Computer Methods for Factorization. Birkhäuser, Boston/Basel/Stuttgart 1985, ISBN 3-7643-3291-3.
  • David M. Bressoud: Factorization and Primality Testing. Springer, New York u. a. 1989, ISBN 0-387-97040-1.
  • Paulo Ribenboim: The little book of bigger primes. 2. Ausgabe. Springer, New York u. a. 2004, ISBN 0-387-20169-6.
  • Die Welt der Primzahlen. Geheimnisse und Rekorde. Auf den neuesten Stand gebracht von Wilfrid Keller. Springer, Berlin / Heidelberg /New York 2006, ISBN 978-3-540-34283-0.

Einzelnachweise Bearbeiten

  1. Wolfgang Blum: Goldbach und die Zwillinge. In: Spektrum der Wissenschaft, Dezember 2008, S. 97 (reproduziert: Primzahlen: Wer lüftet das Geheimnis der Unteilbarkeit? Spiegel Online, 25. Dezember 2008; abgerufen am 24. August 2018).
  2. Paulo Ribenboim: Die Welt der Primzahlen. Geheimnisse und Rekorde. Springer, Berlin / Heidelberg / New York 2006, ISBN 978-3-540-34283-0, S. 219.
  3. Edmund Landau: Handbuch der Lehre von der Verteilung der Primzahlen. B. G. Teubner, 1909, S. 211, abgerufen am 30. Juni 2018.
  4. ↑ Konstantin Fackeldey: Die Goldbachsche Vermutung und ihre bisherigen Lösungsversuche. (PDF) Freie Universität Berlin, 2002, S. 25–27, abgerufen am 30. Juni 2018.
Primzahl­mengen


formelbasiert

Carol ((2n − 1)2 − 2) | Doppelte Mersenne (22p − 1 − 1) | Fakultät (n! ± 1) | Fermat (22n + 1) | Kubisch (x3 − y3)/(x − y) | Kynea ((2n + 1)2 − 2) | Leyland (xy + yx) | Mersenne (2p − 1) | Mills (A3n) | Pierpont (2u⋅3v + 1) | Primorial (pn# ± 1) | Proth (k⋅2n + 1) | Pythagoreisch (4n + 1) | Quartisch (x4 + y4) | Thabit (3⋅2n − 1) | Wagstaff ((2p + 1)/3) | Williams ((b-1)⋅bn − 1) | Woodall (n⋅2n − 1)

Primzahlfolgen

Bell | Fibonacci | Lucas | Motzkin | Pell | Perrin

eigenschaftsbasiert

Elitär | Fortunate | Gut | Glücklich | Higgs | Hochkototient | Isoliert | Pillai | Ramanujan | Regulär | Stark | Stern | Wall–Sun–Sun | Wieferich | Wilson

basis­abhängig

Belphegor | Champernowne | Dihedral | Einzigartig | Fröhlich | Keith | Lange | Minimal | Mirp | Permutierbar | Primeval | Palindrom | Repunit-Primzahl ((10n − 1)/9) | Schwach | Smarandache–Wellin | Strobogrammatisch | Tetradisch | Trunkierbar | Zirkular

basierend auf Tupel

Ausbalanciert (p − n, p, p + n) | Chen | Cousin (p, p + 4) | Cunningham (p, 2p ± 1, …) | Drilling (p, p + 2 oder p + 4, p + 6) | Konstellation | Sexy (p, p + 6) | Sichere (p, (p − 1)/2) | Sophie Germain (p, 2p + 1) | Vierling (p, p + 2, p + 6, p + 8) | Zwilling (p, p + 2) | Zwillings-Bi-Kette (n ± 1, 2n ± 1, …)

nach Größe

Titanisch (1.000+ Stellen) | Gigantisch (10.000+ Stellen) | Mega (1.000.000+ Stellen) | Beva (1.000.000.000+ Stellen)

wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Eine n displaystyle n Fastprimzahl oder auch Fastprimzahl n displaystyle n ter Ordnung ist eine naturliche Zahl deren Primfaktorzerlegung aus genau n displaystyle n Primzahlen besteht wobei mehrfache Primteiler entsprechend oft gezahlt werden Da alle naturlichen Zahlen grosser eins aus Primfaktoren zusammengesetzt sind ist jede naturliche Zahl zugleich auch eine Fastprimzahl Fastprimzahlen zweiter Ordnung also die Produkte von genau zwei Primzahlen nennt man auch Semiprimzahlen Fastprimzahlen bewegen sich zwischen den Polen der unteilbaren Primzahlen und der maximal teilbaren hochzusammengesetzten Zahlen und schliessen dabei beide mit ein Der Norweger Viggo Brun fuhrte den Begriff um 1915 zur Verallgemeinerung von Primzahlen ein um einen neuen Ansatz fur ungeloste Primzahlprobleme zu finden 1 Inhaltsverzeichnis 1 Definition 2 Beispiele und Werte 3 Eigenschaften 4 Anwendungen 5 Weblinks 6 Literatur 7 EinzelnachweiseDefinition BearbeitenSei z N 0 displaystyle z in mathbb N setminus 0 nbsp und z i 1 k p i e i displaystyle textstyle z prod i 1 k p i e i nbsp mit Primzahlen p 1 p k displaystyle p 1 dotsc p k nbsp Dann heisst z displaystyle z nbsp Fastprimzahl n displaystyle n nbsp ter Ordnung wobei n i 1 k e i displaystyle textstyle n sum i 1 k e i nbsp gilt Die Zahlenfolge fur ein festes n displaystyle n nbsp wird auch mit P n displaystyle P n nbsp bezeichnet 2 Die Wohldefiniertheit folgt aus der Eindeutigkeit der Primfaktorzerlegung fur alle naturlichen Zahlen Dieses Konzept kann problemlos auf die ganzen Zahlen und beliebige ZPE Ringe verallgemeinert werden Beispiele und Werte BearbeitenBeispiele 13 displaystyle 13 nbsp ist eine Fastprimzahl erster Ordnung Primzahl 91 7 13 displaystyle 91 7 cdot 13 nbsp ist eine Fastprimzahl zweiter Ordnung Semiprimzahl 100 2 2 5 2 displaystyle 100 2 2 cdot 5 2 nbsp ist eine Fastprimzahl vierter Ordnung 1024 2 10 displaystyle 1024 2 10 nbsp ist eine Fastprimzahl zehnter Ordnung 5308416 2 16 3 4 displaystyle 5308416 2 16 cdot 3 4 nbsp ist eine Fastprimzahl zwanzigster Ordnung Die ersten zwolf Fastprimzahlen erster bis zwanzigster Ordnung 0 1 Ordnung 2 3 5 7 11 13 17 19 23 29 31 37 Folge A000040 in OEIS0 2 Ordnung 4 6 9 10 14 15 21 22 25 26 33 34 Folge A001358 in OEIS0 3 Ordnung 8 12 18 20 27 28 30 42 44 45 50 52 Folge A014612 in OEIS0 4 Ordnung 16 24 36 40 54 56 60 81 84 88 90 100 Folge A014613 in OEIS0 5 Ordnung 32 48 72 80 108 112 120 162 168 176 180 200 Folge A014614 in OEIS0 6 Ordnung 64 96 144 160 216 224 240 324 336 352 360 400 Folge A046306 in OEIS0 7 Ordnung 128 192 288 320 432 448 480 648 672 704 720 800 Folge A046308 in OEIS0 8 Ordnung 256 384 576 640 864 896 960 1296 1344 1408 1440 1600 Folge A046310 in OEIS0 9 Ordnung 512 768 1152 1280 1728 1792 1920 2592 2688 2816 2880 3200 Folge A046312 in OEIS10 Ordnung 1024 1536 2304 2560 3456 3584 3840 5184 5376 5632 5760 6400 Folge A046314 in OEIS11 Ordnung 2048 3072 4608 5120 6912 7168 7680 10368 10752 11264 11520 12800 Folge A069272 in OEIS12 Ordnung 4096 6144 9216 10240 13824 14336 15360 20736 21504 22528 23040 25600 Folge A069273 in OEIS13 Ordnung 8192 12288 18432 20480 27648 28672 30720 41472 43008 45056 46080 51200 Folge A069274 in OEIS14 Ordnung 16384 24576 36864 40960 55296 57344 61440 82944 86016 90112 92160 102400 Folge A069275 in OEIS15 Ordnung 32768 49152 73728 81920 110592 114688 122880 165888 172032 180224 184320 204800 Folge A069276 in OEIS16 Ordnung 65536 98304 147456 163840 221184 229376 245760 331776 344064 360448 368640 409600 Folge A069277 in OEIS17 Ordnung 131072 196608 294912 327680 442368 458752 491520 663552 688128 720896 737280 819200 Folge A069278 in OEIS18 Ordnung 262144 393216 589824 655360 884736 917504 983040 1327104 1376256 1441792 1474560 1638400 Folge A069279 in OEIS19 Ordnung 524288 786432 1179648 1310720 1769472 1835008 1966080 2654208 2752512 2883584 2949120 3276800 Folge A069280 in OEIS20 Ordnung 1048576 1572864 2359296 2621440 3538944 3670016 3932160 5308416 5505024 5767168 5898240 6553600 Folge A069281 in OEISEigenschaften BearbeitenJede Primzahl ist eine Fastprimzahl der Ordnung 1 jede zusammengesetzte Zahl ist eine Fastprimzahl der Ordnung 2 oder hoher Fastprimzahlen dritter Ordnung sofern diese aus 3 verschiedenen Primfaktoren bestehen nennt man auch sphenische Zahlen Die Vereinigung der P n displaystyle P n nbsp bilden eine Zerlegung der naturlichen Zahlen Jede Fastprimzahl n displaystyle n nbsp ter Ordnung ist das Produkt von Fastprimzahlen der Ordnungen k 1 k m displaystyle k 1 dotsc k m nbsp mit i 1 m k i n displaystyle sum i 1 m k i n nbsp z B Das Produkt der 3 Fastprimzahl 12 und der 4 Fastprimzahl 40 ergibt die 7 Fastprimzahl 480 Fur k 1 k m gt 0 displaystyle k 1 dotsc k m gt 0 nbsp gibt es S n m displaystyle S n m nbsp solcher moglichen Zerlegungen wobei S n m displaystyle S n m nbsp die Stirling Zahlen zweiter Art bezeichnet Da es fur die Null keine mogliche Primfaktorzerlegung gibt ist sie keine Fastprimzahl n displaystyle n nbsp ter Ordnung Der Eins wird das leere Produkt als Primfaktorzerlegung zugewiesen Entsprechend kann sie definitionskonform als Fastprimzahl 0 ter Ordnung bezeichnet werden Sei p k n displaystyle pi k n nbsp die Anzahl der positiven ganzen Zahlen kleiner gleich n displaystyle n nbsp mit genau k displaystyle k nbsp Primteilern die nicht unbedingt verschieden sein mussen Dann gilt 3 p k n n log n log log n k 1 k 1 displaystyle pi k n sim frac n log n cdot frac log log n k 1 k 1 nbsp Jede genugend grosse gerade Zahl lasst sich als die Summe einer Primzahl und einer Fastprimzahl zweiter Ordnung darstellen 4 Diese Aussage hat Ahnlichkeit mit der Goldbachschen Vermutung wurde 1978 von Chen Jingrun bewiesen und nennt sich Satz von Chen Es gibt unendlich viele Primzahlen sodass p 2 displaystyle p 2 nbsp eine 2 Fastprimzahl ist 4 Diese Aussage hat Ahnlichkeit mit der Vermutung uber Primzahlzwillinge und wurde ebenfalls von Chen bewiesen Anwendungen BearbeitenFastprimzahlen zweiter Ordnung also Produkte zweier Primzahlen finden in der Kryptographie Anwendung Weblinks BearbeitenEric W Weisstein Almost prime In MathWorld englisch Fastprimzahlen Eric W Weisstein Semiprime In MathWorld englisch Fastprimzahlen 2 OrdnungLiteratur BearbeitenWladyslaw Narkiewicz The Development of Prime Number Theory From Euclid to Hardy and Littlewood Springer Berlin u a 2000 ISBN 3 540 66289 8 Hans Riesel Prime Numbers and Computer Methods for Factorization Birkhauser Boston Basel Stuttgart 1985 ISBN 3 7643 3291 3 David M Bressoud Factorization and Primality Testing Springer New York u a 1989 ISBN 0 387 97040 1 Paulo Ribenboim The little book of bigger primes 2 Ausgabe Springer New York u a 2004 ISBN 0 387 20169 6 Die Welt der Primzahlen Geheimnisse und Rekorde Auf den neuesten Stand gebracht von Wilfrid Keller Springer Berlin Heidelberg New York 2006 ISBN 978 3 540 34283 0 Einzelnachweise Bearbeiten Wolfgang Blum Goldbach und die Zwillinge In Spektrum der Wissenschaft Dezember 2008 S 97 reproduziert Primzahlen Wer luftet das Geheimnis der Unteilbarkeit Spiegel Online 25 Dezember 2008 abgerufen am 24 August 2018 Paulo Ribenboim Die Welt der Primzahlen Geheimnisse und Rekorde Springer Berlin Heidelberg New York 2006 ISBN 978 3 540 34283 0 S 219 Edmund Landau Handbuch der Lehre von der Verteilung der Primzahlen B G Teubner 1909 S 211 abgerufen am 30 Juni 2018 a b Konstantin Fackeldey Die Goldbachsche Vermutung und ihre bisherigen Losungsversuche PDF Freie Universitat Berlin 2002 S 25 27 abgerufen am 30 Juni 2018 V DPrimzahl mengenformelbasiert Carol 2n 1 2 2 Doppelte Mersenne 22p 1 1 Fakultat n 1 Fermat 22n 1 Kubisch x3 y3 x y Kynea 2n 1 2 2 Leyland xy yx Mersenne 2p 1 Mills A3n Pierpont 2u 3v 1 Primorial pn 1 Proth k 2n 1 Pythagoreisch 4n 1 Quartisch x4 y4 Thabit 3 2n 1 Wagstaff 2p 1 3 Williams b 1 bn 1 Woodall n 2n 1 Primzahlfolgen Bell Fibonacci Lucas Motzkin Pell Perrineigenschaftsbasiert Elitar Fortunate Gut Glucklich Higgs Hochkototient Isoliert Pillai Ramanujan Regular Stark Stern Wall Sun Sun Wieferich Wilsonbasis abhangig Belphegor Champernowne Dihedral Einzigartig Frohlich Keith Lange Minimal Mirp Permutierbar Primeval Palindrom Repunit Primzahl 10n 1 9 Schwach Smarandache Wellin Strobogrammatisch Tetradisch Trunkierbar Zirkularbasierend auf Tupel Ausbalanciert p n p p n Chen Cousin p p 4 Cunningham p 2p 1 Drilling p p 2 oder p 4 p 6 Konstellation Sexy p p 6 Sichere p p 1 2 Sophie Germain p 2p 1 Vierling p p 2 p 6 p 8 Zwilling p p 2 Zwillings Bi Kette n 1 2n 1 nach Grosse Titanisch 1 000 Stellen Gigantisch 10 000 Stellen Mega 1 000 000 Stellen Beva 1 000 000 000 Stellen Abgerufen von https de wikipedia org w index php title Fastprimzahl amp oldid 216083996