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.

Die Golomb-Dickman-Konstante ist definiert als

  (Folge A084945 in OEIS),

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

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]

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]

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.