TOPICS
Search

Distinct Prime Factors


DistinctPrimeFactors

The distinct prime factors of a positive integer n>=2 are defined as the omega(n) numbers p_1, ..., p_(omega(n)) in the prime factorization

 n=p_1^(a_1)p_2^(a_2)...p_(omega(n))^(a_(omega(n)))
(1)

(Hardy and Wright 1979, p. 354).

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

The first few values of omega(n) for n=1, 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 {chi_P(n)}, where chi_P 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.

nprime factorizationomega(n)distinct prime factors (A027748)
1--0--
2212
3313
42^212
5515
62·322, 3
7717
82^312
93^213
102·522, 5
1111111
122^2·322, 3
1313113
142·722, 7
153·523, 5
162^412

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

A sum involving omega(n) is given by

 sum_(n=1)^infty(2^(omega(n)))/(n^s)=(zeta^2(s))/(zeta(2s))
(2)

for s>1 (Hardy and Wright 1979, p. 255).

The average order of omega(n) is

 omega(n)∼lnlnn
(3)

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

 omega(n)∼lnlnn+B_1+sum_(k=1)^infty(-1+sum_(j=0)^(k-1)(gamma_j)/(j!))((k-1)!)/((lnn)^k)
(4)

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

 var(omega(n))∼lnlnn+B_1^'+(c_1)/(lnn)+(c_2)/((lnn)^2)+...,
(5)

where

B_1^'=B_1-t-1/6pi^2
(6)
=-1.83568427...
(7)

(OEIS A091588), where

 t=sum_(k=1)^infty1/(p_k^2)=0.452247...
(8)

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

c_1=gamma-1+2sum_(k=1)^(infty)(lnp_k)/(p_k(p_k-1))
(9)
=gamma-1+2sum_(k=2)^(infty)mu(k)(zeta^'(k))/(zeta(k))
(10)
=1.0879488865...
(11)
c_2=-gamma_1-(gamma-1)[gamma+2sum_(k=1)^(infty)(lnp_k)/(p_k(p_k-1))]+2sum_(k=1)^(infty)((2p_k-1)(lnp_k)^2)/(2p_k(p_k-1)^2)
(12)
=3.3231293098...
(13)

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

u=sum_(k=1)^(infty)(lnp_k)/(p_k(p_k-1))
(14)
=0.755366...
(15)
v=sum_(k=1)^(infty)((2p_k-1)(lnp_k)^2)/(2p_k(p_k-1)^2)
(16)
=1.183780...
(17)

(Finch 2003).

If n is a primorial, then

 omega(n)∼(lnn)/(lnlnn)
(18)

(Hardy and Wright 1979, p. 355).

The summatory function of omega(k) is given by

 sum_(k=2)^nomega(k)=nlnlnn+B_1n+O(n/(lnn))
(19)

where B_1 is the Mertens constant (Hardy 1999, p. 57), the o(n) term (Hardy and Ramanujan 1917; Hardy and Wright 1979, p. 355) has been rewritten in a more explicit form, and o(x) and O(x) 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,

 sum_(k=2)^n[omega(k)]^2=n(lnlnn)^2+O(nlnlnn)
(20)

(Hardy and Wright 1979, p. 357).

The first few numbers u_n 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). u_n satisfies

 sum_(n=1)^infty1/(u_n^s)=1/2[(zeta(s))/(zeta(2s))-zeta(s)]
(21)

(Hardy 1999, pp. 64-65). In addition, if U(n) is the number of u_k with k<=n, then

 U(x)∼(3x)/(pi^2)
(22)

(Hardy 1999, pp. 64-65).


See also

Dedekind Function, Distinct Prime Factorization, Divisor Function, Erdős-Kac Theorem, Greatest Prime Factor, Hardy-Ramanujan Theorem, Heterogeneous Numbers, Least Prime Factor, Mertens Constant, Prime Factor, Squarefree

Explore with Wolfram|Alpha

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 n." 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. http://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 n." Quart. J. Math. 48, 76-92, 1917.Hardy, G. H. and Wright, E. M. "The Number of Prime Factors of n" and "The Normal Order of omega(n) and Omega(n)." §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 E_n(Omega) and Var_n(Omega)." 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.

Referenced on Wolfram|Alpha

Distinct Prime Factors

Cite this as:

Weisstein, Eric W. "Distinct Prime Factors." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/DistinctPrimeFactors.html

Subject classifications