OFFSET
2,5
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
LINKS
Alois P. Heinz, Table of n, a(n) for n = 2..10000
EXAMPLE
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.
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 *)
PROG
(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
CROSSREFS
KEYWORD
nonn,changed
AUTHOR
Lucas B. Vieira, Mar 09 2006
STATUS
approved