Golomb-Dickman-Konstante

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

Die Golomb-Dickman-Konstante ist eine mathematische Konstante aus der Kombinatorik und Zahlentheorie. Sie stellt einerseits den asymptotischen Erwartungswert der relativen Länge des längsten Zyklus einer zufälligen Permutation dar, andererseits gibt sie den asymptotischen Erwartungswert der relativen Anzahl der Ziffern des größten Primfaktors einer natürlichen Zahl an. Die Konstante ist nach dem US-amerikanischen Mathematiker Solomon W. Golomb und dem schwedischen Aktuar Karl Dickman benannt, die sie unabhängig voneinander entdeckten.

Definition[Bearbeiten | Quelltext bearbeiten]

Die Golomb-Dickman-Konstante ist definiert als

  (Folge A084945 in OEIS),

wobei der Integrallogarithmus und die Integralexponentialfunktion sind.[1][2]

Vorkommen[Bearbeiten | Quelltext bearbeiten]

Zyklen in Permutationen[Bearbeiten | Quelltext bearbeiten]

Bezeichnet die Anzahl der disjunkten Zyklen der Länge einer Permutation , dann ist

die Länge des längsten Zyklus von . Für den Erwartungswert der relativen Länge des längsten Zyklus einer (gleichverteilt) zufälligen Permutation der Länge gilt asymptotisch[1]

.

Hierbei ist die Dickman-Funktion die eindeutige stetige Lösung der Delay-Differentialgleichung

mit .[3]

Primfaktoren[Bearbeiten | Quelltext bearbeiten]

Bezeichnet den größten Primfaktor einer zufälligen natürlichen Zahl , dann gilt[1][4]

für mit der Dickman-Funktion . Hieraus folgt

.

Die Konstante gibt demnach auch den asymptotischen Erwartungswert der relativen Anzahl der Ziffern des größten Primfaktors einer natürlichen Zahl an.[5] Allgemein entspricht sogar die gesamte Verteilung der Anzahl der Ziffern der Primfaktoren einer natürlichen Zahl asymptotisch der Verteilung der Längen der Zyklen einer zufälligen Permutation.[1]

Siehe auch[Bearbeiten | Quelltext bearbeiten]

  • Niven-Konstante, der Grenzwert des arithmetischen Mittels der maximalen Exponenten der Primfaktorzerlegungen der ersten natürlichen Zahlen

Literatur[Bearbeiten | Quelltext bearbeiten]

Einzelnachweise[Bearbeiten | Quelltext bearbeiten]

  1. a b c d Steven R. Finch: Mathematical Constants. Cambridge University Press, 2003, S. 284–292.
  2. Larry A. Shepp, Stuart P. Lloyd: Ordered cycle lengths in a random permutation. In: Trans. Amer. Math. Soc. Nr. 121, 1966, S. 350–557.
  3. Solomon W. Golomb: Random permutations. In: Bull. Amer. Math. Soc. Nr. 70, 1964, S. 747.
  4. Karl Dickman: On the frequency of numbers containing prime factors of a certain relative magnitude. In: Arkiv för Mat., Astron. och Fys. 22A, 1930, S. 1–14.
  5. Donald E. Knuth, Luis Trabb Pardo: Analysis of a simple factorization algorithm. In: Theor. Comput. Sci. Nr. 3, 1976, S. 321–348.

Weblinks[Bearbeiten | Quelltext bearbeiten]