Lowest base system that has all 1s in its digits-CodePudding

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?

CodePudding user response：

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.

CodePudding user response：

Just some small twist, slightly faster but don't improve the time complexity.

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}s\n")  # 3.292s

    start = time.time()
    print(get_min_base2(number))            # 10000000
    print(f"{time.time() - start:.3f}s\n")  # 1.731s

Also try to approach with some math trick, but I actually make it worse 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}s\n")  # 4.597s