Glatte Zahl - LinkFang.de





Glatte Zahl


Eine glatte Zahl bezüglich einer Schranke [math]S[/math] 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 [math]S[/math]-glatt.

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

[math]q^{a_q} \leq S[/math].

Beispiele

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)
  • 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 [math]p[/math] eine Primzahl, [math]p_2[/math] die nächstgrößere Primzahl und [math]p \leq n \lt p_2[/math] ist, ist die Menge der [math]n[/math]-glatten Zahlen gleich der Menge der [math]p[/math]-glatten Zahlen.
  • 2-glatte Zahlen entsprechen den Zweierpotenzen.
  • Als "1-glatt" kann formal die Zahl 1 gelten.

Eigenschaften

Für jede natürliche Zahl gibt es eine eindeutige Primfaktorzerlegung. Das heißt zu jedem [math]a\in\mathbb{N}[/math] existiert [math]n\in\mathbb{N}[/math] und Primzahlen [math]p_1,\dots,p_n\in\mathbb{P}[/math], sowie Vielfachheiten [math]a_1,\dots,a_n\in\mathbb{N}[/math] so, dass gilt

[math]a=\prod_{i=1}^{n} q_i^{a_i}[/math]

Nun definieren wir

[math]g(a):=\max\{q_i;i=1,\dots,n\}[/math]
[math]z(a):=\max\{q_i^{a_i};i=1,\dots,n\}[/math]

Für jedes [math]g\geq g(a)[/math] und [math]z\geq z(a)[/math] ist die Zahl a g-glatt und z-potenzglatt, für alle [math]g\ltg(a)[/math] und [math]z\ltz(a)[/math] ist die Zahl a weder g-glatt noch z-potenzglatt.

7-glatte Zahlen

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

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[1], 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

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

Literatur

Weblinks

Einzelnachweise

  1. D. Bernstein: How to find smooth parts of integers. Entwurf für Math. Comput., pdf-Datei

Kategorien: Analytische Zahlentheorie

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Glatte Zahl (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.