A333001 -id:A333001 - cp's OEIS frontend

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.

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

A333000 Sum of integers (with multiplicity) encountered on all possible paths from n to 1 when iterating with nondeterministic map k -> k- k/p, where p is any prime factor of k.

Original entry on oeis.org

1, 3, 6, 7, 12, 25, 39, 15, 43, 47, 69, 76, 115, 185, 198, 31, 48, 209, 304, 138, 604, 317, 432, 203, 213, 500, 344, 640, 901, 899, 1271, 63, 1777, 179, 2274, 736, 1069, 1572, 1860, 361, 525, 3156, 4360, 1074, 2580, 2150, 2808, 506, 4528, 924, 1042, 1630, 2266, 1836, 2878, 1930, 5004, 4165, 5522, 3026, 4307, 6343, 7638, 127, 6801

Offset: 1

Antti Karttunen, Apr 06 2020

nonn

			a(12): we have three alternative paths: {12, 8, 4, 2, 1}, {12, 6, 4, 2, 1} or {12, 6, 3, 2, 1}, therefore a(12) = (12+8+4+2+1) + (12+6+4+2+1) + (12+6+3+2+1) = 27+25+24 = 76
For n=15 we have five alternative paths from 15 to 1 (illustrated below): therefore a(15) = (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) = 37+40+42+40+39 = 198.
        15
       / \
      /   \
    10     12
    / \   / \
   /   \ /   \
  5     8     6
   \__  |  __/|
      \_|_/   |
        4     3
         \   /
          \ /
           2
           |
           1.

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

Cf. A332904, A333001, A333123.

up_to = 20000;
A333000list(up_to) = { my(u=vector(up_to), v=vector(up_to)); u[1] = v[1] = 1; for(n=2,up_to, u[n] = vecsum(apply(p -> u[n-n/p], factor(n)[, 1]~)); v[n] = (u[n]*n)+vecsum(apply(p -> v[n-n/p], factor(n)[, 1]~))); (v); };
v333000 = A333000list(up_to);
A333000(n) = v333000[n];

a(n) = n*A333123(n) + Sum_{p prime and dividing n} a(n - n/p).

For all n, a(n) >= A332904(n).

A333790 Smallest path sum when iterating from n to 1 with nondeterministic map k -> k - k/p, where p is any prime factor of k.

Original entry on oeis.org

1, 3, 6, 7, 12, 12, 19, 15, 21, 22, 33, 24, 37, 33, 37, 31, 48, 39, 58, 42, 54, 55, 78, 48, 67, 63, 66, 61, 90, 67, 98, 63, 88, 82, 96, 75, 112, 96, 102, 82, 123, 96, 139, 99, 112, 124, 171, 96, 145, 117, 133, 115, 168, 120, 154, 117, 153, 148, 207, 127, 188, 160, 159, 127, 180, 154, 221, 150, 193, 166, 237, 147, 220, 186, 192, 172, 231

Offset: 1

Antti Karttunen, Apr 06 2020

nonn

Note that although in many cases a simple heuristics of always subtracting the largest proper divisor (i.e., iterating with A060681) gives the path with the minimal sum, this does not hold for the following numbers 119, 143, 187, 209, 221, ..., A333789, on which this sequence differs from A073934.

			For n=119, the graph obtained is this:
              119
             _/\_
            /    \
          102    112
         _/|\_    | \_
       _/  |  \_  |   \_
      /    |    \ |     \
    51     68    96     56
    /|   _/ |   _/|   _/ |
   / | _/   | _/  | _/   |
  /  |/     |/    |/     |
(48) 34    64     48    28
     |\_    |    _/|   _/|
     |  \_  |  _/  | _/  |
     |    \_|_/    |/    |
    17     32     24    14
      \_    |    _/|   _/|
        \_  |  _/  | _/  |
          \_|_/    |/    |
           16      12    7
            |    _/|    _/
            |  _/  |  _/
            |_/    |_/
            8     _6
            |  __/ |
            |_/    |
            4      3
             \     /
              \_ _/
                2
                |
                1.
