Rough number
{{Short description|Positive integer with large prime factors}}
A k-rough number, as defined by Finch in 2001 and 2003, is a positive integer whose prime factors are all greater than or equal to k. k-roughness has alternately been defined as requiring all prime factors to strictly exceed k.p. 130, Naccache and Shparlinski 2009.
Examples (after Finch)
- Every odd positive integer is 3-rough.
- Every positive integer that is congruent to 1 or 5 mod 6 is 5-rough.
- Every positive integer is 2-rough, since all its prime factors, being prime numbers, exceed 1.
See also
- Buchstab function, used to count rough numbers
- Smooth number
Notes
{{reflist}}
References
- {{MathWorld|title=Rough Number|urlname=RoughNumber}}
- [http://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind0108&L=nmbrthry&P=963 Finch's definition from Number Theory Archives]
- "Divisibility, Smoothness and Cryptographic Applications", D. Naccache and I. E. Shparlinski, pp. 115–173 in Algebraic Aspects of Digital Communications, eds. Tanush Shaska and Engjell Hasimaj, IOS Press, 2009, {{isbn|9781607500193}}.
The On-Line Encyclopedia of Integer Sequences (OEIS)
lists p-rough numbers for small p:
- 2-rough numbers: A000027
- 3-rough numbers: A005408
- 5-rough numbers: A007310
- 7-rough numbers: A007775
- 11-rough numbers: A008364
- 13-rough numbers: A008365
- 17-rough numbers: A008366
- 19-rough numbers: A166061
- 23-rough numbers: A166063
{{Divisor classes}}
{{Classes of natural numbers}}
{{numtheory-stub}}