Like the title says, I'm trying to make a program that finds the highest natural radix of a given number with a natural output. My program works, but it loops every number possible number up to a certain limit, which can give obvious problems and performance issues.
Example (let's say the limit is 1000, so it loops from base 2-1000):
Log7(117649) = 6 |Base = 7 -->OK
Log49(117649) = 3 |Base = 49 -->OK
Log343(117649) = 2 |Base = 343 -->OK (highest)
Log6(117649) = 6.516198795 |Base = 6 -->Wrong because output is not a natural number
From the example you see that base 343 is the highest base possible.
Now I was wondering if there's a way to find the numbers 7-49-343. Or even just one of them without doing it my way(which is just looping through numbers)
Is there some formula or rule I'm missing? Any suggestion on how to tackle this in a different way is very much appriciated.
Find the prime factorization of your number $n$ and take the greatest common divisor $d$ of the exponents. Then $\sqrt[k]n$ is an integer if and only if $k$ divides $d$ (and we may also want $k>1$). You want the radix base to be as big as possible, i.e., you are looking for the smallest $k$. If $d>1$, that would be $\sqrt[p]n$ where $p$ is the smallest prime dividing $d$.
In your example, the prime factorization is $n=7^6$. So $d=6$, which tells us that $\sqrt[6]n=7$, $\sqrt[3]n=7^2$, $\sqrt[2]n=7^3$ are integers, the last being the biggest because $2$ is the smallest prime dividing $d$.
Another example: $n=125000000$. The prime factorization is $n=2^65^9$, so $d=\gcd(6,9)=3$ and the smallest (and only) prime $p$ dividing $d$ is $p=3$. So here the largest integer radix is $\sqrt[3]{125000000}=500$. Finally, it may happen that $d=1$ (for example when $n=72=2^33^2$); in such a case, no radix base is integer.