A ''k''-rough number, as defined by Finch in 2001 and 2003, is a positive
integer
An integer is the number zero (0), a positive natural number (1, 2, 3, ...), or the negation of a positive natural number (−1, −2, −3, ...). The negations or additive inverses of the positive natural numbers are referred to as negative in ...
whose
prime factor
A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
s 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
Congruence may refer to:
Mathematics
* Congruence (geometry), being the same size and shape
* Congruence or congruence relation, in abstract algebra, an equivalence relation on an algebraic structure that is compatible with the structure
* In modu ...
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
In number theory, an ''n''-smooth (or ''n''-friable) number is an integer whose prime factors are all less than or equal to ''n''. For example, a 7-smooth number is a number in which every prime factor is at most 7. Therefore, 49 = 72 and 15750 = 2 ...
Notes
References
*
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, .
The
On-Line Encyclopedia of Integer Sequences
The On-Line Encyclopedia of Integer Sequences (OEIS) is an online database of integer sequences. It was created and maintained by Neil Sloane while researching at AT&T Labs. He transferred the intellectual property and hosting of the OEIS to th ...
(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
Integer sequences
{{numtheory-stub