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

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.

Links

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

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.

Example

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.

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

Prog

(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];

Crossrefs

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

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

Sequence in context: A275992 A271824 A253589 * A337788 A346510 A023568

Adjacent sequences: A332989 A332990 A332991 * A332993 A332994 A332995

Keyword

nonn

Author

Antti Karttunen, Apr 04 2020

Status

approved