A334144 -id:A334144 - cp's OEIS frontend

A333959 First occurrence of n in A334144.

1, 6, 15, 33, 65, 77, 154, 161, 217, 231, 455, 469, 483, 693, 957, 987, 1001, 1449, 1463, 2021, 2717, 2093, 2415, 2967, 3003, 4147, 3059, 4853, 4945, 4899, 6083, 8533, 4991, 7161, 9982, 8987, 9177, 10787, 10857, 10465, 10199, 12857, 14539, 20355, 18753, 20398

Offset: 1

Michael De Vlieger, Peter Kagey, Antti Karttunen, Robert G. Wilson v, Apr 24 2020

nonn

Consider the mappings f(m) := m -> m - m/p across primes p | m.
Row m of A334184, read as a triangle T(m, k), lists the number of distinct values that proceed from the mapping after exactly k iterations.
A334144(m) is the largest value in row m of A334184.
The smallest term in this sequence that is not an index of a record in A334144 is a(22) = 2093.
From Robert G. Wilson v, Jun 14 2020: (Start)
All terms are nonprimes, but not necessarily squarefree. They are: 693, 1449, 91791, 13126113, 46334057, ..., .
Even terms: 6, 154, 9982, 20398, 29946, 812630, 1366666, 4263182, 17766658, 22866158, 34688186, 80633294, ..., .
Except for the initial even term, all even terms divided by 2 are also terms.
(End)

			1 is the first term since 1 is the empty product.
6 follows 1 since 2 <= m <= 5 have total order, thus the maximum number in A333184 is 1. For m = 6, the mapping f(m) has two distinct results {4, 3}, which generate chains {4, 2, 1} and {3, 2, 1}, respectively, with the last two terms in both chains coincident. Since the largest number of terms in an antichain is 2, a(2) = 6.
15 follows 6 since row 15 of A334184 = [1, 2, 3, 2, 1, 1] is the smallest m for which n = 3 appears.
Hasse diagrams of the 3 smallest terms, with brackets around the widest row.
[1]        6           15
          / \          /\
         /   \        /  \
        [4   3]     12  __10
         |  /       | \/   |
         | /        |_/\   |
         2         [8  _6  5]
         |          | /_|_/
         |          |// |
         1          4   3
                    |  /
                    |_/
                    2
                    |
                    |
                    1

Robert G. Wilson v, Table of n, a(n) for n = 1..871 (first 256 terms from Peter Kagey)
Math StackExchange, Does a graded poset on the positive integers generated from subtracting factors define a lattice?, 2020.
Michael De Vlieger, Hasse diagrams of a(n) for 2 <= n <= 37.

Cf. A064097, A332809, A333123, A334144, A334184.

