Distinct Prime Factors

The distinct prime factors of a positive integer  are defined as the  numbers , ...,  in the prime factorization

(1)

(Hardy and Wright 1979, p. 354).

A list of distinct prime factors of a number  can be computed in the Wolfram Language using FactorInteger[n][[All, 1]], and the number  of distinct prime factors is implemented as PrimeNu[n].

The first few values of  for , 2, ... are 0, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 2, 1, 2, 2, 1, 1, 2, 1, 2, ... (OEIS A001221; Abramowitz and Stegun 1972, Kac 1959). This sequence is given by the inverse Möbius transform of , where  is the characteristic function of the prime numbers (Sloane and Plouffe 1995, p. 22). The prime factorizations and distinct prime factors of the first few positive integers are listed in the table below.

	prime factorization		distinct prime factors (A027748)
1	--	0	--
2	2	1	2
3	3	1	3
4		1	2
5	5	1	5
6		2	2, 3
7	7	1	7
8		1	2
9		1	3
10		2	2, 5
11	11	1	11
12		2	2, 3
13	13	1	13
14		2	2, 7
15		2	3, 5
16		1	2

The numbers consisting only of distinct prime factors are precisely the squarefree numbers.

A sum involving  is given by

(2)

for  (Hardy and Wright 1979, p. 255).

The average order of  is

(3)

(Hardy 1999, p. 51). More precisely,

(4)

(Diaconis 1976, Knuth 2000, Diaconis 2002, Finch 2003, Knuth 2003), where  is the Mertens constant and  are Stieltjes constants. Furthermore, the variance is given by

(5)

where

			(6)
			(7)

(OEIS A091588), where

(8)

(OEIS A085548) is the prime zeta function  (Finch 2003). The coefficients  and  are given by the sums

			(9)
			(10)
			(11)
			(12)
			(13)

(Diaconis 1976, Knuth 2000, Diaconis 2002, Finch 2003, Knuth 2003), where

			(14)
			(15)
			(16)
			(17)

(Finch 2003).

If  is a primorial, then

(18)

(Hardy and Wright 1979, p. 355).

The summatory function of  is given by

(19)

where  is the Mertens constant (Hardy 1999, p. 57), the  term (Hardy and Ramanujan 1917; Hardy and Wright 1979, p. 355) has been rewritten in a more explicit form, and  and  are asymptotic notation. The first few values of the summatory function are 1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 14, 15, 17, 19, 20, 21, ... (OEIS A013939). In addition,

(20)

(Hardy and Wright 1979, p. 357).

The first few numbers  which are products of an odd number of distinct prime factors (Hardy 1999, p. 64; Ramanujan 2000, pp. xxiv and 21) are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 30, 31, 37, 41, 42, 43, 47, ... (OEIS A030059).  satisfies

(21)

(Hardy 1999, pp. 64-65). In addition, if  is the number of  with , then

(22)

(Hardy 1999, pp. 64-65).

REFERENCES:

Abramowitz, M. and Stegun, I. A. (Eds.). Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables, 9th printing. New York: Dover, p. 844, 1972.

Diaconis, P. "Asymptotic Expansions for the Mean and Variance of the Number of Prime Factors of a Number ." Dept. Statistics Tech. Report 96, Stanford, CA: Stanford University, 1976.

Diaconis, P. "G. H. Hardy and Probability???" Bull. London Math. Soc. 34, 385-402, 2002.

Finch, S. "Two Asymptotic Series." December 10, 2003. https://algo.inria.fr/bsolve/.

Hardy, G. H. Ramanujan: Twelve Lectures on Subjects Suggested by His Life and Work, 3rd ed. New York: Chelsea, 1999.

Hardy, G. H. and Ramanujan, S. "The Normal Number of Prime Factors of a Number ." Quart. J. Math. 48, 76-92, 1917.

Hardy, G. H. and Wright, E. M. "The Number of Prime Factors of " and "The Normal Order of  and ." §22.10 and 22.11 in An Introduction to the Theory of Numbers, 5th ed. Oxford, England: Clarendon Press, pp. 354-358, 1979.

Kac, M. Statistical Independence in Probability, Analysis and Number Theory. Washington, DC: Math. Assoc. Amer., p. 64, 1959.

Knuth, D. E. Selected Papers on Analysis of Algorithms. Stanford, CA: CSLI Publications, pp. 338-339, 2000.

Knuth, D. E. "Asymptotics for  and ." Cited by Finch (2003). Unpublished note, 2003.

Ramanujan, S. Collected Papers of Srinivasa Ramanujan (Ed. G. H. Hardy, P. V. S. Aiyar, and B. M. Wilson). Providence, RI: Amer. Math. Soc., 2000.

Sloane, N. J. A. Sequences A001221/M0056, A013939, A027748, A085548, and A091588 in "The On-Line Encyclopedia of Integer Sequences."

Sloane, N. J. A. and Plouffe, S. The Encyclopedia of Integer Sequences. San Diego, CA: Academic Press, 1995.