A332992 - OEIS

%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