login
A333001
The average path sum (floored down) when iterating from n to 1 with nondeterministic map k -> k - k/p, where p is any prime factor of k.
7
1, 3, 6, 7, 12, 12, 19, 15, 21, 23, 34, 25, 38, 37, 39, 31, 48, 41, 60, 46, 60, 63, 86, 50, 71, 71, 68, 71, 100, 74, 105, 63, 104, 89, 108, 81, 118, 112, 116, 90, 131, 112, 155, 119, 122, 153, 200, 101, 161, 132, 148, 135, 188, 131, 179, 137, 178, 181, 240, 144, 205, 192, 181, 127, 206, 191, 258, 170, 251, 199, 270, 160, 233, 218, 216
OFFSET
1,2
LINKS
FORMULA
a(n) = floor(A333000(n)/A333123(n)) = floor(A333002(n)/A333003(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 path sums 27, 25, 24, whose average is 76/3 = 25.333..., therefore a(12) = 25.
For n=15 we have five alternative paths from 15 to 1 (illustrated below) with path sums 37, 40, 42, 40, 39, whose average is 198/5 = 39.6, therefore a(15) = 39.
15
/ \
/ \
10 12
/ \ / \
/ \ / \
5 8 6
\_ | __/|
\__|_/ |
4 3
\ /
\ /
2
|
1.
MATHEMATICA
Map[Floor@ Mean[Total /@ #] &, #] &@ Nest[Function[{a, n}, Append[a, Join @@ Table[Flatten@ Prepend[#, n] & /@ a[[n - n/p]], {p, FactorInteger[n][[All, 1]]}]]] @@ {#, Length@ # + 1} &, {{{1}}}, 74] (* Michael De Vlieger, Apr 15 2020 *)
PROG
(PARI)
up_to = 20000;
A333001list(up_to) = { my(u=vector(up_to), v=vector(up_to)); u[1] = v[1] = 1; for(n=2, up_to, my(ps=factor(n)[, 1]~); u[n] = vecsum(apply(p -> u[n-n/p], ps)); v[n] = (u[n]*n)+vecsum(apply(p -> v[n-n/p], ps))); vector(up_to, n, floor(v[n]/u[n])); };
v333001 = A333001list(up_to);
A333001(n) = v333001[n];
CROSSREFS
Cf. A333002/A333003 (average as exact rational, numerator/denominator in lowest terms), A333785 (where the average is integer).
Cf. A333790 (smallest path sum), A333794 (conjectured largest path sum).
Sequence in context: A209246 A073934 A333790 * A092150 A028802 A141742
KEYWORD
nonn
AUTHOR
Antti Karttunen, Apr 06 2020
STATUS
approved