www.wikidata.de-de.nina.az

Glatte Zahl Eine glatte Zahl bezüglich einer Schranke S displaystyle S ist eine natürliche Zahl in deren Primfaktorzerle

Glatte Zahl

Eine glatte Zahl bezüglich einer Schranke ist eine natürliche Zahl, in deren Primfaktorzerlegung keine Primzahlen vorkommen, die größer als die Schranke sind. Man bezeichnet eine solche Zahl auch als -glatt.

Eine natürliche Zahl heißt potenzglatt bezüglich einer Schranke , wenn in ihrer Primfaktorzerlegung nur Primpotenzen kleiner oder gleich vorkommen. Das heißt, für jeden Primfaktor , der mal vorkommt, gilt:

Beispiele Bearbeiten

Untersuchen wir zum Beispiel die Zahl 720 (Primfaktorzerlegung: 720 = 24 · 32 · 5):

  • sie ist 5-glatt, 6-glatt …
  • nicht jedoch 3-glatt oder 4-glatt (wegen der 5 als Primfaktor, da 5 größer ist als 3 und 4)
  • sie ist ferner 16-potenzglatt, 17-potenzglatt …,
  • nicht jedoch 15-potenzglatt (da in der Primfaktorzerlegung die 2 in der 4. Potenz (= 16) auftritt, womit die Schranke 15 überschritten wird)

Betrachten wir im Folgenden die Zahl 8 als Schranke.

8-glatt

  • sind z. B. 3, 4, 5, 12, 14 oder 120
  • nicht jedoch 11 oder 26

8-potenzglatt

  • sind z. B. 3, 4, 5, 12, 56 oder 840 (=23 · 3 · 5· 7)
  • nicht jedoch 9 (= 32) oder 16 (= 24)

Hinweise:

  • Wenn eine Primzahl, die nächstgrößere Primzahl und ist, ist die Menge der -glatten Zahlen gleich der Menge der -glatten Zahlen.
  • 2-glatte Zahlen entsprechen den Zweierpotenzen.
  • Als "1-glatt" kann formal die Zahl 1 gelten.

Eigenschaften Bearbeiten

Für jede natürliche Zahl gibt es eine eindeutige Primfaktorzerlegung. Das heißt, zu jedem existiert und Primzahlen , sowie Vielfachheiten so, dass gilt

Nun definieren wir

Für jedes und ist die Zahl -glatt und -potenzglatt, für alle und ist die Zahl weder -glatt noch -potenzglatt.

7-glatte Zahlen Bearbeiten

7-glatte (oder 7er glatte) Zahlen sind solche, die ausschließlich aus Potenzen der Primfaktoren 2, 3, 5 und 7 bestehen, zum Beispiel 1372 = 22 · 73.

Ein häufig synonym gebrauchter Begriff ist hochzusammengesetzte Zahlen, wobei 7-glatte Zahlen sich vom tatsächlichen mathematischen Konzept der Hochzusammengesetzten Zahl unterscheiden, das alle Primfaktoren zulässt und weitere Bedingungen an diese stellt.

Da die Primzahlen 2, 3, 5 und 7 in den auf leichte Teilbarkeit hin orientierten, vormetrischen, alten Maßen und Gewichten auftreten (z. B. 1 Nürnberger Apothekergran = 19600 Nürnberger Grän = 980 Nürnberger Skrupel = 3 Karlspfund), spielt diese Folge auch in der Forschung zur historischen Metrologie eine Rolle. (siehe dazu Nippur-Elle, Karlspfund, Apothekergewicht)

Die Zahlenfolge der 7-glatten Zahlen: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 24, 25, 27, 28, 30, 32, 35, 36, 40, 42 … findet sich unter Folge A002473 in OEIS mit der Benennung „hochzusammengesetzte Zahlen (2)“ (Highly composite numbers (2): numbers whose prime divisors are all <= 7.)

Verfahren Bearbeiten

