|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
LINKS
|
|
|
FORMULA
|
For all primes p, a(p) = a(p-1) + p.
|
|
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);
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|