login
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.
8
1, 3, 6, 7, 12, 16, 23, 15, 25, 30, 41, 36, 49, 57, 66, 31, 48, 63, 82, 66, 105, 99, 122, 76, 91, 115, 90, 125, 154, 156, 187, 63, 222, 114, 240, 139, 176, 196, 217, 138, 179, 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
OFFSET
1,2
LINKS
FORMULA
For all primes p, a(p) = a(p-1) + p.
For all n >= 1, A333000(n) >= a(n) >= A333794(n) >= A333790(n).
EXAMPLE
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.
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:
15
/ \
/ \
10 12
/ \ / \
/ \ / \
5 8 6
\__ | __/|
\_|_/ |
4 3
\ /
\ /
2
|
1,
therefore a(15) = 1+2+3+4+5+6+8+10+12+15 = 66.
MATHEMATICA
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 *)
PROG
(PARI)
up_to = 20000;
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); }
v332904 = A332904list(up_to);
A332904(n) = v332904[n];
CROSSREFS
Cf. A333790 (sum of the route with minimal sum), A333794.
Sequence in context: A047705 A309839 A169799 * A370900 A069891 A190118
KEYWORD
nonn
AUTHOR
Antti Karttunen, Apr 04 2020
STATUS
approved