TOPICS
Search

Rough Number


A k-rough number is a positive integer all of whose prime factors are greater than or equal to k (Finch 2001).

Greene and Knuth (1990) define "unusual numbers" as positive integers n>=2 whose greatest prime factor is greater than or equal to sqrt(n). This condition differs from being sqrt(n)-rough, which for n>=2 requires n to be a prime number or n=p^2 for a prime number p. For example, 6 is unusual but is not sqrt(6)-rough. The first few unusual numbers are 2, 3, 4, 5, 6, 7, 9, 10, 11, 13, ... (OEIS A063538), which turn out to not be so unusual after all (Greene and Knuth 1990, Finch 2001). Including 1 by convention, the first few "usual" numbers are 1, 8, 12, 16, 18, 24, 27, 30, ... (OEIS A063539).

Finch (2003, p. 166) calls n jagged when its greatest prime factor is strictly greater than sqrt(n). These numbers differ from unusual numbers by excluding numbers p^2 with p prime.

For an integer sampled uniformly from 1, 2, ..., m, the probability of obtaining n>=2 whose greatest prime factor exceeds sqrt(n) tends to ln2 as m->infty (Schroeppel 1972).


See also

Greatest Prime Factor, Round Number, Semiprime, Smooth Number

Explore with Wolfram|Alpha

References

Finch, S. "RE: Unusual Numbers." 27 Aug 2001. https://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind0108&L=NMBRTHRY&F=&S=&P=963.Finch, S. R. "Stieltjes Constants." §2.21 in Mathematical Constants. Cambridge, England: Cambridge University Press, pp. 166-171, 2003.Greene, D. H. and Knuth, D. E. Mathematics for the Analysis of Algorithms, 3rd ed. Boston, MA: Birkhäuser, pp. 95-98, 1990.Schroeppel, R. Item 29 in Beeler, M.; Gosper, R. W.; and Schroeppel, R. HAKMEM. Cambridge, MA: MIT Artificial Intelligence Laboratory, Memo AIM-239, p. 13, Feb. 1972. https://www.inwap.com/pdp10/hbaker/hakmem/number.html#item29.Sloane, N. J. A. Sequences A063538 and A063539 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

Rough Number

Cite this as:

Weisstein, Eric W. "Rough Number." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/RoughNumber.html

Subject classifications