cp's OEIS Frontend

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.

%I A333001 #23 Jan 11 2025 13:47:22
%S A333001 1,3,6,7,12,12,19,15,21,23,34,25,38,37,39,31,48,41,60,46,60,63,86,50,
%T A333001 71,71,68,71,100,74,105,63,104,89,108,81,118,112,116,90,131,112,155,
%U A333001 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
%N 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.
%H A333001 Antti Karttunen, <a href="/A333001/b333001.txt">Table of n, a(n) for n = 1..20000</a>
%F A333001 a(n) = floor(A333000(n)/A333123(n)) = floor(A333002(n)/A333003(n)).
%e A333001 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.
%e A333001 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.
%e A333001         15
%e A333001        / \
%e A333001       /   \
%e A333001     10     12
%e A333001     / \   / \
%e A333001    /   \ /   \
%e A333001   5     8     6
%e A333001    \_   |  __/|
%e A333001      \__|_/   |
%e A333001         4     3
%e A333001          \   /
%e A333001           \ /
%e A333001            2
%e A333001            |
%e A333001            1.
%t A333001 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 *)
%o A333001 (PARI)
%o A333001 up_to = 20000;
%o A333001 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])); };
%o A333001 v333001 = A333001list(up_to);
%o A333001 A333001(n) = v333001[n];
%Y A333001 Cf. A333000, A333123.
%Y A333001 Cf. A333002/A333003 (average as exact rational, numerator/denominator in lowest terms), A333785 (where the average is an integer).
%Y A333001 Cf. A333790 (smallest path sum), A333794 (conjectured largest path sum).
%K A333001 nonn
%O A333001 1,2
%A A333001 _Antti Karttunen_, Apr 06 2020