Definition of a powersmooth number

Question

I understand the basic definition of a smooth & powersmooth number.

• Let $B$ be an integer. An integer $N$ is called $B$-smooth if every prime factor $p$ of $N$ is less than $B$
  $N = 2^{78} · 3^{89} · 11^3$ is called as a $12$-smooth number

• A number is said to be $B$-powersmooth if every prime power dividing $N$ is less than $B$. $N = 2^5 · 3^3$ is $33$-powersmooth (the biggest prime power is $2^5$ which is 32)

I also found a different defintion of powersmooth

• An integer $N$ is said to be $B$-powersmooth if it is a product of coprime numbers less than $B$.

I am unable to understand this definition. Can someone give an example for this & how it co-relates with the other definition?

Answer 1

Let's try to put this in an actual answer. First: a number that is $B$-powersmooth is also $(B+z)$-powersmooth for any positive integer $z$. (Also true for smooth.)

For instance, your first example, $2^5 \cdot 3^3$ is $33$-powersmooth, because $2^5 < 33$ and $3^3 < 33$. But $32$ and $27$ are also both less than, say, $53$, and $175$, and $2021$. So $864$ is $33$-powersmooth, but is also $2021$-powersmooth and $10^{1000}$-powersmooth.

The issue here is that we want to find the lowest possible $B$, in general.

The second definition you give is "An integer $N$ is said to be $B$-powersmooth if it is a product of coprime numbers less than $B$." That is:

$$(N = abc\cdots Q) \land (a < b < c < \cdots < Q) \land (a,b,c,\cdots Q) = 1 \implies N \text{ is } (Q+1)\text{-powersmooth}$$

Since we only really care about the smallest possible $B$, it makes sense to find the product of the smallest possible coprime integers. Those smallest coprime integers will be the individual terms in the prime factorization $N = \prod p_i^{a_i}$.

This is essentially the same as the first definition; it's just that the first definition is a lot more explicit.

Edit to add: The first definition is:

$$(N = \prod_{i=1}^k p_i^{a_i}) \land (B > p_1^{a_1}, B > p_2^{a_2}, \dots B > p_k^{a_k}) \implies N \text{ is } B \text{-powersmooth}$$

But we can rewrite the prime-power factorization as $N = abc \cdots B$. WLOG, we can order the prime powers by size so that $p_1^{a_1} < p_2^{a_2} < \cdots < p_k^{a_k} < B$. And since the terms are all prime powers, we know they're coprime: $(p_1^{a_1}, p_2^{a_2}, \dots p_k^{a_k}) = 1$. Hopefully you see how these can be directly substituted into the second definition as I wrote it above.