%I #27 May 02 2020 23:05:45
%S 0,1,1,1,1,2,2,1,2,2,2,2,2,2,2,1,1,2,2,2,2,2,2,2,2,2,2,2,2,3,3,1,3,2,
%T 3,2,2,2,2,2,2,3,3,2,3,2,2,2,3,2,2,2,2,2,2,2,2,2,2,3,3,3,3,1,3,3,3,2,
%U 3,3,3,2,2,2,3,2,3,3,3,2,2,2,2,3,2,3,3,2,2,3,3,2,3,2,3,2,2,3,3,2,2,3,3,2,3
%N Maximum outdegree in the graph formed by a subset of numbers in range 1 .. n with edge relation k -> k - k/p, where p can be any of the prime factors of k.
%C Maximum number of distinct prime factors of any one integer encountered on all possible paths from n to 1 when iterating with nondeterministic map k -> k - k/p, where p can be any of the prime factors of k.
%H Antti Karttunen, <a href="/A332992/b332992.txt">Table of n, a(n) for n = 1..65539</a>
%F a(n) = max(A001221(n), {Max a(n - n/p), for p prime and dividing n}).
%F For all odd primes p, a(p) = a(p-1).
%F For all n >= 0, a(A002110(n)) = n.
%e 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:
%e 15
%e / \
%e / \
%e 10 12
%e / \ / \
%e / \ / \
%e 5 8 6
%e \__ | __/|
%e \_|_/ |
%e 4 3
%e \ /
%e \ /
%e 2
%e |
%e 1
%e With edges going from 15 towards 1, the maximum outdegree is 2, which occurs at nodes 15, 12, 10 and 6, therefore a(15) = 2.
%t With[{s = Nest[Function[{a, n}, Append[a, Join @@ Table[Flatten@ Prepend[#, n] & /@ a[[n - n/p]], {p, FactorInteger[n][[All, 1]]}]]] @@ {#, Length@ # + 1} &, {{{1}}}, 105]}, Array[If[# == 1, 0, Max@ Tally[#][[All, -1]] &@ Union[Join @@ Map[Partition[#, 2, 1] &, s[[#]] ]][[All, 1]] ] &, Length@ s]] (* _Michael De Vlieger_, May 02 2020 *)
%o (PARI)
%o up_to = 105;
%o A332992list(up_to) = { my(v=vector(up_to)); v[1] = 0; for(n=2,up_to, v[n] = max(omega(n),vecmax(apply(p -> v[n-n/p], factor(n)[, 1]~)))); (v); };
%o v332992 = A332992list(up_to);
%o A332992(n) = v332992[n];
%Y Cf. A001221, A064097, A332809, A332999 (max. indegree), A333123, A334111, A334144, A334184.
%Y Cf. A002110 (positions of records and the first occurrence of each n).
%K nonn
%O 1,6
%A _Antti Karttunen_, Apr 04 2020