0

Given a range $[a, b]$, how does one find the smallest perfect power contained in the range? i.e., find $a \le k^m \le b$ where $a, b \in \mathbb{R_{\ge 0}}$ and $k, m \in \mathbb{Z_{\ge 0}}, m \ge 2$.

If $N(x)$, is the counting function for perfect powers $\le x$, then $N(x) \sim \sqrt x, x \to \infty $ as squares dominate the perfect powers.

What I have so far is a procedure for searching squares in the range $[\lceil \sqrt a \rceil, \lfloor \sqrt b \rfloor]$. My intuition is to find the smallest square in this range, say $x_2^2$ and then narrow the range to $[a, x_2^2 - 1]$ and search for perfect cubes in the narrowed range and so on. We stop when the range has just one element i.e., $a$ and return the smallest perfect power that we have kept track of.

Am I right? Is there a better way?

vvg
  • 3,311

1 Answers1

1

This can be done without searching, merely by calculating: The smallest perfect power larger than $a$ is the minimum of the numbers $$ \lceil a^{1/2} \rceil^2,\ \lceil a^{1/3} \rceil^3,\ \lceil a^{1/4} \rceil^4,\ \dots,\ \lceil a^{1/k} \rceil^k $$ where we can stop as soon as $2^k > \lceil a^{1/2} \rceil^2$ (so roughly $k=\log_2 a$). This is easy to calculate, and then one discovers whether it's less than or equal to $b$ or not (if not then there are no perfect powers in the interval).

Greg Martin
  • 78,820