Das Quadratische Sieb, ein Faktorisierungsverfahren, beruht auf der Primfaktorzerlegung quadratischer Reste. Diese Zerlegung kann für glatte Zahlen leicht durchgeführt werden. Dabei ist es auch von Interesse, für viele Zahlen auf einmal ihren größten glatten Teiler zu ermitteln (und eventuell deren Restfaktoren weiter zu analysieren).
Daniel Bernstein entwickelte hierzu ein effizientes Verfahren, das für eine Menge von unzerlegten natürlichen Zahlen mittels gruppenweiser Multiplikationen und sparsamster Organisation jeden glatten Primfaktor jeder einzelnen Zahl ermittelt, ohne Testdivisionen mit den in Frage kommenden Primzahlen durchzuführen. Das Verfahren nutzt lediglich bekannte schnelle Algorithmen für Multiplikation, Division ohne Rest und Berechnung des größten gemeinsamen Teilers zweier natürlicher Zahlen.

Folgen glatter Zahlen Bearbeiten

Für jede Schranke bilden die entsprechenden -glatten Zahlen eine Folge. Unter der On-Line Encyclopedia of Integer Sequences (OEIS) stehen diese Folgen für kleine Schranken zur Verfügung:

Literatur Bearbeiten

Weblinks Bearbeiten

