1

What is the largest number less than a given $N$ expressible as $b^e$, where $b,e\in\mathbb N$? For $N=10$ the answer is $3^2$; for $N=18$ the answer is $2^4$. Is there a procedure to find the correct $b$ and $e$?

Here $b$,$e$>1

Note: Only $N$ is provided. $b$,$e$ are not provided as part of question or input

Hemachandra
  • 13

1 Answers1

1

Given $N$ and a base $b$, it can be shown that the largest $e$ such that $b^e \leq N$ is equal to $\lfloor \log_b(N) \rfloor$. We don't know what the base is, but we can loop over different bases and see which one gives us the largest result. Thus, the largest number would be:

$$\max \{ b^{\lfloor \log_b(N) \rfloor} \mid b = 2, 3, 4 \dots ,\lfloor\sqrt{N}\rfloor \}.$$

EDIT: It suffices to only go up to $\lfloor\sqrt{N}\rfloor$ because if we pick $b > \lfloor\sqrt{N}\rfloor$, then $b > \sqrt{N}$ (since $b$ is an integer). Also, $e$ needs to be an integer bigger than 1, so $e \geq 2$. Thus, we would have $b^e > \sqrt{N}^2 = N$, a contradiction. Thus, $b$ must be no more than $\lfloor\sqrt{N}\rfloor$.

benguin
  • 3,846
  • Can you please explain the scenario if N=343? @benguin – Hemachandra Aug 13 '16 at 07:39
  • Sure. We want to iterate through all the bases from $2$ to $\lfloor \sqrt(343) \rfloor = \lfloor 18.52\dots \rfloor = 18$.

    Thus, we have $\max {b^{\lfloor \log_b(343) \rfloor} \mid b=2, 3, 4, \dots, 18} = {2^{\lfloor \log_2(343) \rfloor}, 3^{\lfloor \log_3(343) \rfloor}, \dots, 18^{\lfloor \log_{18}(343) \rfloor} }$. Computing each of these terms yields the set of numbers {256, 243, 256, 125, 216, 343, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289, 324} of which 343 is the biggest and corresponds to $b=7$, i.e., $343 = 7^{\lfloor \log_7{343} \rfloor} = 7^{\lfloor 3 \rfloor} = 7^3$.

     – benguin Aug 13 '16 at 07:49
  • Unless you want a number strictly less than 343, then 324 is the next largest number which corresponds to base $b=18$, i.e., $18^{\lfloor \log_{18} 343 \rfloor} = 18^{\lfloor 2.0197\dots \rfloor} = 18^2 = 324 < 343$. – benguin Aug 13 '16 at 07:56
  • 1
    This is so clear and easy to understand. Thanks for the clear cut explanation. – Hemachandra Aug 13 '16 at 09:58
  • No problem, I see you're more active in Stack Overflow so this kind of solution with a more computational/algorithmic flavor probably suits you best ;) – benguin Aug 13 '16 at 10:12
  • yep. I want to make that flavor.. ;) – Hemachandra Aug 13 '16 at 13:36