第4题

(a) 对哪些整数

n>2

，存在

n

个连续正整数组成的集合，使得集合中最大的数是其余

n-1

个数的最小公倍数的因数？(b) 对哪些整数

n>2

，恰好存在一个这样的集合？

第 1/6 步：用

k

中最大的素数幂来限制集合大小

上一步下一步

通俗地说

$k$ 中“最苛刻”的素数幂因子决定了需要多少个连续数字才能再次出现该素数幂的倍数。

k=\prod_i p_i^{e_i} \implies \text{need } n > \max_i p_i^{e_i}

详细分析

若最大的数 $k$ 能被素数幂 $p_i^{e_i}$ 整除，则 $k$ 整除其余数的最小公倍数，仅当该最小公倍数也被 $p_i^{e_i}$ 整除；小于 $k$ 且最接近的 $p_i^{e_i}$ 的倍数是 $k-p_i^{e_i}$ ，因此集合必须至少延伸到那里，即至少含有 $p_i^{e_i}$ 个元素。对整除 $k$ 的所有素数幂取最大值即得上述界限。