|
%I #28 Apr 14 2020 20:19:18
%S 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 67,63,66,61,90,67,98,63,88,82,96,75,112,96,102,82,123,96,139,99,112,
%U 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 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 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 Antti Karttunen, <a href="/A333790/b333790.txt">Table of n, a(n) for n = 1..20000</a>
%H 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 a(n) = n + Min a(n - n/p), for p prime and dividing n.
%F For n >= 1, a(n) <= A333794(n) <= A332904(n), a(n) <= A333001(n).
%e For n=119, the graph obtained is this:
%e 119
%e _/\_
%e / \
%e 102 112
%e _/|\_ | \_
%e _/ | \_ | \_
%e / | \ | \
%e 51 68 96 56
%e /| _/ | _/| _/ |
%e / | _/ | _/ | _/ |
%e / |/ |/ |/ |
%e (48) 34 64 48 28
%e |\_ | _/| _/|
%e | \_ | _/ | _/ |
%e | \_|_/ |/ |
%e 17 32 24 14
%e \_ | _/| _/|
%e \_ | _/ | _/ |
%e \_|_/ |/ |
%e 16 12 7
%e | _/| _/
%e | _/ | _/
%e |_/ |_/
%e 8 _6
%e | __/ |
%e |_/ |
%e 4 3
%e \ /
%e \_ _/
%e 2
%e |
%e 1.
%e 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 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 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 (PARI)
%o up_to = 65537; \\ 2^20;
%o 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 v333790 = A333790list(up_to);
%o A333790(n) = v333790[n];
%Y Cf. A032742, A060681, A332904, A333000, A333001, A333123, A333794.
%Y Differs from A073934 for the first time at n=119, where a(119) = 348, while A073934(119) = 354. (See A333789).
%K nonn
%O 1,2
%A _Antti Karttunen_, Apr 06 2020
|
