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

Author

Robert G. Wilson v, Oct 31 2023

Keywords

• nonn

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.

Examples

			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.
		

Crossrefs

Cf. A366929 (records).

Programs

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]