一个数论问题

Sirius

萨沙沿着圆周以任意顺序写了不多于100个互不相同的正整数，而季玛试图猜出它们的个数，为此，季玛以某种顺序告知萨沙一些号码，萨沙则从某一固定位置开始依顺时针方向，把季玛所说的号码所对应的位置上所写的数告诉季玛，季玛为了保证猜出圆周上数的个数，最少要告之多少个号码。

mathe

设M=[1,2,3,...,100]也就是前100个数的最小公倍数。
那么对于任意一个素数p,如果两个位置相差$M/p$而值相同，那么就说明圆周长度不是p的倍数；否则必然是p的倍数。
而对于大于11的所有21个素因子，必然不会同时出现，我们可以同时判断多个大于11的素因子来使用二分法判断出各个素因子是否为圆周长度的因子。
对于小于11的4个因子，可以在大素数因子确定的情况下，在设计方案缩小范围

Sirius

谢谢mathe老师，这个题目是第76届莫斯科数学竞赛的一道题，原题目的问题有2个，（1）季玛为了保证猜出圆周上数的个数，告之17个号码可以吗。（2）告之的号码少于16个可以吗。 第二个问题的答案也是这个思路，给出了15个号码可以保证猜出。
答案最后又说了一句最少的号码要比15小很多，这个就不太明白了。我感觉最少的号码应该比15小不了多少啊。

mathe

我也觉得应该可以远远小于15个号码。但是找最优解很难。

mathe

首先一次操作可以判断是否存在不小于11的素因子，如果存在，由于只有21种可能，5次二分法可以完全确定大于10的素因子。而对于小于10的素因子，2最多6次，3次二分法可以确定其次数。3最多4次 ，也最多判断3此次，5和7都最多判断两次。
这种简单方案累积已经最多需要1+5+3+3+2+2=16次了。如果我们考虑第一次判断后，不存在大于10的因子只需要再判断3+3+2+2,而存在大于10的因子，那么2最多3次，3最多两次，5,7最多一次，需要最多判断5+2+2+1+1,再加上第一次区分两种情况需要的方案，12次即可。
但是这方案显然远远不是最优的。

mathe

上面提到次数应该全部加一，也就是我们实际上只使用了第一次和后面各次的差值。如果设计良好，继续使用了后面各次之间的差值，会有更好的改善

Sirius

又算了一下，11个号码是可以的。