sum of digits of a number in base B

Question

We are given a number $n$ in base $10$, now we have to find the sum of the digits of this number if it was written in base $B$. For example : if $n=216$ and $B=2$

$$216=2^7+2^6+2^4+2^3$$ so $216$ in binary would look like $11011000,$ now the sum of the digits in this will come out to be $4.$

Is it possible to find a function $f(n, B)$ that can give out this answer? If yes then what will it be?

PS: the second part of the problem... now we are given a number R.Find the value of B corresponding to which f(n, B) is minimum for all 2≤B≤R as i have to use this in a program can someone find a function or maybe an approach to solve this such that it can be computed very quickly as the numbers n and r can have values ranging from 2 to 10^12

Answer 1

The upper bound of the solution is $\lfloor \log_2(n)\rfloor +1$ because that's how many digits $n$ has in base $2$ (binary) and each of them is at most $1$. While programming you can just find $f(n, 2)$.

Now when $B>\lfloor \sqrt n \rfloor$ we have that $n$ has at most $2$ digits because $B^2>n$. Lets write a number in such base as $xB+y=n$ now we are wondering if we can find such $x, y$ such that $x+y<f(n, 2)$, lets rewrite $xB+y=n$ as $B=(n-y)/x$ now we iterate over $x+y=k$ where $1<k<f(n,2)$ and check if $B$ is an integer (smaller than $R$) , stop once you find such $B$ and $k$ is the minimum for $B>\lfloor \sqrt n \rfloor$.

Now you are left to find min of $f(n, B) $ where $B\leq\lfloor \sqrt n \rfloor$ which you can do by simply iterating.

Possible optimization is to repeat the process for $B>\lfloor n^{1/3} \rfloor$ just with $xB^2+yB+z=n$ here solving for $B$ it's marginally harder, anyway I leave this part to you to finish.

Answer 2

You could write it as a series. If $n>0$, we can write $$f(n,b) = \sum\limits_{k=1}^{+\infty}\left(\left\lfloor\frac{n}{b^{k-1}}\right\rfloor\; mod\; b\right)$$ Where $a\; mod\; b$ is the remainder of the division $a/b$ and $\lfloor r \rfloor$ is the greatest integer not exceeding $r$ (also known as floor function)