位数全为1的最低基数系统

Question

我需要确定输入n(以10为基数)的最低位数制，在该数制中表示，其位数都是15。

例子:2进制下的7是111，合适!答案是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.

我有下面的代码，它可以很好地处理一定范围的数字，但对于巨大的数字算法仍然是耗时的:

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

如何优化当前代码使其运行得更快?

Answer 1

以b为基数的一串x1表示的数为b^(x-1) + b^(x-2) + ... + b^2 + b + 1。

注意，对于x >= 3，这个数字大于b^(x-1)(平凡)，小于(b+1)^(x-1)(应用二项式定理)。因此，如果数n在b的基数下用x表示，则得到b^(x-1) < n < (b+1)^(x-1)。应用x-1次方根，我们得到b < n^(1/(x-1)) < b+1。因此，要使b存在，b必须是floor(n^(1/(x-1))。

到目前为止，我已经用^符号而不是python风格的**语法写了一些东西，因为这些方程和不等式只适用于精确的实数算术，而不适用于浮点数。如果您尝试使用浮点数学计算b，舍入误差可能会使您的计算出错，特别是对于ULP大于1的超大输入。(我认为浮点数对于您正在使用的输入范围是可以的，但我不确定。)

尽管如此，不管浮点数是否足够好，或者你是否需要更花哨的东西，算法的思想是存在的:你可以通过直接计算相应的b必须是什么来直接检查x的值是否可行，并检查b基数中的x1s是否真的代表n。

Answer 2

只是一些小改动，稍微快一点，但不会提高时间复杂度。

def check_digits2(number, base):
while number % base == 1:
if number == 1:
return True
number //= base
return False

def get_min_base2(number):
for i in range(2, int(number**0.5) + 2):
if check_digits2(number, i):
return i
return number - 1

def test():
number = 100000010000001
start = time.time()
print(get_min_base(number))             # 10000000
print(f"{time.time() - start:.3f}sn")  # 3.292s
start = time.time()
print(get_min_base2(number))            # 10000000
print(f"{time.time() - start:.3f}sn")  # 1.731s

还尝试用一些数学技巧来接近，但我实际上使它更糟lol

def calculate_n(number, base):
return math.log(number * (base - 1) + 1, base).is_integer()

def get_min_base3(number):
for i in range(2, int(number**0.5) + 2):
if calculate_n(number, i):
return i
return number - 1

def test():
number = 100000010000001
start = time.time()
print(get_min_base3(number))            # 10000000
print(f"{time.time() - start:.3f}sn")  # 4.597s