设N是正整数,如果存在大于1的正整数k,使N-[k(k-1)/2]是k的正整数倍,则N称为一个千禧数,试确定在1,2,3……2000中千禧数的个数,并说明理由

Question

设N是正整数,如果存在大于1的正整数k,使N-[k(k-1)/2]是k的正整数倍,
则N称为一个千禧数,试确定在1,2,3……2000中千禧数的个数,并说明理由

Answer 1

这个没写错么?按这个定义那基本上都是的,除了2的幂
对任意N,设 N = k(k-1)/2 + nk 所以 2N = k(k+2n-1)
为了找到合适的k,只要把2N分成两个整数的乘积,因为这两个整数的差是2n-1的形式,也就是说这两个整数奇偶性要不同.因为2N必定是偶数,所以必定分成a * b的形式,其中a是2的整数次幂,b是个奇数,这个分法肯定存在而且唯一.这样a,b中较小的一个就是k,较大的一个就是 k+2n-1,两个的差就是2n-1,因为这个差必定是正奇数,所以这个n一定有解.
所以唯一的问题就在于,k必须是大于1的,也就是说,a和b中较小的那个不能是1,也就是说,2N必定有一个大于1的奇数因子,所以只要N不是2的整数次幂就可以按上面的办法找到k了.