An integer is -smooth if it has no prime factors . The following table gives the first few -smooth numbers for small . Berndt (1994, p. 52) called the 7-smooth numbers "highly composite numbers."
OEIS | -smooth numbers | |
2 | A000079 | 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, ... |
3 | A003586 | 1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, ... |
5 | A051037 | 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, ... |
7 | A002473 | 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, ... |
11 | A051038 | 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, ... |
The probability that a random positive integer is -smooth is , where is the number of -smooth numbers . This fact is important in application of Kraitchik's extension of Fermat's factorization method because it is related to the number of random numbers which must be examined to find a suitable subset whose product is a square.
Since about -smooth numbers must be found (where is the prime counting function), the number of random numbers which must be examined is about . But because it takes about steps to determine if a number is -smooth using trial division, the expected number of steps needed to find a subset of numbers whose product is a square is (Pomerance 1996). Canfield et al. (1983) showed that this function is minimized when
(1)
|
and that the minimum value is about
(2)
|
In the continued fraction factorization algorithm, can be taken as , but in Fermat's factorization method, it is . is an estimate for the largest prime in the factor base (Pomerance 1996).
The curiosity
(3)
|
involves the largest consecutive 19-smooth numbers, 11859210 and 11859211.