Rough number

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.

Examples (after Finch)

1. Every odd positive integer is 3-rough.
2. Every positive integer that is congruent to 1 or 5 mod 6 is 5-rough.
3. Every positive integer is 2-rough, since all its prime factors, being prime numbers, exceed 1.

Powerrough numbers

Like powersmooth numbers, we define "n-powerrough numbers" as the numbers whose prime factorization $p_{1}^{r_{1}}\cdot p_{2}^{r_{2}}\cdot p_{3}^{r_{3}}\cdot \dots p_{k}^{r_{k}}$ has $p_{i}^{r_{i}}\geq n$ for every $1\leq i\leq k$ (while the condition is $p_{i}^{r_{i}}\leq n$ for n-powersmooth numbers), e.g. every positive integer is 2-powerrough, 3-powerrough numbers are exactly the numbers not == 2 mod 4, 4-powerrough numbers are exactly the numbers neither == 2 mod 4 nor == 3, 6 mod 9, 5-powerrough numbers are exactly the numbers neither == 2, 4, 6 mod 8 nor == 3, 6 mod 9, etc.

Sequences

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

See also

• Buchstab function, used to count rough numbers
• Smooth number

References

• Weisstein, Eric W. "Rough Number". MathWorld.
• 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.