找到给定范围内的所有A ^ x

Question

我需要找到所有单项的形式的^X是评估时范围内从m到n.可以肯定地说,基数A大于1,功率X大于2,并且只需要使用整数.例如,在50到100的范围内,解决方案将是:

2^6
3^4
4^3

我解决这个问题的第一个尝试就是强行执行所有组合A并X使其"有意义".然而,当在大范围内用于非常大的数字时,这变得太慢,因为这些解决方案在更密集的处理中被使用.这是代码:

def monoSearch(min, max):
    base = 2
    power = 3

    while 1:
        while base**power < max:
            if base**power > min:
                print "Found " + repr(base) + "^" + repr(power) + "   = " + repr(base**power)    
            power = power + 1
        base = base + 1
        power = 3
        if base**power > max:
            break

我可以base**power通过将值保存在临时变量中来删除一个,但我认为这不会产生重大影响.我也想知道使用对数是否更好或者是否有一个封闭的表单表达式.我愿意接受任何优化或替代方案来寻找解决方案.

Answer 1

使用log(x)是一个递增函数的事实:

m <= a^x <= n 当且仅当 log(m) <= x * log(a) <= log(n)

然后找到数字x,log(a)其产品位于此变换的区间内将更容易.

Answer 2

不要搜索; 考虑端点.

例如,所有解决方案x == 3都a在多维数据集根m和多维数据集根之间n.因此,计算这些立方根并使用其间的整数范围.由于a至少为2,因此最大值x为log 2 n,因此您知道何时停止.

from math import log, ceil, floor

def monoSearch(low, high):
    max_power = int(floor(log(high) / log(2)))
    for power in range(3, max_power + 1):
        min_base = low ** (1.0 / power)
        max_base = high ** (1.0 / power)
        for base in range(int(ceil(min_base)), int(floor(max_base)) + 1):
            yield '%s ^ %s' % (base, power)

print '\n'.join(monoSearch(42, 1000000))

遗憾的是,由于浮点不精确,这可能会遗漏几个值.