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.

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

Offset: 1

Author

Antti Karttunen, Apr 04 2020

Keywords

• nonn

Comments

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.

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 outdegree is 2, which occurs at nodes 15, 12, 10 and 6, therefore a(15) = 2.
		

Links

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

Crossrefs

Cf. A001221, A064097, A332809, A332999 (max. indegree), A333123, A334111, A334144, A334184.

Cf. A002110 (positions of records and the first occurrence of each n).

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

up_to = 105;
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); };
v332992 = A332992list(up_to);
A332992(n) = v332992[n];

Formula

a(n) = max(A001221(n), {Max a(n - n/p), for p prime and dividing n}).

For all odd primes p, a(p) = a(p-1).

For all n >= 0, a(A002110(n)) = n.