A332810 -id:A332810 - 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

A332809 Number of distinct integers encountered on possible paths from n to 1 when iterating the nondeterministic map k -> k - k/p, where p is any of the prime factors of k.

Original entry on oeis.org

1, 2, 3, 3, 4, 5, 6, 4, 6, 6, 7, 7, 8, 9, 10, 5, 6, 9, 10, 8, 12, 10, 11, 9, 9, 11, 10, 12, 13, 14, 15, 6, 17, 8, 18, 12, 13, 14, 15, 10, 11, 17, 18, 13, 18, 15, 16, 11, 18, 12, 14, 14, 15, 14, 16, 15, 17, 17, 18, 18, 19, 20, 20, 7, 22, 23, 24, 10, 26, 24, 25, 15, 16, 17, 21, 18, 30, 20, 21, 12, 15, 14, 15, 22, 16, 24, 25, 16

Offset: 1

Antti Karttunen, Apr 04 2020

The count includes also n itself, and the final 1 when it is distinct from n.

a(n) >= A000005(n) because all divisors of n can be found in the union of those paths. - Antti Karttunen, Apr 19 2020

			a(1): {1}, therefore a(1) = 1;
a(6): we have two alternative paths: {6, 4, 2, 1} or {6, 3, 2, 1}, with numbers [1, 2, 3, 4, 6] present, therefore a(6) = 5;
a(12): we have three alternative paths: {12, 8, 4, 2, 1}, {12, 6, 4, 2, 1} or {12, 6, 3, 2, 1}, with numbers [1, 2, 3, 4, 6, 8, 12] present, therefore a(12) = 7;
a(14): we have five alternative paths: {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}, with numbers [1, 2, 3, 4, 6, 7, 8, 12, 14] present in at least one of the paths, therefore a(14) = 9.

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

Cf. A064097, A332810, A333123, A334230, A334231, A333786 (first occurrence of each n), A334112.
Partial sums of A332902.
See A332904 for the sum.

a[n_] := Block[{lst = {{n}}}, While[lst[[-1]] != {1}, lst = Join[ lst, {Union[ Flatten[# - #/(First@# & /@ FactorInteger@#) & /@ lst[[-1]]]]}]]; Length@ Union@ Flatten@ lst]; Array[a, 75] (* Robert G. Wilson v, Apr 06 2020 *)

up_to = 105;
A332809list(up_to) = { my(v=vector(up_to)); v[1] = Set([1]); for(n=2,up_to, my(f=factor(n)[, 1]~, s=Set([n])); for(i=1,#f,s = setunion(s,v[n-(n/f[i])])); v[n] = s); apply(length,v); }
v332809 = A332809list(up_to);
A332809(n) = v332809[n];

from sympy import factorint
from functools import cache
@cache
def b(n): return {n}.union(*(b(n - n//p) for p in factorint(n)))
def a(n): return len(b(n))
print([a(n) for n in range(1, 89)]) # Michael S. Branicky, Aug 13 2022

a(p) = 1 + a(p-1) for all primes p.
a(n) = n - A332810(n).
a(n) = A334112(n) + A000005(n). - Antti Karttunen, May 09 2020

A366927 Number of distinct primes p used in the mapping of k = k - k/p terminating at 1, where p is any of the prime factors of k.

Original entry on oeis.org

0, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 3, 1, 2, 2, 3, 2, 3, 3, 4, 2, 2, 3, 2, 3, 4, 3, 4, 1, 4, 2, 4, 2, 3, 3, 3, 2, 3, 3, 4, 3, 3, 4, 5, 2, 3, 2, 3, 3, 4, 2, 3, 3, 3, 4, 5, 3, 4, 4, 3, 1, 4, 4, 5, 2, 5, 4, 5, 2, 3, 3, 3, 3, 5, 3, 4, 2, 2, 3, 4, 3, 3, 4, 4, 3, 4, 3, 4, 4, 4, 5, 4, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4

Offset: 1

Robert G. Wilson v, Oct 31 2023

nonn

A001221(n) <= a(n) <= pi(n) = A000720(n).
Just because some prime < n is not a prime factor of n does not preclude it from being a prime used in the cascade from n to 1. Take, for instance, n=14; 14 -> 12 and 3 is a prime factor of 12 but not of 14.
If p is a prime factor of n, then a(p^e * n) = a(n), where e is any exponent.
The number of primes p counting multiplicity is obviously the same as the path length, A332810. For n>1, 2 is always one of the primes.

			a(1) = 0 because 1 is at the end of all iterations;
a(2) = 1 since 2 -> 2 - 2/2 = 1, so there is one iteration of the mapping and it only involves the prime 2;
a(3) = 2 since 3 -> 2 -> 1 and this involves two primes, 2 and 3;
a(7) = 3 since 7 -> 6 -> 3 or 2 and this involves three primes, 7, 3, and 2; etc.

Cf. A366929 (records).

a[n_] := Block[{m = n, p, lst = {}}, While[m > 1, p = FactorInteger[m][[1, 1]]; AppendTo[lst, p]; m = m - m/p]; Length@ Union@ lst]; Array[a, 105]

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

A332809 Number of distinct integers encountered on possible paths from n to 1 when iterating the nondeterministic map k -> k - k/p, where p is any of the prime factors of k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

A366927 Number of distinct primes p used in the mapping of k = k - k/p terminating at 1, where p is any of the prime factors of k.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica