I am actually trying to solve the problem: "Beautiful Numbers", asked in Google Kickstart $2017$ Practice Round $2$ (Link: https://code.google.com/codejam/contest/12254486/dashboard#s=p2). The problem statement is:
Given an integer $N$, can you find a base $B$ (with $B > 1$) to write it in such that all of its digits become $1$? If there are multiple bases that satisfy this property, choose the one that maximizes the number of $1$ digits.
I have been trying to get some "number theoretic idea" for sometime (given that I am not quite good at it). I know that for a number $N$, $N-1$ is a solution. But it need not be the optimal solution, as per the question. Is there a "clever" way to think about it?
(Some pointers in the right direction will help -- I can type down the solution on my own)
In base $b$, the number $11...11$ can be computed using the geometric series, since ($k$ times)$111..111=b^{k−1}+b^{k−2}+...+1=\frac{b^{k−1}}{b−1}$. Therefore, it is enough to see if $N$ is of the form $b^k−1 \over b−1$ for some $b$. I am sure it is enough to check for $b$ up to some easy-to-compute bound in $N$. Certainly $k$ needs to be checked only up to $\log_2 N + 1$, since the maximum number of digits that $N$ has in any base is $\lfloor \log_2 N + 1 \rfloor$. Therefore, if we write $k$ in terms of $b$ and $r$, then we can see if any $1 \leq b \leq N$ works out. Certainly this is doable in short time.