Конечный результат многократного добавления простых коэффициентов числа и замены этого числа на сумму до повторения

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, [$1..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 итераций, поэтому он также кажется быстрым сходящимся алгоритмом.