Einzelnachweise Bearbeiten

  1. D. Bernstein: How to find smooth parts of integers. Entwurf für Math. Comput., PDF-Datei
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 glatte Zahl bezuglich einer Schranke S displaystyle S ist eine naturliche Zahl in deren Primfaktorzerlegung keine Primzahlen vorkommen die grosser als die Schranke sind Man bezeichnet eine solche Zahl auch als S displaystyle S glatt Eine naturliche Zahl heisst potenzglatt bezuglich einer Schranke S displaystyle S wenn in ihrer Primfaktorzerlegung nur Primpotenzen kleiner oder gleich S displaystyle S vorkommen Das heisst fur jeden Primfaktor q displaystyle q der a q displaystyle a q mal vorkommt gilt q a q S displaystyle q a q leq S Inhaltsverzeichnis 1 Beispiele 2 Eigenschaften 3 7 glatte Zahlen 4 Verfahren 5 Folgen glatter Zahlen 6 Literatur 7 Weblinks 8 EinzelnachweiseBeispiele BearbeitenUntersuchen wir zum Beispiel die Zahl 720 Primfaktorzerlegung 720 24 32 5 sie ist 5 glatt 6 glatt nicht jedoch 3 glatt oder 4 glatt wegen der 5 als Primfaktor da 5 grosser ist als 3 und 4 sie ist ferner 16 potenzglatt 17 potenzglatt nicht jedoch 15 potenzglatt da in der Primfaktorzerlegung die 2 in der 4 Potenz 16 auftritt womit die Schranke 15 uberschritten wird Betrachten wir im Folgenden die Zahl 8 als Schranke 8 glatt sind z B 3 4 5 12 14 oder 120 nicht jedoch 11 oder 268 potenzglatt sind z B 3 4 5 12 56 oder 840 23 3 5 7 nicht jedoch 9 32 oder 16 24 Hinweise Wenn p displaystyle p nbsp eine Primzahl p 2 displaystyle p 2 nbsp die nachstgrossere Primzahl und p n lt p 2 displaystyle p leq n lt p 2 nbsp ist ist die Menge der n displaystyle n nbsp glatten Zahlen gleich der Menge der p displaystyle p nbsp glatten Zahlen 2 glatte Zahlen entsprechen den Zweierpotenzen Als 1 glatt kann formal die Zahl 1 gelten Eigenschaften BearbeitenFur jede naturliche Zahl gibt es eine eindeutige Primfaktorzerlegung Das heisst zu jedem a N displaystyle a in mathbb N nbsp existiert n N displaystyle n in mathbb N nbsp und Primzahlen q 1 q n P displaystyle q 1 dots q n in mathbb P nbsp sowie Vielfachheiten a 1 a n N displaystyle a 1 dots a n in mathbb N nbsp so dass gilt a i 1 n q i a i displaystyle a prod i 1 n q i a i nbsp Nun definieren wir g a max q i i 1 n displaystyle g a max q i i 1 dots n nbsp z a max q i a i i 1 n displaystyle z a max q i a i i 1 dots n nbsp Fur jedes g g a displaystyle g geq g a nbsp und z z a displaystyle z geq z a nbsp ist die Zahl a displaystyle a nbsp g displaystyle g nbsp glatt und z displaystyle z nbsp potenzglatt fur alle g lt g a displaystyle g lt g a nbsp und z lt z a displaystyle z lt z a nbsp ist die Zahl a displaystyle a nbsp weder g displaystyle g nbsp glatt noch z displaystyle z nbsp potenzglatt 7 glatte Zahlen Bearbeiten7 glatte oder 7er glatte Zahlen sind solche die ausschliesslich aus Potenzen der Primfaktoren 2 3 5 und 7 bestehen zum Beispiel 1372 22 73 Ein haufig synonym gebrauchter Begriff ist hochzusammengesetzte Zahlen wobei 7 glatte Zahlen sich vom tatsachlichen mathematischen Konzept der Hochzusammengesetzten Zahl unterscheiden das alle Primfaktoren zulasst und weitere Bedingungen an diese stellt Da die Primzahlen 2 3 5 und 7 in den auf leichte Teilbarkeit hin orientierten vormetrischen alten Massen und Gewichten auftreten z B 1 Nurnberger Apothekergran 19600 Nurnberger Gran 980 Nurnberger Skrupel 3 Karlspfund spielt diese Folge auch in der Forschung zur historischen Metrologie eine Rolle siehe dazu Nippur Elle Karlspfund Apothekergewicht Die Zahlenfolge der 7 glatten Zahlen 1 2 3 4 5 6 7 8 9 10 12 14 15 16 18 20 21 24 25 27 28 30 32 35 36 40 42 findet sich unter Folge A002473 in OEIS mit der Benennung hochzusammengesetzte Zahlen 2 Highly composite numbers 2 numbers whose prime divisors are all lt 7 Verfahren BearbeitenDas Quadratische Sieb ein Faktorisierungsverfahren beruht auf der Primfaktorzerlegung quadratischer Reste Diese Zerlegung kann fur glatte Zahlen leicht durchgefuhrt werden Dabei ist es auch von Interesse fur viele Zahlen auf einmal ihren grossten glatten Teiler zu ermitteln und eventuell deren Restfaktoren weiter zu analysieren Daniel Bernstein entwickelte hierzu ein effizientes Verfahren 1 das fur eine Menge von unzerlegten naturlichen Zahlen mittels gruppenweiser Multiplikationen und sparsamster Organisation jeden glatten Primfaktor jeder einzelnen Zahl ermittelt ohne Testdivisionen mit den in Frage kommenden Primzahlen durchzufuhren Das Verfahren nutzt lediglich bekannte schnelle Algorithmen fur Multiplikation Division ohne Rest und Berechnung des grossten gemeinsamen Teilers zweier naturlicher Zahlen Folgen glatter Zahlen BearbeitenFur jede Schranke S displaystyle S nbsp bilden die entsprechenden S displaystyle S nbsp glatten Zahlen eine Folge Unter der On Line Encyclopedia of Integer Sequences OEIS stehen diese Folgen fur kleine Schranken zur Verfugung 0 2 glatte Zahlen Folge A000079 in OEIS alle Zweierpotenzen 2 x displaystyle 2 x nbsp 0 3 glatte Zahlen Folge A003586 in OEIS Zahlen der Form 2 x 3 y displaystyle 2 x cdot 3 y nbsp 0 5 glatte Zahlen Folge A051037 in OEIS Zahlen der Form 2 x 3 y 5 z displaystyle 2 x cdot 3 y cdot 5 z nbsp 0 7 glatte Zahlen Folge A002473 in OEIS 11 glatte Zahlen Folge A51038 in OEIS 13 glatte Zahlen Folge A80197 in OEIS 17 glatte Zahlen Folge A80681 in OEIS 19 glatte Zahlen Folge A80682 in OEIS 23 glatte Zahlen Folge A80683 in OEISLiteratur BearbeitenCarl Pomerance The role of smooth numbers in number theoretic algorithms PDF 8 3 MB Proc Int Congr Mathematicians Zurich 1994 Birkhauser Verlag Basel 1995 S 411 422 Andrew Granville Smooth numbers computational number theory and beyond PDF 403 kB In Algorithmic Number Theory MSRI Publications 44 2008 S 267 323Weblinks BearbeitenEric W Weisstein Smooth Number In MathWorld englisch Einzelnachweise Bearbeiten D Bernstein How to find smooth parts of integers Entwurf fur Math Comput PDF Datei Abgerufen von https de wikipedia org w index php title Glatte Zahl amp oldid 202601120