Find the nth number in the increasing sequence formed by 0,2,4,6,8?

Question

We have an increasing sequence in which each element is consist of even digits only (0, 2, 4, 6, 8). How can we find the nth number in this sequence

Is it possible to find nth number in this sequence in O(1) time.

Sequence: 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

The nth number in this sequence is n in base 5, with the digits doubled.

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)

This runs in O(log n) time. I don't think it's possible to do it in O(1) time.

It can be simplified a bit by combining the doubling of the digits with the generation of the base 5 digits of n:

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