烏拉姆數列

烏拉姆數列是由烏拉姆在1964年提出的。數列的首兩項U1和U2定義為1和2,對於n>2,Un為最小而又能剛好以一種方法表達成之前其中兩個相異項的和。例如3=1+2,故U3=3;4=1+3(注意2+2不計算在內),故U4=4;5=2+3=1+4,所以它不在數列內。首幾項是1, 2, 3, 4, 6, 8, 11, 13, 16, 18, 26, 28, 36, 38, 47, 48, 53, 57, 62, 69, 72, 77, 82, 87, 97, 99...(OEIS:A002858

烏拉姆猜想這個數列密度為0,但它似乎約為0.07396。這是個數學上的未解決問題。

编程实现(python)

L = [0] * 100000
ans = [1,2] 
while len(ans) < 100:
    x = ans[len(ans)-1]
    flag = False
    for i in range(len(ans)-1): # generate the successive number by the known numbers
        if flag == False and L[x + ans[i]] == 0: # find a possible proper number x+ans[i]
            for j in range(x+ans[i]): # check if there is a smaller proper number than x+ans[i]
                if L[j] == 1:
                    ans.append(j)
                    L[j] = 2;
                    break
            else:
                ans.append(x + ans[i])
                L[x + ans[i]] = 2;
            flag = True
        L[x+ans[i]] += 1
print(ans)

參考

  • Guy, Richard (2004), Unsolved Problems in Number Theory (3 ed.), Springer-Verlag, ISBN 0-387-20860-7