0
$\begingroup$

This was a programming problem but i thought this might be the correct forum for this doubt. The problem is called "Smallest Good Base" where you're asked to "for an integer n, find the smallest k where n base k are 1".

In some of the explanations i see

  1. Define base to be k, and number of digits to be m
  2. n = 1 + k^1 + k^2 + ... + k^(m-1)
  3. Using geometric sequence summation, we know n = (1 - k^m)/(1 - k)

How would we know number of digits? Let's say we're given n as 5, and we're testing base 2, what is m in that case?

$\endgroup$
0

1 Answer 1

0
$\begingroup$

I'll list two ways of finding the number of digits.

The first is to find the largest $m$ such that $k^{m-1} \leq n$. So in your example $2^{3-1} \leq 5$, but $2^{4-1} \not \leq 5$. Thus the numbers of digits is $3$.

A similar method is to take the floor of $\log_{k}(n)$ and add $1$. For instance, $1+\lfloor \log_{2}(5)\rfloor = 3$ implying that the number of digits is $3$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .