A334144 Consider the mapping k -> (k - (k/p)), where prime p | k. a(n) = maximum distinct terms at any position j among the various paths to 1.

1, 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, 3, 3, 3, 3, 1, 4, 2, 4, 3, 3, 3, 3, 2, 2, 4, 4, 3, 4, 3, 3, 2, 4, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 1, 5, 5, 5, 2, 5, 5, 5, 3, 3, 3, 4, 3, 6, 4, 4, 2, 3, 2, 2, 4, 3, 4, 4, 3, 3, 5, 5, 3, 5, 3, 5, 2, 2, 4, 6, 3, 3, 3, 3, 3, 6, 3

Offset: 1

Author

Michael De Vlieger, Peter Kagey, Antti Karttunen, Apr 15 2020

Keywords

• nonn

Comments

Let i = A064097(n) be the common path length and let 1 <= j <= i. Given a path P, we find for any j relatively few distinct values. Regarding a common path length i, see A333123 comment 2, and proof at A064097.

Maximum term in row n of A334184.

Examples

			For n=15, the paths are shown vertically at left, and the graph obtained appears at right:
  15   15   15   15   15  =>         15
   |    |    |    |    |            _/ \_
   |    |    |    |    |           /     \
  10   10   12   12   12  =>     10       12
   |    |    |    |    |         | \_   _/ |
   |    |    |    |    |         |   \ /   |
   5    8    6    6    8  =>     5    8    6
   |    |    |    |    |          \_  |  _/|
   |    |    |    |    |            \_|_/  |
   4    4    3    4    4  =>          4    3
   |    |    |    |    |              |  _/
   |    |    |    |    |              |_/
   2    2    2    2    2  =>          2
   |    |    |    |    |              |
   |    |    |    |    |              |
   1    1    1    1    1  =>          1
Because the maximum number of distinct terms in any row is 3, a(15) = 3.
		

Links

• Peter Kagey, Table of n, a(n) for n = 1..10000
• Peter Kagey, Math.StackExchange, Does a graded poset on the positive integers generated from subtracting factors define a lattice?
• Richard Stanley, MIT OpenCourseWare, Lecture Notes in Algebraic Combinatorics: The Sperner Property
• Wikipedia, Sperner property of a partially ordered set

Crossrefs

Cf. A064097, A332992, A332999, A333123, A334111, A334184.

Cf. also A096825.

Programs

Mathematica

Max[Length@ Union@ # & /@ Transpose@ #] & /@ Nest[Function[{a, n}, Append[a, Join @@ Table[Flatten@ Prepend[#, n] & /@ a[[n - n/p]], {p, FactorInteger[n][[All, 1]]}]]] @@ {#, Length@ # + 1} &, {{{1}}}, 105]
(* Second program: *)
g[n_] := Block[{lst = {{n}}}, While[lst[[-1]] != {1}, lst = Join[lst, {Union@ Flatten[# - #/(First@ # & /@ FactorInteger@ #) & /@ lst[[-1]] ]}]]; Max[Length /@ lst]]; Array[g, 105] (* Robert G. Wilson v, May 08 2020 *)