任意两项差的绝对值均不等的自然数数列

LZC_314

对于自然数数列 An，满足以下条件：
1，数列是递增的
2，任意两项的差的绝对值都不相等
3，数列的最后一项要尽可能第小
问题：
给定项数 n，求出满足上述要求的最小数列
（注：这里说的最小，是指数列的最后一项最小）
例如：
n=2，  0,1
n=3，  0,1,3
n=4，  0,1,4,6
.......
n=10   0,1,6,10,23,26,34,41,53,55
上述数据是用程序计算出来的，想问一下有没有公式或者数学方法能够算出最后一项？

mathe

optimal Golomb rulers

aimisiyou

n=5时，结果是0,1,6,9,11吧！

BeerRabbit

OEIS上居然没有收录

LZC_314

对于给定的n，符合条件的不止一个，我通过程序计算，只能想到暴力的方法，非常耗时间，下面再给出几组例子，看看有没有规律可循：
n=5:  0,1,4,9,11 or 0,3,4,9,11
n=6:  0,1,4,10,12,17  or   0,1,4,10,15,17  or  0,3,5,9,16,17  or   0,4,6,9,16,17
n=7:  0,1,4,10,18,23,25  等五组
n=8： 0,1,4,9,15,22,32,34
n=9： 0,3,9,17,19,32,39,43,44
n=10： 0,1,6,10,23,26,34,41,53,55
我是用暴力搜索数字的所有组合情况，从中找到符合条件的，但是时间复杂度太大，几乎是指数级别的。有没有数学方法可以计算出某一项的最后一个数字，不用把整个数列算出。

aimisiyou

其实此题等效于求 \(\min(x_1+x_2+……+x_{n-1})\)
\(x_i\) 为互不相等的自然数且不存在连续几数之和相等的情形
如\(x_i+x_{i+1}+x_{i+2}+……+x_{i+k}=x_{j}+x_{j+1}+x_{j+2}+……x_{j+t}\)形式，\(k、t>=0\)
当n=4时，\(\min(1+3+2)=6\)；
当n=5时，\(\min(1+3+5+2)=11\)；
当n=6时，\(\min(1+3+6+5+2)=17\)；
当n=7时，\(\min(1+3+6+8+5+2)=25\)；
当n=8时，\(\min(1+3+5+6+7+10+2)=34\)；
当n=9时，\(\min(3+6+8+2+13+7+4+1)=44\)；
当n=10时，\(\min(1+5+4+13+3+8+7+12+2)=55\).

liangbch

我想到的算法也只是背包算法，主要改进也只是在剪枝方面优化。

liangbch

想看看《optimal Golomb rulers》，打惜wiki page 打不开，只好作罢。

mathe

wiki部分复制:
Methods of construction[edit]
A number of construction methods produce asymptotically optimal Golomb rulers.

Erdős–Turan construction[edit]
The following construction, due to Paul Erdős and Pál Turán, produces a Golomb ruler for every odd prime p.[12]

2pk+(k^{2}\,{\bmod {\,}}p),k\in [0,p-1]
Known optimal Golomb rulers[edit]
The following table contains all known optimal Golomb rulers, excluding those with marks in the reverse order. The first four are perfect.

order        length        marks        discovered[*]        discoverer
1        0        0               
2        1        0 1               
3        3        0 1 3               
4        6        0 1 4 6               
5        11        0 1 4 9 11
0 2 7 8 11        1967?[18]        John P. Robinson and Arthur J. Bernstein
6        17        0 1 4 10 12 17
0 1 4 10 15 17
0 1 8 11 13 17
0 1 8 12 14 17        1967?[18]        John P. Robinson and Arthur J. Bernstein
7        25        0 1 4 10 18 23 25
0 1 7 11 20 23 25
0 1 11 16 19 23 25
0 2 3 10 16 21 25
0 2 7 13 21 22 25        1967?[18]        John P. Robinson and Arthur J. Bernstein
8        34        0 1 4 9 15 22 32 34        1972[18]        William Mixon
9        44        0 1 5 12 25 27 35 41 44        1972[18]        William Mixon
10        55        0 1 6 10 23 26 34 41 53 55        1972[18]        William Mixon
11        72        0 1 4 13 28 33 47 54 64 70 72
0 1 9 19 24 31 52 56 58 69 72        1972[18]        William Mixon
12        85        0 2 6 24 29 40 43 55 68 75 76 85        1979[18]        John P. Robinson
13        106        0 2 5 25 37 43 59 70 85 89 98 99 106        1981[18]        John P. Robinson
14        127        0 4 6 20 35 52 59 77 78 86 89 99 122 127        1985[18]        James B. Shearer
15        151        0 4 20 30 57 59 62 76 100 111 123 136 144 145 151        1985[18]        James B. Shearer
16        177        0 1 4 11 26 32 56 68 76 115 117 134 150 163 168 177        1986[18]        James B. Shearer
17        199        0 5 7 17 52 56 67 80 81 100 122 138 159 165 168 191 199        1993[18]        W. Olin Sibert
18        216        0 2 10 22 53 56 82 83 89 98 130 148 153 167 188 192 205 216        1993[18]        W. Olin Sibert
19        246        0 1 6 25 32 72 100 108 120 130 153 169 187 190 204 231 233 242 246        1994[18]        Apostolos Dollas, William T. Rankin and David McCracken
20        283        0 1 8 11 68 77 94 116 121 156 158 179 194 208 212 228 240 253 259 283        1997?[18]        Mark Garry, David Vanderschel et al. (web project)
21        333        0 2 24 56 77 82 83 95 129 144 179 186 195 255 265 285 293 296 310 329 333        8 May 1998[19]        Mark Garry, David Vanderschel et al. (web project)
22        356        0 1 9 14 43 70 106 122 124 128 159 179 204 223 253 263 270 291 330 341 353 356        1999[18]        Mark Garry, David Vanderschel et al. (web project)
23        372        0 3 7 17 61 66 91 99 114 159 171 199 200 226 235 246 277 316 329 348 350 366 372        1999[18]        Mark Garry, David Vanderschel et al. (web project)
24        425        0 9 33 37 38 97 122 129 140 142 152 191 205 208 252 278 286 326 332 353 368 384 403 425        13 October 2004[5]        distributed.net
25        480        0 12 29 39 72 91 146 157 160 161 166 191 207 214 258 290 316 354 372 394 396 431 459 467 480        25 October 2008[6]        distributed.net
26        492        0 1 33 83 104 110 124 163 185 200 203 249 251 258 314 318 343 356 386 430 440 456 464 475 487 492        24 February 2009[7]        distributed.net
27        553        0 3 15 41 66 95 97 106 142 152 220 221 225 242 295 330 338 354 382 388 402 415 486 504 523 546 553        19 February 2014[8]        distributed.net
^ * The optimal ruler would have been known before this date; this date represents that date when it was discovered to be optimal (because all other rulers were proven to not be smaller). For example, the ruler that turned out to be optimal for order 26 was recorded on 10 October 2007, but it was not known to be optimal until all other possibilities were exhausted on 24 February 2009.

mathe

分布式计算网站:
http://www.distributed.net/OGR