login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


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] = 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.

License Agreements, Terms of Use, Privacy Policy. .

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