OFFSET
1,1
COMMENTS
Numbers n for which the {smallest path sum when iterating from n to 1 with nondeterministic map k -> k - k/p, where p is any prime factor of k} cannot be obtained by always selecting the smallest prime factor of k (A020639). See the example in A333790 how that simple heuristic fails when starting from k=119.
LINKS
Antti Karttunen, Table of n, a(n) for n = 1..36576; all terms <= 2^17
MATHEMATICA
Block[{a, b, nn = 1122}, a = Min@ Map[Total, #] & /@ Nest[Function[{a, n}, Append[a, Join @@ Table[Flatten@ Prepend[#, n] & /@ a[[n - n/p]], {p, FactorInteger[n][[All, 1]]}]]] @@ {#, Length@ # + 1} &, {{{1}}}, nn]; b = Array[If[# == 1, 1, Total@ NestWhileList[If[PrimeQ@ #, # - 1, # - #/FactorInteger[#][[1, 1]] ] &, #, # > 1 &]] &, nn]; Select[Range@ nn, a[[#]] < b[[#]] &]] (* Michael De Vlieger, Apr 15 2020 *)
PROG
(PARI)
search_up_to = 2^17;
A333790list(up_to) = { my(v=vector(up_to)); v[1] = 1; for(n=2, up_to, v[n] = n+vecmin(apply(p -> v[n-n/p], factor(n)[, 1]~))); (v); };
v333790 = A333790list(search_up_to);
A333790(n) = v333790[n];
CROSSREFS
KEYWORD
nonn
AUTHOR
Antti Karttunen, Apr 12 2020
STATUS
approved