With[{s = Table[Max[Length@ Union@ # & /@ Transpose@ #] &@ If[n == 1, {{1}}, NestWhile[If[Length[#] == 0, Map[{n, #} &, # - # /FactorInteger[#][[All, 1]] ], Union[Join @@ Map[Function[{w, n}, Map[Append[w, If[n == 0, 0, n - n/#]] &, FactorInteger[n][[All, 1]] ]] @@ {#, Last@ #} &, #]] ] &, n, If[ListQ[#], AllTrue[#, Last[#] > 1 &], # > 1] &]], {n, 10^3}]}, TakeWhile[Array[FirstPosition[s, #][[1]] &, Max@ s], IntegerQ]]
f[n_] := Block[{lst = {{n}}}, While[lst[[-1]] != {1}, lst = Join[ lst, {Union[ Flatten[# - #/(First@# & /@ FactorInteger@#) & /@ lst[[-1]]] ]}]]; Max[Length@# & /@ lst]]; t[] := 0; k = 1; While[k < 21001, a = f@k; If[ t[a] == 0, t[a] = k]; k++]; t@# & /@ Range@ 46 (* _Robert G. Wilson v, Jun 14 2020 *)

A333123 Consider the mapping k -> (k - (k/p)), where p is any of k's prime factors. a(n) is the number of different possible paths from n to 1.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 2, 1, 2, 2, 2, 3, 3, 5, 5, 1, 1, 5, 5, 3, 10, 5, 5, 4, 3, 7, 5, 9, 9, 12, 12, 1, 17, 2, 21, 9, 9, 14, 16, 4, 4, 28, 28, 9, 21, 14, 14, 5, 28, 7, 7, 12, 12, 14, 16, 14, 28, 23, 23, 21, 21, 33, 42, 1, 33, 47, 47, 3, 61, 56, 56, 14, 14, 23, 28, 28, 103, 42, 42, 5

Offset: 1

Ali Sada and Robert G. Wilson v, Mar 09 2020

The iteration always terminates at 1, regardless of the prime factor chosen at each step.
Although there may exist multiple paths to 1, their path lengths (A064097) are the same! See A064097 for a proof. Note that this behavior does not hold if we allow any divisor of k.
First occurrence of k or 0 if no such value exists: 1, 6, 12, 24, 14, 96, 26, 85, 28, 21, 578, 30, 194, 38, 164, 39, 33, 104, 1538, 112, 35, 328, 58, 166, ..., .
Records: 1, 2, 3, 5, 10, 12, 17, 21, 28, 33, 42, 47, 61, 103, 168, ..., .
Record indices: 1, 6, 12, 14, 21, 30, 33, 35, 42, 62, 63, 66, 69, ..., .
When viewed as a graded poset, the paths of the said graph are the chains of the corresponding poset. This poset is also a lattice (see Ewan Delanoy's answer to Peter Kagey's question at the Mathematics Stack Exchange link). - Antti Karttunen, May 09 2020

			a(1): {1}, therefore a(1) = 1;
a(6): {6, 4, 2, 1} or {6, 3, 2, 1}, therefore a(6) = 2;
a(12): {12, 8, 4, 2, 1}, {12, 6, 4, 2, 1} or {12, 6, 3, 2, 1}, therefore a(12) = 3;
a(14): {14, 12, 8, 4, 2, 1}, {14, 12, 6, 4, 2, 1}, {14, 12, 6, 3, 2, 1}, {14, 7, 6, 4, 2, 1} or {14, 7, 6, 3, 2, 1}, therefore a(14) = 5.
From _Antti Karttunen_, Apr 05 2020: (Start)
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}, therefore a(15) = 5. These form a graph illustrated below:
        15
       / \
      /   \
    10     12
    / \   / \
   /   \ /   \
  5     8     6
   \_   |  __/|
     \__|_/   |
        4     3
         \   /
          \ /
           2
           |
           1
(End)

Antti Karttunen, Table of n, a(n) for n = 1..20000
Peter Kagey, Mathematics Stack Exchange, Does a graded poset on the positive integers generated from subtracting factors define a lattice?

Cf. A064097, A332809 (size of the lattice), A332810.
Cf. A332904 (sum of distinct integers present in such a graph/lattice), A333000 (sum over all paths), A333001, A333785.
Cf. A332992 (max. outdegree), A332999 (max. indegree), A334144 (max. rank level).
Cf. A334230, A334231 (meet and join).
Partial sums of A332903.
Cf. also tables A334111, A334184.

a[n_] := Sum[a[n - n/p], {p, First@# & /@ FactorInteger@n}]; a[1] = 1; (* after PARI coding by Rémy Sigrist *) Array[a, 70]
(* view the various paths *)
f[n_] := Block[{i, j, k, p, q, mtx = {{n}}}, Label[start]; If[mtx[[1, -1]] != 1, j = Length@ mtx;  While[j > 0, k = mtx[[j, -1]]; p = First@# & /@ FactorInteger@k; q = k - k/# & /@ p; pl = Length@p; If[pl > 1, Do[mtx = Insert[mtx, mtx[[j]], j], {pl - 1}]]; i = 1;  While[i < 1 + pl, mtx[[j + i - 1]] = Join[mtx[[j + i - 1]], {q[[i]]}]; i++]; j--]; Goto[start], mtx]]

for (n=1, #a=vector(80), print1 (a[n]=if (n==1, 1, vecsum(apply(p -> a[n-n/p], factor(n)[,1]~)))", ")) \\ Rémy Sigrist, Mar 11 2020

a(n) = 1 iff n is a power of two (A000079) or a Fermat Prime (A019434).
a(p) = a(p-1) if p is prime.
a(n) = Sum_{p prime and dividing n} a(n - n/p) for any n > 1. - Rémy Sigrist, Mar 11 2020

A334111 Irregular triangle where row n gives all terms k for which A064097(k) = n.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 8, 7, 9, 10, 12, 16, 11, 13, 14, 15, 17, 18, 20, 24, 32, 19, 21, 22, 25, 26, 27, 28, 30, 34, 36, 40, 48, 64, 23, 29, 31, 33, 35, 37, 38, 39, 41, 42, 44, 45, 50, 51, 52, 54, 56, 60, 68, 72, 80, 96, 128, 43, 46, 49, 53, 55, 57, 58, 61, 62, 63, 65, 66, 70, 73, 74, 75, 76, 78, 81, 82, 84

Offset: 0

Antti Karttunen, Michael De Vlieger and Robert G. Wilson v, Apr 14 2020

Applying map k -> (p-1)*(k/p) to any term k on any row n > 1, where p is any prime factor of k, gives one of the terms on preceding row n-1.
Any prime that appears on row n is 1 + {some term on row n-1}.
The e-th powers of the terms on row n form a subset of terms on row (e*n). More generally, a product of terms that occur on rows i_1, i_2, ..., i_k can be found at row (i_1 + i_2 + ... + i_k), because A064097 is completely additive.
A001221(k) gives the number of terms on the row above that are immediate descendants of k.
A067513(k) gives the number of terms on the row below that lead to k.

			Rows 0-6 of the irregular table:
0 |   1;
1 |   2;
2 |   3, 4;
3 |   5, 6, 8;
4 |   7, 9, 10, 12, 16;
5 |  11, 13, 14, 15, 17, 18, 20, 24, 32;
6 |  19, 21, 22, 25, 26, 27, 28, 30, 34, 36, 40, 48, 64;

Michael De Vlieger, Table of n, a(n) for n = 0..14422 (rows 0 <= n <= 17, flattened)
Index entries for sequences that are permutations of the natural numbers

Cf. A001221, A064097, A067513, A333123, A334144.
Cf. A105017 (left edge), A000079 (right edge), A175125 (row lengths).
Cf. also A058812, A334100.

f[n_] := Length@ NestWhileList[# - #/FactorInteger[#][[1, 1]] &, n, # != 1 &]; SortBy[ Range@70, f]
(* Second program *)
With[{nn = 8}, Values@ Take[KeySort@ PositionIndex@ Array[-1 + Length@ NestWhileList[# - #/FactorInteger[#][[1, 1]] &, #, # > 1 &] &, 2^nn], nn + 1]] // Flatten (* Michael De Vlieger, Apr 18 2020 *)

A060681(n) = (n-if(1==n,n,n/vecmin(factor(n)[,1])));
A064097(n) = if(1==n,0,1+A064097(A060681(n)));
for(n=0, 10, for(k=1,2^n,if(A064097(k)==n, print1(k,", "))));

A334184 Irregular table read by rows: T(n,k) gives the number of values that can be reached after exactly k iterations of maps of the form (n - n/p) where p is a prime divisor of n. 0 <= k < A073933(n).

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 2, 2, 1, 1, 1, 2, 2, 2, 1, 1, 1, 2, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 1, 1, 1, 1, 2, 2, 2

Offset: 1

Peter Kagey, Apr 17 2020

Row lengths are given by A073933(n). Row sums are given by A332809(n). The maximum value in each row is given by A334144(n).
The n-th row consists of all 1's if and only if n is a power of two (A000079) or a Fermat prime (A019434).
Conjecture: rows are unimodal (increasing and then decreasing).
Not all rows are unimodal. Indices of rows that have terms that increase and decrease more than once are A334238. - Michael De Vlieger, Apr 18 2020

			For n = 15, the fifteenth row of this table is [1,2,3,2,1,1] because there is one value (15 itself) that can be reached with zero iterations of (n - n/p) maps, two values (10 and 12) that can be reached after one iteration, three values (5, 8, and 6) that can be reached after two iterations, and so on.
      15
     _/ \_
    /     \
  10       12
  | \_   _/ |
  |   \ /   |
  5    8    6
   \_  |  _/|
     \_|_/  |
       4    3
       |  _/
       |_/
       2
       |
       |
       1
Table begins:
1
1, 1
1, 1, 1
1, 1, 1
1, 1, 1, 1
1, 2, 1, 1
1, 1, 2, 1, 1
1, 1, 1, 1
1, 1, 2, 1, 1
1, 2, 1, 1, 1
1, 1, 2, 1, 1, 1
1, 2, 2, 1, 1
1, 1, 2, 2, 1, 1
1, 2, 2, 2, 1, 1
1, 2, 3, 2, 1, 1
1, 1, 1, 1, 1

Michael De Vlieger, Table of n, a(n) for n = 1..12386 (rows 1 <= n <= 1000, flattened)
Michael De Vlieger, Hasse diagrams showing rows n = {55, 63, 171, ...} that increase and decrease more than once.
Michael De Vlieger, Table of n, b(n) for n = 1..10000, encoding the running total of row n of this sequence as a binary number expressed decimally.

Cf. A001221, A073933, A332809, A333123, A334111, A334144, A334238.

Cf. A000079, A019434.

Table[Length@ Union@ # & /@ Transpose@ # &@ If[n == 1, {{1}}, NestWhile[If[Length[#] == 0, Map[{n, #} &, # - # /FactorInteger[#][[All, 1]] ], Union[Join @@ Map[Function[{w, n}, Map[Append[w, If[n == 0, 0, n - n/#]] &, FactorInteger[n][[All, 1]] ]] @@ {#, Last@ #} &, #]]] &, n, If[ListQ[#], AllTrue[#, Last[#] > 1 &], # > 1] &]], {n, 22}] // Flatten (* Michael De Vlieger, Apr 18 2020 *)

T(n,0) = T(n, A073933(n) - 2) = T(n, A073933(n) - 1) = 1.

T(n,1) = A001221(n) for n > 1.

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.

Original entry on oeis.org

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

Antti Karttunen, Apr 04 2020

nonn

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.

			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.

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

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

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

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

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

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.

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.

Original entry on oeis.org

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

Antti Karttunen, Apr 05 2020

nonn

			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.

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

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

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

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

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

cp's OEIS Frontend

A333959 First occurrence of n in A334144.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A333123 Consider the mapping k -> (k - (k/p)), where p is any of k's prime factors. a(n) is the number of different possible paths from n to 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A334111 Irregular triangle where row n gives all terms k for which A064097(k) = n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A334184 Irregular table read by rows: T(n,k) gives the number of values that can be reached after exactly k iterations of maps of the form (n - n/p) where p is a prime divisor of n. 0 <= k < A073933(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

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.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI