Rough number

Uses your system voice; voice and rate in settings.

Snapshot

≈ 2 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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.

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)

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.

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} \ge n for every 1 \le i \le k (while the condition is p_i^{r_i} \le 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

Notes

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, .

Text derived from https://en.wikipedia.org/w/index.php?oldid=1345440840 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

No external citation was extracted for this revision. That is a statement about the source, not a claim that none exists.