cp's OEIS Frontend

A332904 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.

%I A332904 #20 Apr 15 2020 12:30:16
%S A332904 1,3,6,7,12,16,23,15,25,30,41,36,49,57,66,31,48,63,82,66,105,99,122,
%T A332904 76,91,115,90,125,154,156,187,63,222,114,240,139,176,196,217,138,179,
%U A332904 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 A332904 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 A332904 Antti Karttunen, <a href="/A332904/b332904.txt">Table of n, a(n) for n = 1..20000</a>
%F A332904 For all primes p, a(p) = a(p-1) + p.
%F A332904 For all n >= 1, A333000(n) >= a(n) >= A333794(n) >= A333790(n).
%e A332904 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 A332904 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 A332904         15
%e A332904        / \
%e A332904       /   \
%e A332904     10     12
%e A332904     / \   / \
%e A332904    /   \ /   \
%e A332904   5     8     6
%e A332904    \__  |  __/|
%e A332904       \_|_/   |
%e A332904         4     3
%e A332904          \   /
%e A332904           \ /
%e A332904            2
%e A332904            |
%e A332904            1,
%e A332904 therefore a(15) = 1+2+3+4+5+6+8+10+12+15 = 66.
%t A332904 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 A332904 (PARI)
%o A332904 up_to = 20000;
%o A332904 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 A332904 v332904 = A332904list(up_to);
%o A332904 A332904(n) = v332904[n];
%Y A332904 Cf. A064097, A073934, A332809, A332993, A332994, A333000, A333123.
%Y A332904 Cf. A333790 (sum of the route with minimal sum), A333794.
%K A332904 nonn
%O A332904 1,2
%A A332904 _Antti Karttunen_, Apr 04 2020