找出由0、2、4、6、8组成的递增序列中第n个数是什么？

Question

我们有一个递增序列，其中每个元素都由偶数字（0、2、4、6、8）组成。如何找到该序列中的第n个数字？是否可以在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等。

- Godfather

---

n 从零还是从一开始？ - ankush yadav

我投票关闭此问题，因为它是一个作业任务的转储，显示出提问者零努力。 - S.L. Barth

查看这种类型问题时，你在网上的第一站应该是整数数列在线百科全书(OEIS)，对于数列0、2、4、6、8、20、22、24、26、28、40、42，它有如下内容。 - Lasse V. Karlsen

Answer 1

该序列的第n个数字是将n转换为5进制，并且将每个数字都乘以2得到的结果。

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

- Paul Hankin

---

@Paul Hankin：先生，您能告诉我您是如何解决这个序列的吗？ - Abhishek Tripathi

@Ram，我对你的帮助不大，但我立刻看出了这个数字与5进制的关系，从那里开始编写代码相对来说比较简单。上面评论中的Lasse建议检查OEIS中的序列——如果你没有看到它，那将是找到模式的好方法。 - Paul Hankin

Answer 2

int Code()
{
    k=0;
   for(i=0;i<=10000;i++)
   {
       count=0;
       n=i;
       while(n!=0)
       {
           c=n%10;
           n=n/10;
           if(c%2!=0)
           {
               count=1;
           }
       }
       if(count==0)
       { a[k]=i;
       k++;}
    }
 }

- api_48