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.

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, 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, 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

Offset: 1

Author

Antti Karttunen, Apr 05 2020

Keywords

• nonn

Examples

			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:
        15
       / \
      /   \
    10     12
    / \   / \
   /   \ /   \
  5     8     6
   \__  |  __/|
      \_|_/   |
        4     3
         \   /
          \ /
           2
           |
           1
With edges going from 15 towards 1, the maximum indegree is 3, which occurs at node 4, therefore a(15) = 3.
		

Links

• Antti Karttunen, Table of n, a(n) for n = 1..31031

Crossrefs

Cf. A332992 (max. outdegree), A333123, A334144, A334184.

Cf. A067513 for the maximal indegree in the whole semilattice (see A334111).

Programs

Mathematica

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 *)

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); };