I need to determine the lowest number base system in which the input n (base 10), expressed in this number base system, is all 1s in its digits.
Examples: 7 in base 2 is 111 - fits! answer is 2
21 in base 2 is 10101 - contains 0, does not fit
21 in base 3 is 210 - contains 0 and 2, does not fit
21 in base 4 is 111 - contains only 1 it fits! answer is 4
n is always less than Number.MAX_SAFE_INTEGER or equivalent.
I have the following code, which works well with a certain range of numbers, but for huge numbers the algorithm is still time consuming:
def check_digits(number, base):
res = 1
while res == 1 and number:
res *= number % base
number //= base
return res
def get_min_base(number):
for i in range(2, int(number ** 0.5) + 2):
if check_digits(number, i) == 1:
return i
return number - 1
How can I optimize the current code to make it run faster?
The number represented by a string of x 1s in base b is b^(x-1) + b^(x-2) + ... + b^2 + b + 1.
Note that for x >= 3, this number is greater than b^(x-1) (trivially) and less than (b+1)^(x-1) (apply the binomial theorem). Thus, if a number n is represented by x 1s in base b, we have b^(x-1) < n < (b+1)^(x-1). Applying x-1'th roots, we have b < n^(1/(x-1)) < b+1. Thus, for b to exist, b must be floor(n^(1/(x-1)).
I've written things with ^ notation instead of Python-style ** syntax so far because those equations and inequalities only hold for exact real number arithmetic, not for floating point. If you try to compute b with floating point math, rounding error may throw off your calculations, especially for extremely large inputs where the ULP is greater than 1. (I think floating point is fine for the input range you're working with, but I'm not sure.)
Still, regardless of whether floating point is good enough or if you need something fancier, the idea of an algorithm is there: you can directly check if a value of x is viable by directly computing what the corresponding b would have to be, and checking if x 1s in base b really represent n.