|
|
A115588
|
|
Number of distinct prime numbers necessary to represent a natural number n > 1.
|
|
4
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
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)):
|
|
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
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|