OFFSET
1,2
COMMENTS
LINKS
Antti Karttunen, Table of n, a(n) for n = 1..20000
Michael De Vlieger, Graph montage of k -> k - k/p, with prime p|k for 2 <= k <= 121, red line showing path of least sum.
FORMULA
EXAMPLE
For n=119, the graph obtained is this:
119
_/\_
/ \
102 112
_/|\_ | \_
_/ | \_ | \_
/ | \ | \
51 68 96 56
/| _/ | _/| _/ |
/ | _/ | _/ | _/ |
/ |/ |/ |/ |
(48) 34 64 48 28
|\_ | _/| _/|
| \_ | _/ | _/ |
| \_|_/ |/ |
17 32 24 14
\_ | _/| _/|
\_ | _/ | _/ |
\_|_/ |/ |
16 12 7
| _/| _/
| _/ | _/
|_/ |_/
8 _6
| __/ |
|_/ |
4 3
\ /
\_ _/
2
|
1.
By choosing the path that follows the right edge of the above diagram, we obtain the smallest sum for any such path that goes from 119 to 1, thus a(119) = 119+112+56+28+14+7+6+3+2+1 = 348.
Note that if we always subtracted the largest proper divisor (A032742), i.e., iterated with A060681 (starting from 119), we would obtain 119-(119/7) = 102 -> 102-(102/2) -> 51-(51/3) -> 34-(34/2) -> 17-(17/17) -> 16-(16/2) -> 8-(8/2) -> 4-(4/2) -> 2-(2/2) -> 1, with sum 119+102+51+34+17+16+8+4+2+1 = 354 = A073934(119), which is NOT minimal sum in this case.
MATHEMATICA
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}}}, 76] (* Michael De Vlieger, Apr 14 2020 *)
PROG
(PARI)
up_to = 65537; \\ 2^20;
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(up_to);
A333790(n) = v333790[n];
CROSSREFS
KEYWORD
nonn
AUTHOR
Antti Karttunen, Apr 06 2020
STATUS
approved