By choosing the path that follows the right edge of the above diagram, we obtain the smallest sum for any such path that goes from 119 to 1, thus a(119) = 119+112+56+28+14+7+6+3+2+1 = 348.
Note that if we always subtracted the largest proper divisor (A032742), i.e., iterated with A060681 (starting from 119), we would obtain 119-(119/7) = 102 -> 102-(102/2) -> 51-(51/3) -> 34-(34/2) -> 17-(17/17) -> 16-(16/2) -> 8-(8/2) -> 4-(4/2) -> 2-(2/2) -> 1, with sum 119+102+51+34+17+16+8+4+2+1 = 354 = A073934(119), which is NOT minimal sum in this case.

Antti Karttunen, Table of n, a(n) for n = 1..20000
Michael De Vlieger, Graph montage of k -> k - k/p, with prime p|k for 2 <= k <= 121, red line showing path of least sum.

Cf. A032742, A060681, A332904, A333000, A333001, A333123, A333794.

Differs from A073934 for the first time at n=119, where a(119) = 348, while A073934(119) = 354. (See A333789).

Min@ Map[Total, #] & /@ Nest[Function[{a, n}, Append[a, Join @@ Table[Flatten@ Prepend[#, n] & /@ a[[n - n/p]], {p, FactorInteger[n][[All, 1]]}]]] @@ {#, Length@ # + 1} &, {{{1}}}, 76]   (* Michael De Vlieger, Apr 14 2020 *)

up_to = 65537; \\ 2^20;
A333790list(up_to) = { my(v=vector(up_to)); v[1] = 1; for(n=2, up_to, v[n] = n+vecmin(apply(p -> v[n-n/p], factor(n)[, 1]~))); (v); };
v333790 = A333790list(up_to);
A333790(n) = v333790[n];

a(n) = n + Min a(n - n/p), for p prime and dividing n.

For n >= 1, a(n) <= A333794(n) <= A332904(n), a(n) <= A333001(n).

A333003 Denominator of the average path sum when iterating from n to 1 with nondeterministic map k -> k - k/p, where p is any prime factor of k.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 2, 1, 2, 2, 2, 3, 3, 1, 5, 1, 1, 5, 5, 1, 5, 5, 5, 4, 1, 7, 5, 9, 9, 12, 12, 1, 17, 2, 7, 9, 9, 7, 4, 4, 4, 7, 7, 3, 7, 7, 7, 5, 7, 1, 7, 6, 6, 7, 8, 7, 7, 23, 23, 21, 21, 33, 7, 1, 11, 47, 47, 1, 61, 28, 28, 7, 7, 23, 14, 2, 103, 3, 3, 5, 7, 1, 1, 1, 4, 21, 79, 7, 7, 7, 7, 7, 89, 7, 14, 2, 2, 21, 103, 1, 1, 16, 16, 18, 84

Offset: 1

Antti Karttunen, Apr 06 2020

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

See A333002 for numerator.

Cf. A333000, A333001, A333123, A333785 (positions of ones).

Map[Denominator@ Mean[Total /@ #] &, #] &@ Nest[Function[{a, n}, Append[a, Join @@ Table[Flatten@ Prepend[#, n] & /@ a[[n - n/p]], {p, FactorInteger[n][[All, 1]]}]]] @@ {#, Length@ # + 1} &, {{{1}}}, 104] (* Michael De Vlieger, Apr 15 2020 *)

up_to = 20000;
A333003list(up_to) = { my(u=vector(up_to), v=vector(up_to)); u[1] = v[1] = 1; for(n=2,up_to, my(ps=factor(n)[, 1]~); u[n] = vecsum(apply(p -> u[n-n/p], ps)); v[n] = (u[n]*n)+vecsum(apply(p -> v[n-n/p], ps))); vector(up_to, n, denominator(v[n]/u[n])); };
v333003 = A333003list(up_to);
A333003(n) = v333003[n];

a(n) = denominator(A333000(n)/A333123(n)).

A333785 Numbers m such that the average path sum is an integer when iterating from m to 1 with nondeterministic map k -> k - k/p, where p is any prime factor of k.

Original entry on oeis.org

1, 2, 3, 4, 5, 8, 14, 16, 17, 20, 25, 32, 50, 64, 68, 82, 83, 84, 100, 101, 125, 128, 162, 163, 170, 235, 243, 256, 257, 272, 289, 456, 457, 512, 548, 621, 1024, 1028, 1040, 2048, 4096, 4112, 7225, 8192, 8738, 9248, 13058, 16384, 16480, 16481, 17476, 17477, 32128, 32768, 65536, 65537, 131072, 132098, 262144, 262148, 264196

Offset: 1

Antti Karttunen, Apr 06 2020

nonn

Numbers m such that A333123(m) divides A333000(m).

Positions of ones in A333003.

Antti Karttunen, Table of n, a(n) for n = 1..75; all terms up to <= 2^23

Cf. A333000, A333001, A333003, A333123.

Subsequences: A000079, A019434.

Position[Map[Mean[Total /@ #] &, #], ?IntegerQ][[All, 1]] &@ Nest[Function[{a, n}, Append[a, Join @@ Table[Flatten@ Prepend[#, n] & /@ a[[n - n/p]], {p, FactorInteger[n][[All, 1]]}]]] @@ {#, Length@ # + 1} &, {{{1}}}, 2^10 + 1] (* _Michael De Vlieger, Apr 15 2020 *)

A333002 Numerator of the average path sum when iterating from n to 1 with nondeterministic map k -> k - k/p, where p is any prime factor of k.

Original entry on oeis.org

1, 3, 6, 7, 12, 25, 39, 15, 43, 47, 69, 76, 115, 37, 198, 31, 48, 209, 304, 46, 302, 317, 432, 203, 71, 500, 344, 640, 901, 899, 1271, 63, 1777, 179, 758, 736, 1069, 786, 465, 361, 525, 789, 1090, 358, 860, 1075, 1404, 506, 1132, 132, 1042, 815, 1133, 918, 1439, 965, 1251, 4165, 5522, 3026, 4307, 6343, 1273, 127

Offset: 1

Antti Karttunen, Apr 06 2020

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

See A333003 for denominator.

Cf. A333000, A333001, A333123.

Map[Numerator@ Mean[Total /@ #] &, #] &@ Nest[Function[{a, n}, Append[a, Join @@ Table[Flatten@Prepend[#, n] & /@ a[[n - n/p]], {p, FactorInteger[n][[All, 1]]}]]] @@ {#, Length@ # + 1} &, {{{1}}}, 63] (* Michael De Vlieger, Apr 15 2020 *)

up_to = 20000;
A333002list(up_to) = { my(u=vector(up_to), v=vector(up_to)); u[1] = v[1] = 1; for(n=2,up_to, my(ps=factor(n)[, 1]~); u[n] = vecsum(apply(p -> u[n-n/p], ps)); v[n] = (u[n]*n)+vecsum(apply(p -> v[n-n/p], ps))); vector(up_to, n, numerator(v[n]/u[n])); };
v333002 = A333002list(up_to);
A333002(n) = v333002[n];

a(n) = numerator(A333000(n)/A333123(n)).

cp's OEIS Frontend

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

A333000 Sum of integers (with multiplicity) encountered on all possible paths from n to 1 when iterating with nondeterministic map k -> k- k/p, where p is any prime factor of k.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

A333790 Smallest path sum when iterating from n to 1 with nondeterministic map k -> k - k/p, where p is any prime factor of k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A333003 Denominator of the average path sum when iterating from n to 1 with nondeterministic map k -> k - k/p, where p is any prime factor of k.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A333785 Numbers m such that the average path sum is an integer when iterating from m to 1 with nondeterministic map k -> k - k/p, where p is any prime factor of k.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A333002 Numerator of the average path sum when iterating from n to 1 with nondeterministic map k -> k - k/p, where p is any prime factor of k.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula