|
%I #16 May 12 2020 11:50:14
%S 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 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 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 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 Antti Karttunen, <a href="/A332999/b332999.txt">Table of n, a(n) for n = 1..31031</a>
%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 indegree is 3, which occurs at node 4, therefore a(15) = 3.
%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) 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 Cf. A332992 (max. outdegree), A333123, A334144, A334184.
%Y Cf. A067513 for the maximal indegree in the whole semilattice (see A334111).
%K nonn
%O 1,6
%A _Antti Karttunen_, Apr 05 2020
|
