找到由0,2,4,6,8形成的递增序列中的第n个数字？

Question

我们有一个递增的序列,其中每个元素仅由偶数位组成(0,2,4,6,8).我们怎么样find the nth number in this sequence

是否有可能在O(1)时间内找到此序列中的第n个数字.

序列: 0, 2, 4, 6, 8, 20, 22, 24, 26, 28, 40, 42, 44, 46, 48, 60, 62, 64, 66, 68, 80, 82, 84, 86, 88, 200, 202 and so on.

Answer 1

该序列中的第n个数字是基数为5的n,数字加倍.

def base5(n):
    if n == 0: return
    for x in base5(n // 5): yield x
    yield n % 5

def seq(n):
    return int(''.join(str(2 * x) for x in base5(n)) or '0')

for i in xrange(100):
    print i, seq(i)

这在O(log n)时间内运行.我认为不可能在O(1)时间内完成.

通过将数字的加倍与n的基数为5的数字的生成相结合,可以简化一点:

def seq(n):
    return 10 * seq(n // 5) + (n % 5) * 2 if n else 0