OFFSET
1,2
LINKS
Antti Karttunen, Table of n, a(n) for n = 1..20000
FORMULA
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
KEYWORD
nonn
AUTHOR
Antti Karttunen, Apr 04 2020
STATUS
approved