Misplaced Pages

Golomb–Dickman constant

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
Mathematical constant

In mathematics, the Golomb–Dickman constant, named after Solomon W. Golomb and Karl Dickman, is a mathematical constant, which arises in the theory of random permutations and in number theory. Its value is

λ = 0.62432998854355087099293638310083724 … {\displaystyle \lambda =0.62432998854355087099293638310083724\dots } (sequence A084945 in the OEIS)

It is not known whether this constant is rational or irrational.

It's simple continued fraction is given by [ 0 ; 1 , 1 , 1 , 1 , 1 , 22 , 1 , 2 , 3 , 1 , . . . ] {\displaystyle } , which appears to have an unusually large number of 1s.

Definitions

Let an 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 . {\displaystyle \lambda =\lim _{n\to \infty }{\frac {a_{n}}{n}}.}

In the language of probability theory, λ n {\displaystyle \lambda 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 ) , {\displaystyle \lambda =\lim _{n\to \infty }{\frac {1}{n}}\sum _{k=2}^{n}{\frac {\log(P_{1}(k))}{\log(k)}},}

where P 1 ( k ) {\displaystyle P_{1}(k)} is the largest prime factor of k (sequence A006530 in the OEIS) . So if k is a d digit integer, then λ d {\displaystyle \lambda 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 λ {\displaystyle \lambda } . More precisely,

λ = lim n → ∞ Prob { P 2 ( n ) ≤ P 1 ( n ) } {\displaystyle \lambda =\lim _{n\to \infty }{\text{Prob}}\left\{P_{2}(n)\leq {\sqrt {P_{1}(n)}}\right\}}

where P 2 ( n ) {\displaystyle P_{2}(n)} is the second largest prime factor n.

The Golomb-Dickman constant also arises when we consider the average length of the largest cycle of any function from a finite set to itself. If X is a finite set, if we repeatedly apply a function f: X → X to any element x of this set, it eventually enters a cycle, meaning that for some k we have f n + k ( x ) = f n ( x ) {\displaystyle f^{n+k}(x)=f^{n}(x)} for sufficiently large n; the smallest k with this property is the length of the cycle. Let bn be the average, taken over all functions from a set of size n to itself, of the length of the largest cycle. Then Purdom and Williams proved that

lim n → ∞ b n n = π 2 λ . {\displaystyle \lim _{n\to \infty }{\frac {b_{n}}{\sqrt {n}}}={\sqrt {\frac {\pi }{2}}}\lambda .}

Formulae

There are several expressions for λ {\displaystyle \lambda } . These include:

λ = ∫ 0 1 e l i ( t ) d t {\displaystyle \lambda =\int _{0}^{1}e^{\mathrm {li} (t)}\,dt}

where l i ( t ) {\displaystyle \mathrm {li} (t)} is the logarithmic integral,

λ = ∫ 0 ∞ e − t − E 1 ( t ) d t {\displaystyle \lambda =\int _{0}^{\infty }e^{-t-E_{1}(t)}\,dt}

where E 1 ( t ) {\displaystyle E_{1}(t)} is the exponential integral, and

λ = ∫ 0 ∞ ρ ( t ) t + 2 d t {\displaystyle \lambda =\int _{0}^{\infty }{\frac {\rho (t)}{t+2}}\,dt}

and

λ = ∫ 0 ∞ ρ ( t ) ( t + 1 ) 2 d t {\displaystyle \lambda =\int _{0}^{\infty }{\frac {\rho (t)}{(t+1)^{2}}}\,dt}

where ρ ( t ) {\displaystyle \rho (t)} is the Dickman function.

See also

External links

References

  1. Lagarias, Jeffrey (2013). "Euler's constant: Euler's work and modern developments". Bull. Amer. Math. Soc. 50 (4): 527–628. arXiv:1303.1856. Bibcode:2013arXiv1303.1856L. doi:10.1090/S0273-0979-2013-01423-X. S2CID 119612431.
  2. Weisstein, Eric W. "Golomb-Dickman Constant Continued Fraction". mathworld.wolfram.com. Retrieved 2024-10-11.
  3. Purdon, P.; Williams, J.H (1968). "Cycle length in a random function". Trans. Amer. Math. Soc. 133 (2): 547–551. doi:10.1090/S0002-9947-1968-0228032-3.
  4. Weisstein, Eric W. "Golomb-Dickman Constant". mathworld.wolfram.com. Retrieved 2024-10-11.
Categories: