northwolves在2010年1月提问，如何从$1 - 10^8$范围内选出尽量多的数字，使得它们两两之和互不相等。 northwolves他自己构造出了7069个数字。 经过大家的努力，在2018年这个结果被更新到10007个数字。

详细内容

数学星空首先给出了一个上界

由于每两个数的和均不相同,则N个数可构成$\frac{N\times(N-1)}2$个不同的数, 因两个数字之和最大值为$10^8+10^8-1$,最小值为$3$,则有 $\frac{N\times(N-1)}2\le 2\times 10^8-3$得:$N\le 20000$。
KeyTo9Fans 首先利用比较小的数字数目对应的范围内计算出数列
1,2,3,5,8,13,21,30
然后在OEIS找到了A011185
mathe找出了一种构造性方法
任意选择一个素数p使得$(p-1)p\lt 10^8$
对于$[0,(p-1)p]$的整数根据其关于模p-1和p的余数可以看成二维空间$(x,y)$中的整数点,其中$0\le x\lt p-1,0\le y\lt p$,取p的原根g,取点列$(i,g^i(mod p)),0\le i\lt p-1$,映射回去,可以得到一个p-1个数的例子 于是选择p=9973,那么就可以得出一种有9972个数字的方案。 并且他指出如果两两之和可以包含两个相同数字之和，那么问题就变成比较有名的 Optimal Golomb Ruler问题, 对应A003022。
northewolves建议大家先讨论范围在10000之内的情况，以便大家可以更加容易的交流结果
他指出KeyTo9Fans给出的A011185由于使用了额外的限制，结果不是最优的，比如1-10000之间这个序列只能去67个数，但是他可以给出70个数的方案
143, 288, 435, 584, 735, 888, 1043, 1200, 1288, 1449, 1612, 1706, 1873, 2042, 2142, 2315, 2419, 2596, 2704, 2885, 2997, 3182, 3298, 3416, 3607, 3729, 3853, 3979, 4178, 4308, 4440, 4574, 4710, 4848, 4988, 5130, 5274, 5420, 5568, 5718, 5870, 6024, 6109, 6267, 6427, 6589, 6682, 6848, 7016, 7115, 7287, 7390, 7566, 7673, 7853, 7964, 8148, 8263, 8380, 8570, 8691, 8814, 9010, 9137, 9266, 9397, 9530, 9665, 9802, 9941
显然mathe给出的描述太抽象了，大家表示很难看明白。直到wiley出手, 指出mathe给出的方案叫Ruzsa Construction, 并且给出mathematica代码

s={}; Do[s = Append[s, Mod[97*i + 96*5^i, 9312]], {i, 96}]; Print[Sort[s]]

范围在10000以内96个数据的结果
{86,96,117,305,364,365,369,412,538,577,605,619,791,815,916,938,953,1182,1350,1352,1377,1406,1495,1556,1695,1846,2259,2345,2450,2501,2594,2630,2649,2752,2851,2869,2979,3067,3125,3133,3348,3490,3647,3673,3679,3753,3810,4011,4045,4273,4338,4355,4400,4407,4440,4470,4516,4519,4560,4701,4856,4872,5008,5132,5226,5416,5491,5833,5871,5883,5966,6058,6142,6464,6980,6991,7000,7078,7091,7308,7438,7578,7649,7762,7815,7883,8060,8219,8292,8327,8613,8685,8762,8965,8988,9294}
可是mathe发现他推导的公式和wiley的略有不同，数学星空从网络上搜索结果验证wiley的公式是正确的。最终发现本来就可以有很多个构造方案
求一个素数p的原根g,就是相当于找一个元素,它模p的次数为p-1,于是我们对于p-1的任意因子d,$g^{\frac{p-1}d}\ne 1(mod p)$,而原根g的数目为$\varphi(p-1)$比例是非常高的,所以我们可以随便选择一些数,判断它是否是原根,直到找到一个原根就可以了. 而对于上面的构造方法,简单扩展一下,就可以发现实际上对于任何${a+b\times g^i\times(p-1)+i\times p|0\le i\lt p-1}$,只要$b\ne 0$,都可以构成一个解.所以通过适当的选择a和b,我们可以让最大元素适当的减少,比如对于10000,使用这种方法,选择素数101应该是问题不大的.
根据上面描述wiley马上做出更新，得到对于范围在10000以内可以找到101个元素
{1,168,238,293,300,435,440,451,482,491,736,738,1068,1105,1133,1695,1762,1839,1874,2003,2101,2109,2219,2367,2426,2452,2618,2638,2733,2746,2920,3159,3217,3309,3624,3805,3943,3962,4014,4173,4198,4222,4527,4603,4717,4804,5050,5082,5195,5278,5554,5558,5622,5651,5726,5729,5978,6271,6444,6561,6575,6804,7038,7044,7200,7426,7550,7604,7640,7767,7861,7952,7982,8093,8213,8247,8270,8292,8313,8352,8393,8641,8668,8714,8729,8767,8777,8851,8863,8932,9051,9101,9324,9454,9543,9587,9659,9811,9812,9829,9972}
而且wiley指出根据他给出的参考文献，最佳结果上界可以达到$n^{\frac12}+n^{\frac14}+1$。

