How to reduce the search space for the base?

@JohnPham He asked this problem https://leetcode.com/contest/leetcodeweeklycontest16b/problems/smallestgoodbase/

Hey ,
I have written an editorial , reply if you have doubt
https://discuss.leetcode.com/topic/76332/acceptedsolutioninpython

think about it in a different way, don't search the base up, since the example has given you 9999999999999999, it must timeout. Try to think about how many 1s to represent n using each base. Then you can get something like this
floor(log(n, 2))
Since the biggest n is 10^18 and base 2 has the longest 1s, which is about 60.
Just binary search it and verify.
Hope it helps

@zhongyuan9817 can you exactly explain what is that supposed to mean ? For instance I have to search for n = 10x10^18, so the largest 1s are of 2 which are 60. So, what exactly are you suggesting from binary search, can you elaborate a bit more.
On what matrices we have to use binary search, you can provide with a testcase just for a simple number for instance 10 or 100 or 1000.

@junaidnu1 Take a look at this
https://discuss.leetcode.com/topic/76347/3msacclonglongintbinarysearch

It can be mathematically proved that
 the upper bound for number of digits
d
≤log
_{2}(N+1)
.
And then the good base
k
will be uniquely determined byd
.By the way, the search of
k
should always go byd
from upper bound down because the larger thed
, the smaller thek
.I have a post here if you are interested:
10liner 3ms really TIGHT search bounds with time complexity analysis O((logN)^2) (detailed explanation)
 the upper bound for number of digits