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

Die Golomb-Dickman-Konstante ist definiert als

    (Folge A084945 in OEIS),

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

Vorkommen

Bearbeiten

Zyklen in Permutationen

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

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]

Literatur

Bearbeiten

Einzelnachweise

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.
Bearbeiten