galois.is_smooth

galois.is_smooth(n: int, B: int) bool

Determines if the integer \(n\) is \(B\)-smooth.

Parameters
n: int

An integer.

B: int

The smoothness bound \(B \ge 2\).

Returns

True if \(n\) is \(B\)-smooth.

Notes

An integer \(n\) with prime factorization \(n = p_1^{e_1} \dots p_k^{e_k}\) is \(B\)-smooth if \(p_k \le B\). The \(2\)-smooth numbers are the powers of \(2\). The \(5\)-smooth numbers are known as regular numbers. The \(7\)-smooth numbers are known as humble numbers or highly composite numbers.

Examples

In [1]: galois.is_smooth(2**10, 2)
Out[1]: True

In [2]: galois.is_smooth(10, 5)
Out[2]: True

In [3]: galois.is_smooth(12, 5)
Out[3]: True

In [4]: galois.is_smooth(60**2, 5)
Out[4]: True

Last update: Apr 21, 2022