cp's OEIS Frontend

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

%I A115588 #28 Feb 25 2025 09:00:07
%S A115588 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,
%T A115588 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,
%U A115588 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
%N A115588 Number of distinct prime numbers necessary to represent a natural number n > 1.
%C A115588 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
%C A115588 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
%H A115588 Alois P. Heinz, <a href="/A115588/b115588.txt">Table of n, a(n) for n = 2..10000</a>
%e A115588 a(4)=1, since 4=2^2 and the only prime used was 2.
%e A115588 a(30)=3 because 30=2*3*5 and three primes were necessary.
%e A115588 a(65536)=1, since 65536=2^16=2^(2^4)=2^(2^(2^2)) and, again, only one prime was needed.
%e A115588 a(1) would be undefined, so it is not included.
%p A115588 b:= n-> `if`(n=1, {}, {seq([i[1], b(i[2])[]][], i=ifactors(n)[2])}):
%p A115588 a:= n-> nops(b(n)):
%p A115588 seq(a(n), n=1..200);  # _Alois P. Heinz_, Apr 27 2012
%t A115588 A115588[n_] := Length[Union[NestWhile[DeleteCases[Flatten[FactorInteger[#]], 1] &, {n}, AnyTrue[#, CompositeQ] &]]];
%t A115588 Array[A115588, 100, 2] (* _Paolo Xausa_, Feb 24 2025 *)
%o A115588 (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;}
%o A115588 a(n) = {my(f=factor(n), list=List()); #select(isprime, Set(Vec(listf(f, list))));} \\ _Michel Marcus_, Dec 02 2020
%Y A115588 Cf. A000040, A001221, A002110, A381399, A381400.
%K A115588 nonn
%O A115588 2,5
%A A115588 _Lucas B. Vieira_, Mar 09 2006