Posted by: anthonygenello | December 15, 2008

The Golomb-Dickman Constant

In my statistics class this semester, we’ve learned about a few interesting results that relate well to Math 152. The class is Statistics 135: Statistical Computing Software. Permutations and prime factorization we covered in the context of computer simulation in the statistical programming language R. The questions that we were considering were twofold. First, we were interested in finding the mean of the distribution of the largest cycle of a random permutation on n symbols. Second we were interested in finding the largest prime factor of a random integer n. It turns out that the anwers to the two questions are the same after a logarithmic transformation. The solution as a fraction of n is called the Golomb-Dickman constant: approximately 0.624. The answer to the first question was discovered by Golomb while the answer to the second question was discovered by Dickman.

The formal Golomb definition is as follows: 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.  In the limiting case we have:

\lim_{n\to\infty} \frac{a_n}{n}

The formal Dickman definition is as follows:  the Golomb–Dickman constant appears in connection with the average size of the largest prime factor of a number less than or equal to n . In summation notation we have:

 
\lim_{n\to\infty} \frac1n \sum_{k=2}^n \frac{\log(p_k)}{\log(n)}

where p_k  is the largest prime factor of k .

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Categories

%d bloggers like this: