生成数字序列，对于所有 k，从左到右的第 k 个数字总和为 10

Question

一个 Python 编码练习要求创建一个函数 f 使得 f(k) 是第 k 个数字，使得它从左到右的第 k 个数字总和为 10 k.例如 5, 19, 28, 37 是序列中的前几个数字。

我使用这个函数明确检查数字 'n' 是否满足属性:

def check(n):

    #even digit length
    if len(str(n)) % 2 == 0:

        #looping over positions and checking if sum is 10
        for i in range(1,int(len(str(n))/2) + 1):

            if int(str(n)[i-1]) + int(str(n)[-i]) != 10:

                return False

    #odd digit length
    else:

        #checking middle digit first
        if int(str(n)[int(len(str(n))/2)])*2 != 10:

            return False

        else:
            #looping over posotions and checking if sum is 10
            for i in range(1,int(len(str(n))/2) + 1):

                if int(str(n)[i-1]) + int(str(n)[-i]) != 10:

                    return False

    return True

然后我遍历所有数字以生成序列：

for i in range(1, 10**9):

    if check(i):
        print(i)

然而，练习需要一个函数 f(i) returns 在 10 秒内第 i 个这样的数字。显然，我的需要更长的时间，因为它生成了数字 'i' 之前的整个序列来计算它。是否可以制作一个不必计算所有先验数字的函数？

Answer 1

测试每个自然数是一种糟糕的方法。只有一小部分自然数具有此属性，并且随着我们进入更大的数字，该分数会迅速下降。在我的机器上，下面这个简单的 Python 程序用了 3 多秒来找到第 1,000 个数字 (2,195,198)，用了 26 多秒来找到第 2,000 个数字 (15,519,559)。

# Slow algorithm, only shown for illustration purposes

# '1': '9', '2': '8', etc.
compl = {str(i): str(10-i) for i in range(1, 10)}

def is_good(n):
    # Does n have the property
    s = str(n)
    for i in range((len(s)+1)//2):
        if s[i] != compl.get(s[-i-1]):
            return False
    return True

# How many numbers to find before stopping
ct = 2 * 10**3

n = 5
while True:
    if is_good(n):
        ct -= 1
        if not ct:
            print(n)
            break
    n += 1

显然，需要更高效的算法。

我们可以遍历数字字符串的长度，并在其中以数字顺序生成带有属性的数字。伪代码算法示意图：

for length in [1 to open-ended]:
    if length is even, middle is '', else '5'
    half-len = floor(length / 2)
    for left in (all 1) to (all 9), half-len, without any 0 digits:
        right = 10's complement of left, reversed
        whole-number = left + middle + right

现在，请注意每个长度的数字计数很容易计算：

Length    First    Last     Count
1         5        5        1
2         19       91       9
3         159      951      9
4         1199     9911     81
5         11599    99511    81

一般来说，如果left-half有n个数字，则计数为9**n。

因此，我们可以简单地遍历数字计数，计算存在多少个解决方案而无需计算它们，直到我们到达包含所需答案的群组。然后再次计算我们想要的数字应该相对简单，而不必遍历每一种可能性。

上面的草图应该会产生一些想法。编写代码后要遵循的代码。

代码：

def find_nth_number(n):
    # First, skip cohorts until we reach the one with the answer
    digits = 1
    while True:
        half_len = digits // 2
        cohort_size = 9 ** half_len
        if cohort_size >= n:
            break
        n -= cohort_size
        digits += 1

    # Next, find correct number within cohort

    # Convert n to base 9, reversed
    base9 = []
    # Adjust n so first number is zero
    n -= 1
    while n:
        n, r = divmod(n, 9)
        base9.append(r)
    # Add zeros to get correct length
    base9.extend([0] * (half_len - len(base9)))
    # Construct number
    left = [i+1 for i in base9[::-1]]
    mid = [5] * (digits % 2)
    right = [9-i for i in base9]
    return ''.join(str(n) for n in left + mid + right)

n = 2 * 10**3

print(find_nth_number(n))

Answer 2

这是一个利用模式的函数，其中相邻的 10 次方之间的 "valid" 个数字的数量是 9 的次方。这允许我们跳过很多数字。

def get_starting_point(k):
    i = 0
    while True:
        power = (i + 1) // 2
        start = 10 ** i
        subtract = 9 ** power
        if k >= subtract:
            k -= subtract
        else:
            break
        i += 1
    return k, start

我将其与您定义的方法相结合。假设我们对第 45 个数字感兴趣，这说明搜索从 1000 开始，我们只需要找到 1000 之后出现的第 26 个 "valid" 数字。它保证小于 10000。当然，这个界限在规模上变得越来越糟，你会想要采用其他社区成员建议的技术 post。

k = 45
new_k, start = get_starting_point(k)
print('new_k: {}'.format(new_k))
print('start at: {}'.format(start))
ctr = 0
for i in range(start, 10**9):
    if check(i):
        ctr += 1
        if ctr == new_k:
            break
print(i)

输出：

new_k: 26
start at: 1000
3827

第45个好像是3827

生成数字序列，对于所有 k，从左到右的第 k 个数字总和为 10

Generate sequence of numbers whose k-th digit from the left and from the right sums to 10 for all k

python

digits

sequence