mathe指出上面数据还可以通过平移得到更优结果, 并给出pari/gp代码找到102个元素
[1, 37, 64, 169, 174, 252, 352, 367, 563, 709, 950, 1145, 1221, 1519, 1550,1639, 1769, 1793, 1894, 1940, 1946, 1963, 2210, 2277, 2280, 2296, 2322, 2487, 2650, 2729, 2731, 2778, 2886, 2887, 2958, 3031, 3155, 3247, 3254, 3383, 3592, 3784, 4130, 4169, 4227, 4257, 4479, 4661, 4705, 4718, 4939, 4943, 4953, 5128, 5218,5278, 5331, 5385, 5418, 5590, 5684, 5750, 5848, 5970, 5981, 6010, 6129, 6243, 6264, 6328, 6584, 6612, 6750, 6798, 6830, 7043, 7093, 7134, 7227, 7245, 7283, 7406, 7414, 7457, 7532, 7638, 7733, 8000, 8261, 8322, 8812, 8880, 8889, 8954, 9097,9500, 9535, 9555, 9617, 9639, 9651, 9676]

gb(p)=
{
    local(r,v,m,u,d,di,bd,bv);
    v=vector(p-1);bv=vector(p-1);
    m=p*(p-1);bd=0;
    r=component(znprimroot(p),2);
    for(f=1,p-2,
       if(gcd(f,p-1)!=1,next());
       for(a=1,p-1,
          for(t=1,p-1,
            u=Mod(t*p*f,m)+a*(p-1)*Mod(r,m)^t;
            v[t]=component(u,2);
          );
          v=vecsort(v);
          d=m+v[1]-v[p-1];di=1;
          for(t=2,p-1,
             u=v[t]-v[t-1];
             if(u>d,d=u;di=t)
          );u=v[di];
          if(d>bd,
           for(t=1,p-1,
             if(v[t]>=u,bv[t]=v[t]-u+1,bv[t]=v[t]+m-u+1)
           );
           bv=vecsort(bv);bd=d
          )
       );
    );
    bv 
}

在2018年6月，mathe卷土重来，分别给出了范围在$10^8$以内时可以找到10006和10007个数字的满足条件的解。
可以把目标函数变为$a+b(p-1)g^{h-1}+c \times p \times h(mod p(p-1)), 0\le h\lt p-1$,其中由于我们只要找出${b(p-1)g^{h-1}+c \times p \times h(mod p(p-1)), 0\le h\lt p-1}$中数重排后相邻数最大的差值，就可以找出最优的a,所以上面代码中我们不需要穷举a,而是可以计算出来。 由于对于固定的$g$,存在$s$使得$b=g^s(mod p)$,所以上面公式平移后可以变为$a-c \times p \times s+(p-1)g^{h+s-1}+c \times p \times (h+s) (mod p(p-1))$,所以我们总可以选择$b=1$ 由此我们可以选择P=10007,g=5,求出 a=51625520, b=1, c=9579时，得到$10^8$之内有10006个数任意两数和不同的构造.
取P=10009,g=11,a=21661005,b=1,c=883, 去掉最大一个数可以得到10007个满足条件的解.
点击下载对应c代码