重复添加一个数的质因数并用总和替换该数直到重复的最终结果

Question

考虑以下操作——我们取一个正整数 n 并用它的质因数之和代替它（如果一个质数在 n 的因式分解中出现多次，那么它被计算为相同的次数总和）。此操作首先依次应用于给定数字，然后应用于第一个结果，然后应用于第二个结果，依此类推，直到结果保持相同。给定任意数，求出运算的最终结果。

示例： 24 -> (2 + 2 + 2 + 3) = 9 -> (3 + 3) = 6 -> (2 + 3) = 5 -> 5.

所以 24 的答案是 5。

除了蛮力解决方案，我找不到更好的解决方案

Answer 1

您可能需要查看此序列的 the OEIS page。

它包括几个代码片段，例如 Maple 中的这个：

f:= proc(n) option remember;
if isprime(n) then n
else `procname`(add(x[1]*x[2], x = ifactors(n)[2]))
fi
end proc:
f(1):= 0: f(4):= 4:
map(f, [..100]); # Robert Israel, Apr 27 2015

我不了解 Maple，但这看起来很像您所建议的递归定义。因此，我倾向于说迭代直到达到素数（除了 1 和 4 的特殊情况）是最有效的计算方法。

还有一个 Mathematica 脚本，但我完全看不懂：

ffi[x_] := Flatten[FactorInteger[x]] lf[x_] := Length[FactorInteger[x]] ba[x_] := Table[Part[ffi[x], 2*w-1], {w, 1, lf[x]}] ep[x_] := Table[Part[ffi[x], 2*w], {w, 1, lf[x]}] slog[x_] := slog[x_] := Apply[Plus, ba[x]*ep[x]] Table[FixedPoint[slog, w], {w, 1, 128}]
f[n_] := Plus @@ Flatten[ Table[ #[[1]], {#[[2]]}] & /@ FactorInteger@n]; Array[ FixedPoint[f, # ] &, 87] (* Robert G. Wilson v, Jan 18 2006 *)
fz[n_]:=Plus@@(#[[1]]*#[[2]]&/@FactorInteger@n); Array[FixedPoint[fz, #]&, 1000] (* Zak Seidov, Mar 14 2011 *)

This related sequence 给出了达到结果所需的迭代次数。它说只有一个 n < 10000 的值需要超过 10 次迭代，所以它似乎也是一种快速收敛的算法。

重复添加一个数的质因数并用总和替换该数直到重复的最终结果

Final result of repeatedly adding prime factors of a number and replacing that number by the sum until it repeats

algorithm

primes

factors