## Is *n* a Perfect Power?

That means, is with . We don’t have to check all of the possible candidates, we can do a very large amount of argument reduction.

First observe that the greatest exponent possible comes with smallest base possible. The smallest base is 2, of course, so the largest possible exponent is .

By the Fundamental Theorem of Arithmetic together with the laws of exponentiation we can write the exponent as a product of prime powers and with and we can reduce the set of possible exponents to the set of primes; 16 in the case of the 53 bit long integers in JavaScript.

Can we reduce it further? Yes, by observing the maximum exponent for each base given a finite maximum for the number (that is, not for arbitrary large integers aka bigints simply because they have no maximum): the smaller the base the higher the maximum and vice versa. Lets take a look:

Base | Factors |
---|---|

2 | 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53 |

3 | 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 |

5 | 2, 3, 5, 7, 11, 13, 17, 19 |

7 | 2, 3, 5, 7, 11, 13, 17 |

11 | 2, 3, 5, 7, 11 |

13 | 2, 3, 5, 7, 11 |

17 | 2, 3, 5, 7, 11 |

19 | 2, 3, 5, 7 |

… | … |

181 | 2, 3, 5, 7 |

191 | 2, 3, 5 |

… | … |

1549 | 2, 3, 5 |

1553 | 2, 3 |

… | … |

208057 | 2, 3 |

208067 | 2 |

< 94906266 | 2 |

The number of primes in the range is quite large so just testing won’t make much sense for more than a small handful of bases, although it is mathematically elegant.

The next simple and general test would be . The problem here is the restricted precision of JavaScript and the quite simple implementations of `Math.pow()`

which doesn’t care for integers. This leads to results like `Math.pow(8916100448256,1/3) = 20735.999999999993`

(). The usual floating point tests for equality work only for tests very close to zero.

But we can round the result of if we test . That works because the exponentiation by makes the error two times larger and hence larger than the machine epsilon and a check would suffice but we can check against zero now because of the rounding..

We can even skip the test for base two because it is quite easy to check if a base 2 number is a power of two by just counting the bits: if the count comes up as zero or one it is a power of two. That makes three the smallest base which even triples the error from extracting the root.

Alternatively we could write an optimized integral root function but that is not necessary for JavaScript doubles as seen above. It will be necessary for Bigints, though.

Let’s sum it up for a positive integer x smaller than 53 bits:

*sqrt is optimized in most cases, so try it first*-

Further optimization could be to tak the first values from the large table, make a small table out of it (say, 3–17) and check if it divides the input evenly e.g.: .

D. J. Bernstein described in his paper “Detecting perfect powers in essentially linear time”[1] three different “levels” of such algorithms:

A

perfect-power detection algorithmis an algorithm that, given an integer , figures out whether is a perfect power. Aperfect-power decomposition algorithmdoes more: if is a perfect power, it finds and with . Aperfect-power classification algorithmdoes everything one could expect: it writes in the form with maximal.

[emphasis added by D. J. Bernstein]

As we already computed the root and have the exponent, although not the largest, we can do a perfect-power decomposition algorithm easily.

Number.prototype.isPerfPow = function(nroot){ // check if it is an positive integer omitted var primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53]; var root,log2,t; t = Math.abs(this); log2 = Math.floor(Math.log(t)/Math.LN2); // reduces the number of tries to 11. at most if(this.isPow2()) return true; // sqrt is optimized in most cases, so try it first root = Math.round(Math.sqrt(t)); if(t - (root * root) == 0){ if(arguments.length > 0){ nroot[0] = root; nroot[1] = 2; } return true } // cube root is only in the next ECMAScript standard, sadly for(var i=1;primes[i] <= log2;i++){ root = Math.round(Math.pow(t,1/primes[i])); if(t - (Math.pow(root,primes[i])) == 0){ if(arguments.length > 0){ nroot[0] = Math.round(root); nroot[1] = primes[i]; } return true } } return false; };

To get the numbers you have to pass a two element `Array`

to the function, but I think that is obvious 😉

To make it a perfect-power classification algorithm we need to recursively pass the root to the number until it fails and add the results up. With our example from above ( ) we get

Multiplying all together gives the highest possible exponent.

Another example (albeit base two gets done with a different algorithm)

Building the product gives

The maximum number of recursion is with base two, as expected:

I’ll leave the implementation for that to my dear readers 😉

[1]Bernstein, Daniel. “Detecting perfect powers in essentially linear time.” Mathematics of Computation of the American Mathematical Society 67.223 (1998): 1253-1283.