login
A333790
Smallest path sum when iterating from n to 1 with nondeterministic map k -> k - k/p, where p is any prime factor of k.
6
1, 3, 6, 7, 12, 12, 19, 15, 21, 22, 33, 24, 37, 33, 37, 31, 48, 39, 58, 42, 54, 55, 78, 48, 67, 63, 66, 61, 90, 67, 98, 63, 88, 82, 96, 75, 112, 96, 102, 82, 123, 96, 139, 99, 112, 124, 171, 96, 145, 117, 133, 115, 168, 120, 154, 117, 153, 148, 207, 127, 188, 160, 159, 127, 180, 154, 221, 150, 193, 166, 237, 147, 220, 186, 192, 172, 231
OFFSET
1,2
COMMENTS
Note that although in many cases a simple heuristics of always subtracting the largest proper divisor (i.e., iterating with A060681) gives the path with the minimal sum, this does not hold for the following numbers 119, 143, 187, 209, 221, ..., A333789, on which this sequence differs from A073934.
LINKS
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
a(n) = n + Min a(n - n/p), for p prime and dividing n.
For n >= 1, a(n) <= A333794(n) <= A332904(n), a(n) <= A333001(n).
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
Differs from A073934 for the first time at n=119, where a(119) = 348, while A073934(119) = 354. (See A333789).
Sequence in context: A138037 A209246 A073934 * A333001 A092150 A028802
KEYWORD
nonn
AUTHOR
Antti Karttunen, Apr 06 2020
STATUS
approved