|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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.
|
|
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);
|
|
CROSSREFS
|
Differs from A073934 for the first time at n=119, where a(119) = 348, while A073934(119) = 354. (See A333789).
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|