Golomb–Dickman constant - Alchetron, the free social encyclopedia

In mathematics, the Golomb–Dickman constant arises in the theory of random permutations and in number theory. Its value is

Definitions

Let a_n be the average — taken over all permutations of a set of size n — of the length of the longest cycle in each permutation. Then the Golomb–Dickman constant is

λ = lim n → ∞ a n n .

In the language of probability theory, λ n is asymptotically the expected length of the longest cycle in a uniformly distributed random permutation of a set of size n.

In number theory, the Golomb–Dickman constant appears in connection with the average size of the largest prime factor of an integer. More precisely,

λ = lim n → ∞ 1 n ∑ k = 2 n log ⁡ ( P 1 ( k ) ) log ⁡ ( k ) ,

where P 1 ( k ) is the largest prime factor of k. So if k is a d digit integer, then λ d is the asymptotic average number of digits of the largest prime factor of k.

The Golomb–Dickman constant appears in number theory in a different way. What is the probability that second largest prime factor of n is smaller than the square root of the largest prime factor of n? Asymptotically, this probability is λ . More precisely,

λ = lim n → ∞ Prob { P 2 ( n ) ≤ P 1 ( n ) }

where P 2 ( n ) is the second largest prime factor n.

Formulae

There are several expressions for λ . Namely,

λ = ∫ 0 ∞ e − t − E 1 ( t ) d t

where E 1 ( t ) is the exponential integral,

λ = ∫ 0 ∞ ρ ( t ) t + 2 d t

and

λ = ∫ 0 ∞ ρ ( t ) ( t + 1 ) 2 d t

where ρ ( t ) is the Dickman function.

References

Golomb–Dickman constant Wikipedia

(Text) CC BY-SA

Contents

Definitions

Formulae

References