Intereting Posts

Show that derivative less than 1 implies contraction.
Integral of series with complex exponentials
Why are all the interesting constants so small?
special values of zeta function and L-functions
Why isn't an infinite direct product of copies of $\Bbb Z$ a free module?
Hidden subgroup problem for $\mathbb{Z} mod 2$
Representing a real valued function as a sum of odd and even functions
limit $\lim_{n\to ∞}\sin(\pi(2+\sqrt3)^n)$
What is a good book for a second “course” in group theory?
How to find $A=UDU^H$ in this case
$q$-norm $\leq$ $p$-norm
A non-trivial, non-negative, function bounded below by its derivative with $f(0)=0$?
how to derive the mean and variance of a Gaussian Random variable?
How many ways are there to arrange the letters in the word “mississippi” such that all “p” precede all “i”?
Mathematical Induction divisibility $8\mid 3^{2n}-1$

What better way to check if a number is a perfect power?

Need to write an algorithm to check if $ n = a^b $ to $ b > 1 $.

There is a mathematical formula or function to calculate this?

I do not know a or b, i know only n.

- Formal proof for detection of intersections for constrained segments
- Recurrence relation using substitution method
- merge sort vs insertion sort time complexity
- How can one find intermediate digits of a root of an algebraic equation?
- How to arrange functions in increasing order of growth rate , providing f(n)=O(g(n))
- Simplifying polynomials

- Where is the fallacy? $i=1$?
- modules with several powers $x^{y^z}$
- Find an algorithm to evaluate unknown polynomial of degree $n$ given its values for $x=0,x=1, x=2,\ldots,x=n$
- Non-revealing maximum
- Comparing $\pi^e$ and $e^\pi$ without calculating them
- Shortest Path with odd number of “Green” vertices
- Finding the location of an image of the Mandelbrot set
- How to understand why $x^0 = 1$, where $x$ is any real number?
- How do Gap generate the elements in permutation groups?
- Is there a log-space algorithm for divisibility?

It’s easy to see that increasing $b$ decreases $a$ (and vice versa). Since the smallest possible value of $a$ is $a_{\mathrm{min}}=2$, the largest useful value of $b$ to be tested is $b_{\mathrm{max}}=\lfloor\log_2 n\rfloor$. Thus, in order to check if $n$ is a perfect power, you only need to check whether any of its second, third, fourth, … $b_{\mathrm{max}}$-th roots is an integer. Assuming that your $n$ is (at most) a 64-bit integer, this estimate gives you $b_{\mathrm{max}}<64$, meaning that you wouldn’t need to check more than 62 different roots in any case.

There are a few further steps you can take:

- The identity $(a^x)^y = a^{xy}$ tells us that it’s sufficient to test only prime values of the exponent; if a number is a perfect power, it’s also a perfect power with prime exponent (the base is different, of course). This lowers the number of tested exponents to
*eighteen*. - The high exponents have very few possible bases they can be applied to without exceeding the $64$-bit range. For example, the exponents greater than $40$ can only correspond to base $2$. Instead of checking them using the “expensive” arithmetic, you can just have the possible values corresponding to these exponents hard-coded into the program and just compare the checked number against them. For example, storing the six values $2^{41}, 2^{43}, \ldots 2^{61}$ can save you checking six possible roots.
- Of course, one doesn’t need to stop at base $2$; a few more pre-calculated numbers and the maximum exponent can be lowered even further! For example, $38$ additional numbers can be used to eliminate exponents from $23$ onwards (leaving just eight to be checked) or $144$ (in total) to get down to just the four possible single-digit exponents ($2$, $3$, $5$ and $7$).

Somehow, I can show that the binary search algorithm is $O(lg~n \cdot (lg~lg~n)^2)$.

Firstly, $a^b = n$, there is $b<lg~n$.

**Binary Search Algorithm: **

For each $b$, we use binary search to find $a$.

Each time the computation of $a^b$ cost $lg~b = lg~lg~n$ operations by using **fast exponentiation**. Therefore,

the remaining issue is the range of $a$.

If $A$ is the maximal possible value of $a$, then binary search needs $lg~A$ operations

Note that $b~lg~a = lg~n$, that is

$$lg~A = \frac{lg~n}{b}$$

When summing up,

$$\sum lg~A = lg~n \cdot (\frac{1}{1} + \frac{1}{2} + … + \frac{1}{B}) = lg~n \cdot lg~B = lg~n \cdot lg~lg~n$$

In other words, all the operations for binary search is $O(lg~n \cdot lg~lg~n)$

Consider the operation of $a^b$, it is $O(lg~n \cdot (lg~lg~n)^2)$ finally.

ps: All the lg are base 2.

- Calculate sum of series $\sum \frac{n^2}{n!}$
- An expression that vanishes over every field
- The definition of span
- Binomial Expansion where N is negative
- An exercise on Regular Value Theorem
- Alternating sum of a simple product of binomial coefficients: $\sum_{k=0}^{m} (-1)^k \binom m k \binom n k .$
- Convergence of $\sum \frac{\sqrt{a_n}}{n^p}$
- $|x| – |y| \leq |x-y|?$
- Iterated means $a_{n+1}=\sqrt{a_n \frac{b_n+c_n}{2}}$, $b_{n+1}$ and $c_{n+1}$ similar, closed form for general initial conditions?
- Evaluating $\lim\limits_{n \to \infty }\sqrt{ \frac{\left | \sin1 \right |}{1}\cdot\cdot\cdot\frac{\left | \sin n \right |}{n}} $
- “Closest pair of points” algorithm
- Examples of Non-Noetherian Valuation Rings
- Induction Proof with a $\neq$ 1
- A series with only rational terms for $\ln \ln 2$
- Derivating in respect of a function that's a derivative of another function