A115588 Number of distinct prime numbers necessary to represent a natural number n > 1.

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

Offset: 2

Author

Lucas B. Vieira, Mar 09 2006

Keywords

• nonn

Comments

The sequence gives the number of distinct prime numbers needed to represent a given natural number greater than or equal to 2 upon recursive factorization of powers. In order to do this, we must factor any subsequent composite number that may appear on the exponents of the next factorizations (e.g., 4 in 48=2^4*3), until only prime numbers are used. - Lucas B. Vieira, Mar 15 2006

In this sequence, a(n)=1 if n is prime, or a power tower (tetration or iterated exponentiation) of a prime base (e.g., 2^2, 3^3^3^3, 7^7). The sequence reaches a new boundary whenever n is a primorial number (factorial of primes). - Lucas B. Vieira, Mar 15 2006

Examples

			a(4)=1, since 4=2^2 and the only prime used was 2.
a(30)=3 because 30=2*3*5 and three primes were necessary.
a(65536)=1, since 65536=2^16=2^(2^4)=2^(2^(2^2)) and, again, only one prime was needed.
a(1) would be undefined, so it is not included.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 2..10000

Crossrefs

Cf. A000040, A001221, A002110, A381399, A381400.

Programs

Maple

b:= n-> `if`(n=1, {}, {seq([i[1], b(i[2])[]][], i=ifactors(n)[2])}):
a:= n-> nops(b(n)):
seq(a(n), n=1..200);  # Alois P. Heinz, Apr 27 2012

Mathematica

A115588[n_] := Length[Union[NestWhile[DeleteCases[Flatten[FactorInteger[#]], 1] &, {n}, AnyTrue[#, CompositeQ] &]]];
Array[A115588, 100, 2] (* Paolo Xausa, Feb 24 2025 *)

PARI

listf(f, list) = {for (k=1, #f~, listput(list, f[k,1]); if (isprime(f[k,2]), listput(list, f[k,2]), if (f[k,2] > 1, my(vexp = Vec(listf(factor(f[k,2]), list))); for (i=1, #vexp, listput(list, vexp[i]););););); list;}
a(n) = {my(f=factor(n), list=List()); #select(isprime, Set(Vec(listf(f, list))));} \\ Michel Marcus, Dec 02 2020