从1，2，3，……，1988，1989这些自然数中，最多可以取 个数使得每一个数都不是另一个数的两倍？

Question

如题所述

Answer 1

先取出当中所有的奇数。奇数一定不是任何整数的两倍，有 (1989+1)/2=995个。

再从偶数当中，将范围内奇数的 4^n倍的数挑选出来，它们也一定不是选出的另一个数的两倍，一定是四倍以上的倍数或者不是整数倍。选择 4^n作为系数，是因为4是只含有2质因数的大于2的最小可选数，能确保取出更多的数。

接下来计算取出偶数的数量。计算出相乘的最大奇数，就可以知道n对应的偶数数量。

n=1时，1989/4^1=497.25，最大奇数可以到497，一共有 (497+1)/2=249个；

n=2时，1989/4^2=124.31，最大可以到123，一共有 (123+1)/2=62个；

n=3时，1989/4^3=31.08，最大可以到31，一共有 (31+1)/2=16个；

n=4时，1989/4^4=7.77，最大可以到7，一共有 (7+1)/2=4个；

n=5时，1989/4^5=1.94，最大可以到1，只有1个；

上述取出偶数的总数是：249+62+16+4+1=332个。

上述两项合计，最多可以取出 995+332 = 1327个数，使得每一个数都不是另一个数的两倍。

又写了一段代码进行了枚举验证，结果相同。

附：计算结果和fortran代码

Answer 2

1989÷2=994……1
994+1=995
首先，在1到1989的自然数中，一共有995个奇数，1、3、5……1989这995个奇数都不是其他数的2倍。
其次，16、64、256、1024这四个偶数都不是奇数的2倍，也不是已列出的偶数的2倍。
1989÷4=497……1
497÷2=248
248+1=249
第三，1、3、5、7、……497，一共有249个奇数，这些奇数的4倍，都不是其他奇数的2倍，也不是已经列出的其他偶数的2倍。
995+4+249=1248
最多可以取1248个数，使得每一个数都不是另一个数的两倍。

Answer 3

解：把1，2，3…1998，1999这1999个数分成四组公差是4的等差的数列，
1，5，9，13…1983，1987----共497个数；
2，6，10，14…1984，1988----共497个数；
3，7，11，15…1985，1989----共497个数；
4，8，12，16…1982，1986----共496个数；
我们发现：1．四行中每一行中任意相邻两数相差为4，不相邻两数相差不可能是4；
2．而分属不同两行的任意两个数相差不可能为4，因为如果相差为4的话，两数将被归为一行，这显然与事实矛盾；
故我们用这样的方法来选符合规定的数：前三行每隔一个数选一个，每行最多可选249个数；第四行先选4，再隔一个数字选一个，可选出249个，最终得到249×4=996个数．
答：最多可以取996个数，才能使其中每两个数的差不等于4．

Answer 4

1989÷2=994......1
994÷2=497
497÷2=248......1
248÷2=124
124÷2=62
62÷2=31
31÷2=15......1
15÷2=7......1
7÷2=3......1
3÷2=1......1
1989-994+497-248+124-62+31-15+7-3+1=1327