Question

设x是一个自然数．若一串自然数x₀＝1，x₁，x₂，…，x_t－1，x_t＝x，满足x_i－1＜x_i，x_i－1|x_i，i＝1，2，…，t．则称{x₀，x₁，x₂，…x_t}为x的一条因子链，t为该因子链的长度．T(x)与R(x)分别表示x的最长因子链的长度和最长因子链的条数．对于x＝5^k×31^m×1990ⁿ(k，m，n是自然数)试求T(x)与R(x)．

Answer 1

解析：设x的质因数分解式为

其中p₁、p₂、…、p_n为互不相同的质数，α₁、α₂、…、α_n为正整数．

由于因子链上，每一项至少比前一项多一个质因数，所以T(x)≤α₁＋α₂＋…＋α_n．

将α₁＋α₂＋…＋α_n个质因数(其中α₁个p₁，α₂个p₂，…，α_n个p_n)依任意顺序排列，每个排列产生一个长为α₁＋α₂＋…＋α_n的因子链(x₁为排列的第一项，x₂为x₁乘排列的第二项，x₃为x₂乘第三项，…)，因此T(x)＝α₁＋α₂＋…＋α_n，R(x)即排列

对于x＝5^k×31^m×1990ⁿ＝2ⁿ×5^k＋n×31^m×199ⁿ，

T(x)＝3n＋k＋m