cp's OEIS Frontend

A332999 Maximum indegree in the graph formed by a subset of numbers in range 1 .. n with edge relation k -> k - k/p, where p is any of the prime factors of k.

%I A332999 #16 May 12 2020 11:50:14
%S A332999 0,1,1,1,1,2,2,1,2,2,2,2,2,2,3,1,1,2,2,2,3,2,2,2,2,2,2,2,2,3,3,1,3,2,
%T A332999 3,2,2,2,3,2,2,3,3,2,3,2,2,2,3,2,3,2,2,2,3,2,3,2,2,3,3,3,3,1,3,3,3,2,
%U A332999 3,3,3,2,2,2,3,2,3,3,3,2,2,2,2,3,3,3,3,2,2,3,4,2,3,2,3,2,2,3,3,2,2,3,3,2,4
%N A332999 Maximum indegree in the graph formed by a subset of numbers in range 1 .. n with edge relation k -> k - k/p, where p is any of the prime factors of k.
%H A332999 Antti Karttunen, <a href="/A332999/b332999.txt">Table of n, a(n) for n = 1..31031</a>
%e A332999 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 A332999         15
%e A332999        / \
%e A332999       /   \
%e A332999     10     12
%e A332999     / \   / \
%e A332999    /   \ /   \
%e A332999   5     8     6
%e A332999    \__  |  __/|
%e A332999       \_|_/   |
%e A332999         4     3
%e A332999          \   /
%e A332999           \ /
%e A332999            2
%e A332999            |
%e A332999            1
%e A332999 With edges going from 15 towards 1, the maximum indegree is 3, which occurs at node 4, therefore a(15) = 3.
%t A332999 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 A332999 (PARI) A332999(n) = { my(m = Map(), nodes = List([n]), x, xps, s=0, u, v); while(#nodes, x = nodes[#nodes]; listpop(nodes); xps = factor(x)[, 1]~; for(i=1,#xps, u=x-(x/xps[i]); if(!mapisdefined(m,u,&v), v=0; listput(nodes,u)); mapput(m,u,v+1); s = max(s,v+1))); (s); };
%Y A332999 Cf. A332992 (max. outdegree), A333123, A334144, A334184.
%Y A332999 Cf. A067513 for the maximal indegree in the whole semilattice (see A334111).
%K A332999 nonn
%O A332999 1,6
%A A332999 _Antti Karttunen_, Apr 05 2020