A332904 - OEIS

%I #20 Apr 15 2020 12:30:16

%S 1,3,6,7,12,16,23,15,25,30,41,36,49,57,66,31,48,63,82,66,105,99,122,

%T 76,91,115,90,125,154,156,187,63,222,114,240,139,176,196,217,138,179,

%U 251,294,215,264,284,331,156,300,213,258,247,300,220,345,261,334,348,407,336,397,429,395,127,492,512,579,246,650,546,617,291,364

%N Sum of distinct integers encountered on all possible paths from n to 1 when iterating with nondeterministic map k -> k - k/p, where p is any of the prime factors of k.

%H Antti Karttunen, <a href="/A332904/b332904.txt">Table of n, a(n) for n = 1..20000</a>

%F For all primes p, a(p) = a(p-1) + p.

%F For all n >= 1, A333000(n) >= a(n) >= A333794(n) >= A333790(n).

%e a(12): we have three alternative paths: {12, 8, 4, 2, 1}, {12, 6, 4, 2, 1} or {12, 6, 3, 2, 1}, with numbers [1, 2, 3, 4, 6, 8, 12] present, therefore a(12) = 1+2+3+4+6+8+12 = 36.

%e For n=15 we have five alternative paths from 15 to 1: {15, 10, 5, 4, 2, 1}, {15, 10, 8, 4, 2, 1}, {15, 12, 8, 4, 2, 1},  {15, 12, 6, 4, 2, 1},  {15, 12, 6, 3, 2, 1}. These form a lattice illustrated below:

%e         15

%e        / \

%e       /   \

%e     10     12

%e     / \   / \

%e    /   \ /   \

%e   5     8     6

%e    \__  |  __/|

%e       \_|_/   |

%e         4     3

%e          \   /

%e           \ /

%e            2

%e            |

%e            1,

%e therefore a(15) = 1+2+3+4+5+6+8+10+12+15 = 66.

%t Total /@ Nest[Function[{a, n}, Append[a, Union@ Flatten@ Table[Append[a[[n - n/p]], n], {p, FactorInteger[n][[All, 1]]}]]] @@ {#, Length@ # + 1} &, {{1}}, 72] (* _Michael De Vlieger_, Apr 15 2020 *)

%o (PARI)

%o up_to = 20000;

%o A332904list(up_to) = { my(v=vector(up_to)); v[1] = Set([1]); for(n=2,up_to, my(f=factor(n)[, 1]~, s=Set([n])); for(i=1,#f,s = setunion(s,v[n-(n/f[i])])); v[n] = s); apply(vecsum,v); }

%o v332904 = A332904list(up_to);

%o A332904(n) = v332904[n];

%Y Cf. A064097, A073934, A332809, A332993, A332994, A333000, A333123.

%Y Cf. A333790 (sum of the route with minimal sum), A333794.

%K nonn

%O 1,2

%A _Antti Karttunen_, Apr 04 2020