首页 > 代码库 > 乌拉姆数列 Euler167

乌拉姆数列 Euler167


昨天 yep 问了一个问题:


For two positive integers a and b, the Ulam sequence U(a,b) is defined by U(a,b)1 = a, U(a,b)2 = b and for k > 2, U(a,b)k is the smallest integer greater than U(a,b)(k-1) which can be written in exactly one way as the sum of two distinct previous members of U(a,b).

For example, the sequence U(1,2) begins with
1, 2, 3 = 1 + 2, 4 = 1 + 3, 6 = 2 + 4, 8 = 2 + 6, 11 = 3 + 8;
5 does not belong to it because 5 = 1 + 4 = 2 + 3 has two representations as the sum of two previous members, likewise 7 = 1 + 6 = 3 + 4.

Find ∑U(2,2n+1)k for 2 ≤ n ≤10, where k = 1011.



这题目很偏,不论是搜索还是通项都是没用的。


问了 5 个群(大家也不说话,反正都觉得事不关己,看谁憋得住 。。。)

最后是 laz 群里面给出了一点想法,虽然没有实质性答案;


后来直接在 google 上找到一位作者的题解:

def U( a, b ):
    u = [a,b]
    yield a
    yield b
    even, index = 0, 0
    
    while even == 0 or u[-1] < 2 * even:
        sums = {}
        for x in xrange( len( u ) ):
            for y in xrange( x + 1, len( u ) ):
                if sums.has_key( u[x] + u[y] ):
                    sums[u[x] + u[y]] += 1
                else:
                    sums[u[x] + u[y]] = 1
        u.append( min( k for k, v in sums.iteritems() if v == 1 and k > u[-1] ) )
        yield u[-1]
        if u[-1] % 2 == 0:
            even = u[-1]
        
    while even + u[index] <= u[-1]:
        index+=1 #find first index
    
    while True:
        if even + u[index] > u[-1] + 2:
            u.append( u[-1] + 2 )
        else:
            u.append( even + u[index + 1] )
            index += 2
        yield u[-1]


from time import clock

start = clock()
periods = [32, 26, 444, 1628, 5906, 80, 126960, 380882, 2097152]
diffs = [126, 126, 1778, 6510, 23622, 510, 507842, 1523526, 8388606]
target = 100000000000
total = 0

for i in range( 2, 11 ):
    u = U( 2, 2 * i + 1 )
    count = 0
    
    while count < 1000 or ( target - count ) % periods[i - 2] != 0:
        num = u.next()
        count = count + 1

    total += num + ( target - count ) * diffs[i - 2] / periods[i - 2]

stop = clock()

print total
print stop - start


可是看不懂作者的代码逻辑。


于是 “信息化”前辈质疑 diffs 之类的数据,是研究得到的,所以这题目可能偏向某个领域;

而我质疑 diffs 之类的数据是来源于打表;

最后还是未果。


突然想起有数列数据库 OEIS 这东西,就直接搜索了下 126, 126, 1778, 6510, 23622, 510, 507842,

发现是 A100730Fundamental difference of Ulam 1-additive sequence starting U(2, 2 * n + 1).


发现它原来是 Ulam 序列,属于数论的范畴。


关于乌拉姆序列:

乌拉姆数列是由乌拉姆在 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。这是个数学上的未解决问题。


题目有个特殊性,就是第一个参数为 2,第二个参数为 2 * n + 1,根据 Schmerl and Spiegel (1994) 证明得到,

Ulam( 2, 2 * n + 1 ),n >= 2,那么,整个乌拉姆数列里面只可能有两个整数;

Finch 1991 证明,若是乌拉姆数列中存在无数的偶数,就存在周期性差分。


那么上述的代码就很容易理解了,其实 函数 U 中的最可怕的时间耗费在第一个 while 上,

但是由于只需要找出整个序列中第二的偶数,剩下的时间复杂度就会变得很少,成了线性的。

剩下的奇数只可能由 u[-1] + 2 和 even + u[index + 1] 次小的一个组成,

花点时间就能揣测出代码的用意了。


*** 不理解的是 import 下面的周期性差分怎么解释 ***






乌拉姆数列 Euler167