首页 > 代码库 > 乌拉姆数列 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