cp's OEIS Frontend

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.

%I A333790 #28 Apr 14 2020 20:19:18
%S A333790 1,3,6,7,12,12,19,15,21,22,33,24,37,33,37,31,48,39,58,42,54,55,78,48,
%T A333790 67,63,66,61,90,67,98,63,88,82,96,75,112,96,102,82,123,96,139,99,112,
%U A333790 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
%N 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.
%C A333790 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.
%H A333790 Antti Karttunen, <a href="/A333790/b333790.txt">Table of n, a(n) for n = 1..20000</a>
%H A333790 Michael De Vlieger, <a href="/A333790/a333790.png">Graph montage</a> of k -> k - k/p, with prime p|k for 2 <= k <= 121, red line showing path of least sum.
%F A333790 a(n) = n + Min a(n - n/p), for p prime and dividing n.
%F A333790 For n >= 1, a(n) <= A333794(n) <= A332904(n), a(n) <= A333001(n).
%e A333790 For n=119, the graph obtained is this:
%e A333790               119
%e A333790              _/\_
%e A333790             /    \
%e A333790           102    112
%e A333790          _/|\_    | \_
%e A333790        _/  |  \_  |   \_
%e A333790       /    |    \ |     \
%e A333790     51     68    96     56
%e A333790     /|   _/ |   _/|   _/ |
%e A333790    / | _/   | _/  | _/   |
%e A333790   /  |/     |/    |/     |
%e A333790 (48) 34    64     48    28
%e A333790      |\_    |    _/|   _/|
%e A333790      |  \_  |  _/  | _/  |
%e A333790      |    \_|_/    |/    |
%e A333790     17     32     24    14
%e A333790       \_    |    _/|   _/|
%e A333790         \_  |  _/  | _/  |
%e A333790           \_|_/    |/    |
%e A333790            16      12    7
%e A333790             |    _/|    _/
%e A333790             |  _/  |  _/
%e A333790             |_/    |_/
%e A333790             8     _6
%e A333790             |  __/ |
%e A333790             |_/    |
%e A333790             4      3
%e A333790              \     /
%e A333790               \_ _/
%e A333790                 2
%e A333790                 |
%e A333790                 1.
%e A333790 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.
%e A333790 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.
%t A333790 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 *)
%o A333790 (PARI)
%o A333790 up_to = 65537; \\ 2^20;
%o A333790 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); };
%o A333790 v333790 = A333790list(up_to);
%o A333790 A333790(n) = v333790[n];
%Y A333790 Cf. A032742, A060681, A332904, A333000, A333001, A333123, A333794.
%Y A333790 Differs from A073934 for the first time at n=119, where a(119) = 348, while A073934(119) = 354. (See A333789).
%K A333790 nonn
%O A333790 1,2
%A A333790 _Antti Karttunen_, Apr 06 2020