The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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 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 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; 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 Cf. A032742, A060681, A332904, A333000, A333001, A333123, A333794. 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 Adjacent sequences:  A333787 A333788 A333789 * A333791 A333792 A333793 KEYWORD nonn AUTHOR Antti Karttunen, Apr 06 2020 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified September 23 02:41 EDT 2021. Contains 347609 sequences. (Running on oeis4.)