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.

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

Comments

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.

Links

Table of n, a(n) for n=1..105.

Example

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.

Mathematica

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]

Crossrefs

Cf. A366929 (records).

Sequence in context: A180094 A333870 A354914 * A103748 A104231 A105111

Adjacent sequences: A366924 A366925 A366926 * A366928 A366929 A366930

Keyword

nonn

Author

Robert G. Wilson v, Oct 31 2023

Status

approved