login
A277615
a(1)=1; thereafter, if n = c(x_1)^...^c(x_k) (where c(k) = A007916(k) and with parentheses nested from the right, as in the definition of A277564), a(n) = 1 + a(x_1) + ... + a(x_k).
5
1, 2, 3, 3, 4, 4, 5, 4, 4, 5, 6, 5, 5, 6, 7, 4, 6, 6, 7, 8, 5, 7, 7, 8, 5, 9, 5, 6, 8, 8, 9, 5, 6, 10, 6, 5, 7, 9, 9, 10, 6, 7, 11, 7, 6, 8, 10, 10, 6, 11, 7, 8, 12, 8, 7, 9, 11, 11, 7, 12, 8, 9, 13, 5, 9, 8, 10, 12, 12, 8, 13, 9, 10, 14, 6, 10, 9, 11, 13, 13, 5, 9, 14, 10, 11, 15, 7, 11, 10, 12, 14, 14, 6, 10, 15, 11, 12
OFFSET
1,2
COMMENTS
A007916 lists the numbers whose prime multiplicities are relatively prime. For each n we can construct a plane tree by repeatedly factoring all positive integers at any level into their corresponding power towers of non-perfect-powers (see A277564). a(n) is the number of nodes in this plane tree.
FORMULA
First appearance of n is a(A277576(n)). Last appearance of n is a(2^^{n-1}) where ^^ denotes iterated exponentiation (or tetration).
Number of appearances of n is the Catalan number |{k:a(k)=n}| = C_{n-1}.
EXAMPLE
a(1)=1, a(2)=1+a(1)=2, a(3)=1+a(2)=3, a(4)=1+a(1)+a(1)=3 because 4=c(1)^c(1), a(8)=1+a(1)+a(2)=4 because 8=c(1)^c(2), a(9)=1+a(2)+a(1)=4 because 9=c(2)^c(1), a(10)=1+a(6)=5 because 10=c(6).
MATHEMATICA
nn=10000;
radicalQ[1]:=False; radicalQ[n_]:=SameQ[GCD@@FactorInteger[n][[All, 2]], 1];
hyperfactor[1]:={}; hyperfactor[n_?radicalQ]:={n};
hyperfactor[n_]:=With[{g=GCD@@FactorInteger[n][[All, 2]]}, Prepend[hyperfactor[g], Product[Apply[Power[#1, #2/g]&, r], {r, FactorInteger[n]}]]];
rad[0]:=1; rad[n_?Positive]:=rad[n]=NestWhile[#+1&, rad[n-1]+1, Not[radicalQ[#]]&]; Set@@@Array[radPi[rad[#]]==#&, nn];
rnk[n_]:=rnk[n]=1+Total[rnk/@radPi/@hyperfactor[n]];
Array[rnk, nn]
CROSSREFS
KEYWORD
nonn,look
AUTHOR
Gus Wiseman, Oct 23 2016
EXTENSIONS
Edited by N. J. A. Sloane, Nov 09 2016
STATUS
approved