0

Given a $ a \in \mathbb N $, what is the lowest $ b \in \{1, ..., a \} $ for which $ log_b a \in \mathbb N $ ? How to compute this function in a non-iterative way?

Examples (even if too obvious):
$ a = 1 \Rightarrow b = 1 $,
$ a = 2 \Rightarrow b = 2 $,
$ a = 3 \Rightarrow b = 3 $,
$ a = 4 \Rightarrow b = 2 ...$,

nightcod3r
  • 365

2 Answers2

1

We have $a = b^{\log_b a}$, therefore $e := \log_b a$ is an integer iff $a$ is a power of $b$.

To find $e$ and therefore $b = a^{1/e}$, consider the prime factorization $a=p_1^{e_1}\cdots p_n^{e_n}$. This gives a prime factorization $b = p_1^{e_1/e}\cdots p_n^{e_n/e}$, so $e$ must be the greatest common divisor of $e_1, \ldots, e_n$.

Anon
  • 5,489
  • As I can see in the answers offered, the solution would always mean computing prime factorization, which is an iterative process in itself. Any other more-straightforward option? – nightcod3r May 28 '16 at 10:52
  • You could just go ahead and check for all the integers $e'$ from $\lfloor log_2 a \rfloor$ to $1$ whether $a^{1/e'}$ is an integer. The first such integer you find is $b$. Clearly there aren't that many $e'$ to check. – Anon May 28 '16 at 22:49
  • Then again, you specified that you wanted a non-iterative method. Any particular reason for that? – Anon May 28 '16 at 22:50
  • A formula would be preferred just for the sake of reducing computational time in an implementation. – nightcod3r May 28 '16 at 23:20
  • Dude, if $a$ is a standard 4-byte integer, then you need to check at most 32 possible $e'$, There's no way any other implementation would be significantly faster than that. – Anon May 29 '16 at 08:42
1

If $a=p_1^{n_1} p_2^{n_2} .. p_k^{n_k}, \ p_i $ prime and $d=GCD(n_1,n_2, .. n_k)$. Let $b=p_1^{\frac {n_1} d} .. p_k^{\frac {n_k} d}$. Then $b^d=a$ and $b$ minimal by construction.

  • As I can see in the answers offered, the solution would always mean computing prime factorization, which is an iterative process in itself. Any other more-straightforward option? – nightcod3r May 28 '16 at 10:52
  • @nightcod3r No, it's $d$ not $a$. –  May 28 '16 at 11:19
  • @nightcod3r So basically you want a formula for $b$? –  May 28 '16 at 11:22
  • Yes, a formula is what I would rather prefer to use. Please, check out the subscript of the last factor in the definition of $ b $. – nightcod3r May 28 '16 at 11:35
  • @nightcod3r I've made the corrections. –  May 28 '16 at 11:41
  • We should consider here the case of $ k = 1 $, so the $ GCD(n_1) $ is not defined. – nightcod3r May 28 '16 at 22:53
  • Plus the special case of $ a = 1 \Rightarrow b = 1 $. – nightcod3r May 28 '16 at 23:22
  • For $k=1$, $GCD(n_1)=n_1$ so is perfectly fine. If $a=1$ there is no $b$ because for $log_b a$ to exist, the condition $b \ne 1$ in necessary. –  May 29 '16 at 04:43
  • Gosh, that's incongruent with the definition of the gcd function in GNU Octave 3.8.1, which demands more than one argument, didn't know that the GCD function is defined also for a single number (the 'C' misleads here). – nightcod3r May 29 '16 at 08:11
  • Don't quite understand the problem with $ a = 1 $. In this case, $b$ could take any natural value, since $log_b 1 = 0$. – nightcod3r May 29 '16 at 08:13
  • @nightcod3r See https://en.wikipedia.org/wiki/Logarithm Also GCD demands more than one argument, but doesn't require them to be distinct –  May 29 '16 at 08:55