Surprisingly, there is a connection between and prime
factorization (Knuth and Pardo 1976, Knuth 1997, pp. 367-368, 395, and 611).
Dickman (1930) investigated the probability that the greatest
prime factor of a random integer between 1
and
satisfies
for .
He found that
(21)
where
is now known as the Dickman function. Dickman
then found the average value of such that , obtaining
Dickman, K. "On the Frequency of Numbers Containing Prime Factors of a Certain Relative Magnitude." Arkiv för Mat., Astron.
och Fys.22A, 1-14, 1930.Finch, S. R. "Golomb-Dickman
Constant." §5.4 in Mathematical
Constants. Cambridge, England: Cambridge University Press, pp. 284-292,
2003.Golomb, S. W. "Random Permutations." Bull. Amer.
Math. Soc.70, 747, 1964.Goncharov, W. "Sur la distribution
des cycles dans les permutations." C. R. (Dokl.) Acad. Sci. URSS35,
267-269, 1942.Goncharov, W. "On the Field of Combinatory Analysis."
Izv. Akad. Nauk SSSR8, 3-48, 1944. English translation in Amer.
Math. Soc. Transl.19, 1-46, 1962.Gourdon, X. Combinatoire,
Algorithmique et Géometrie des Polynômes. Ph. D. thesis. École
Polytechnique, 1996.Knuth, D. E. The
Art of Computer Programming, Vol. 1: Fundamental Algorithms, 3rd ed.
Reading, MA: Addison-Wesley, 1997.Knuth, D. E. The
Art of Computer Programming, Vol. 2: Seminumerical Algorithms, 3rd ed.
Reading, MA: Addison-Wesley, 1998.Knuth, D. E. and Pardo, L. T.
"Analysis of a Simple Factorization Algorithm." Theor. Comput. Sci.3,
321-348, 1976.Mitchell, W. C. "An Evaluation of Golomb's Constant."
Math. Comput.22, 411-415, 1968.Purdom, P. W. and
Williams, J. H. "Cycle Length in a Random Function." Trans. Amer.
Math. Soc.133, 547-551, 1968.Shepp, L. A. and Lloyd,
S. P. "Ordered Cycle Lengths in Random Permutation." Trans. Amer.
Math. Soc.121, 350-557, 1966.Sloane, N. J. A.
Sequences A084945, A174974,
and A174975 in "The On-Line Encyclopedia
of Integer Sequences."Wilf, H. S. Generatingfunctionology,
2nd ed. New York: Academic Press, 1994.