我需要确定最小的数字基数系统,在该数字基数系统中表示的输入n(基数10)都是数字中的1.

例如: 基数为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

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

推荐答案

b为基数的x个1的字符串表示的数字是b^(x-1) + b^(x-2) + ... + b^2 + b + 1.

请注意,对于x >= 3,这个数字大于b^(x-1)(微不足道),小于(b+1)^(x-1)(应用二项式定理).因此,如果一个数字n由以b为底的x个1表示,我们就有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式的**语法来编写代码,因为这些等式和不等式只适用于精确的实数算术,而不适用于浮点运算.如果您try 使用浮点数学计算b,舍入误差可能会扰乱您的计算,特别是对于ULP大于1的非常大的输入.(对于您正在使用的输入范围,I think浮点是可以的,但我不确定.)

尽管如此,不管浮点数是否足够好,或者如果你需要更花哨的东西,算法的 idea 都是存在的:你可以通过直接计算相应的b必须是什么来直接判断x的值是否可行,并判断b进制中的x 1是否真的代表n.

Python相关问答推荐

查找两极rame中组之间的所有差异

django禁止直接分配到多对多集合的前端.使用user.set()

我如何根据前一个连续数字改变一串数字?

什么是最好的方法来切割一个相框到一个面具的第一个实例?

dask无groupby(ddf. agg([min,max])?''''

Python pint将1/华氏度转换为1/摄氏度°°

如何根据rame中的列值分别分组值

使用嵌套对象字段的Qdrant过滤

如何将泛型类类型与函数返回类型结合使用?

用来自另一个数据框的列特定标量划分Polars数据框中的每一列,

上传文件并使用Panda打开时的Flask 问题

根据过滤后的牛郎星图表中的数据计算新系列

如何将列表从a迭代到z-以抓取数据并将其转换为DataFrame?

Django更新视图未更新

Stats.ttest_ind:提取df值

通过对列的其余部分进行采样,在Polars DataFrame中填充_null`?

我怎样才能让深度测试在OpenGL中使用Python和PyGame呢?

使用美汤对维基百科表格进行网络刮擦未返回任何内容

Groupby并在组内比较单独行上的两个时间戳

如何使用Pillow基于二进制掩码设置PNG的RGB值