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