Intereting Posts

Probability problem: cars on the road
What we can say about $-\sqrt{2}^{-\sqrt{2}^{-\sqrt{2}^\ldots}}$?
A subsequence of a convergent sequence converges to the same limit. Questions on proof. (Abbott p 57 2.5.1)
How to solve exact equations by integrating factors?
$2^{k} \mid {2k \choose 0} \cdot 3^{0} + {2k \choose 2} \cdot 3^{1} + \cdots + {2k \choose 2i} \cdot 3^{i} + \cdots + {2k \choose 2k} \cdot 3^{k}$
When do equations represent the same curve?
If $E \in \sigma(\mathcal{C})$ then there exists a countable subset $\mathcal{C}_0 \subseteq \mathcal{C}$ with $E \in \sigma(\mathcal{C}_0)$
What is meant by gluing two metric spaces together?
how to show that this complex series converge?
Why does a diagonalization of a matrix B with the basis of a commuting matrix A give a block diagonal matrix?
Why free presentations?
Assume $P$ is a prime ideal s.t. $K \subset P$, show $f(P)$ is a prime ideal
Absolutely continuous functions and the fundamental theorem of calculus
The general argument to prove a set is closed/open
How to Compute $\frac{d}{dx}\left(\left(1+x^2\right)^x\right)$?

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.

- Most Efficient Method to Find Roots of Polynomial
- Mathematically representing combinations with integers uniquely?
- Recurrence with varying coefficient
- How can I solve $8n^2 = 64n\,\log_2(n)$
- Development of a specific hardware architecture for a particular algorithm
- Implementation of Monotone Cubic Interpolation

- Rewriting repeated integer division with multiplication
- How to find out which number is larger without a calculator?
- gradient descent optimal step size
- Find numbers in a set whose sum equals x
- How to determine in polynomial time if a number is a product of two consecutive primes?
- Is there an irrational number $a$ such that $a^a$ is rational?
- Algorithm to compute Gamma function
- General McNugget problem
- Real analysis of powers
- Simply this exponential integral

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.

- Forming Partial Fractions
- To prove that $ + ++\dots ++$ is even.
- A condition for a subgroup of a finitely generated free abelian group to have finite index
- Subnets and finer filters
- A statement about divisibility of relatively prime integers
- Is there a “natural” topology on powersets?
- Representation of symmetric functions
- Proving bipartition in a connected planar graph
- If $g \circ f$ is surjective, show that $f$ does not have to be surjective?
- Show that the right half-open topology on $\mathbb R$ is not metrisable.
- Number of real roots of $\sum_{k=0}^{n}\frac{x^{k}}{k!}=0$
- The direct image of an ideal need not be an ideal
- For a polynomial $p(z)$ with real coefficients if $z$ is a solution then so is $\bar{z}$
- Can a continuous surjection between compacts behave bad wrt Borel probability?
- Gödel, Escher, Bach: $ b $ is a power of $ 10 $.