cp's OEIS Frontend

A332992 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.

%I A332992 #27 May 02 2020 23:05:45
%S A332992 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 A332992 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 A332992 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 A332992 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 A332992 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 A332992 Antti Karttunen, <a href="/A332992/b332992.txt">Table of n, a(n) for n = 1..65539</a>
%F A332992 a(n) = max(A001221(n), {Max a(n - n/p), for p prime and dividing n}).
%F A332992 For all odd primes p, a(p) = a(p-1).
%F A332992 For all n >= 0, a(A002110(n)) = n.
%e A332992 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 A332992         15
%e A332992        / \
%e A332992       /   \
%e A332992     10     12
%e A332992     / \   / \
%e A332992    /   \ /   \
%e A332992   5     8     6
%e A332992    \__  |  __/|
%e A332992       \_|_/   |
%e A332992         4     3
%e A332992          \   /
%e A332992           \ /
%e A332992            2
%e A332992            |
%e A332992            1
%e A332992 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 A332992 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 A332992 (PARI)
%o A332992 up_to = 105;
%o A332992 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 A332992 v332992 = A332992list(up_to);
%o A332992 A332992(n) = v332992[n];
%Y A332992 Cf. A001221, A064097, A332809, A332999 (max. indegree), A333123, A334111, A334144, A334184.
%Y A332992 Cf. A002110 (positions of records and the first occurrence of each n).
%K A332992 nonn
%O A332992 1,6
%A A332992 _Antti Karttunen_, Apr 04 2020