

A058811


Number of terms on the nth level of the InverseTotientTree (ITT). The 0th, 1st, 2nd and 3rd levels are {1}, {2}, {3, 4, 6}, {5, 7, 8, 9, 10, 12, 14, 18} with 1, 1, 3, 8 entries resp. The (n+1)st level is obtained from the nth level as the union of the inverse phi sets of the terms occurring earlier on the nth level.


3



1, 1, 3, 8, 17, 41, 92, 215, 487, 1126, 2583, 5981, 13698, 31647, 72678, 167474, 385021
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

Level 0 is the set {1}, and level k>=1 is the set of numbers t such that phi(t) is in the set of level k; a(n) is the cardinality of the set in level n.  Joerg Arndt, Jan 07 2015
The 3rd level is {5, 8, 10, 12, 7, 9, 14, 18} and a(3)=8. Generate invphi(5)={}, .., invphi(12)={13, 21, 26, 28, 36, 42}, ..., invphi(14)={}, .. The union of these inverses gives the 4th Floor ={15, 16, 20, 24, 30, 11, 22, 13, 21, 26, 28, 36, 42, 19, 27, 38, 54}, which has 17 terms. So a(4)=17. Each levelset may have entries either from A007617, A005278 (initial nodes of the tree) or from A000010 (invphicontinuable numbers).
Results of Shapiro show that largest number in the nth level is 2*3^(n1). The Mathematica code first computes A003434(k) for k <= 2*3^(n1); then it gives the number of numbers k for which A003434(k) = n.  T. D. Noe, Mar 08 2004


LINKS

Table of n, a(n) for n=0..16.
Max Alekseyev, PARI scripts for various problems
Harold Shapiro, An arithmetic function arising from the phi function, Amer. Math. Monthly, Vol. 50, No. 1 (1943), 1830.


FORMULA

a(n) = Cardinality[Floor(n)], where Floor(0)={1}, Floor(n+1)=Union[invphi(t(i, n)), i=1..a(n))], where t(i, n) is the ith integer in Floor(n), ordered by size or lexicographically.


MATHEMATICA

Table[ Length[ Select[ Range[ 1, 1050000 ], Equal[ flo[ # ], k ]& ] ], {k, 1, 20} ], where flo[ x_ ] := Length[ Delete[ FixedPointList[ EulerPhi, x ], 1 ] ]
nMax=16; kMax=2*3^(nMax1); a=Table[0, {kMax}]; Do[e=EulerPhi[k]; a[[k]]=1+a[[e]], {k, 2, kMax}]; Table[Count[a, _?(#==n &)], {n, 0, nMax}]


PROG

(PARI) lista(nn) = {my(v = [1]); print1(#v, ", "); for (n=1, nn, my(nv = []); for (i=1, #v, nv = Set(concat(nv, invphi(v[i]))); ); nv = setminus(nv, v); print1(#nv, ", "); v = nv; ); } \\ Michel Marcus, Sep 02 2019


CROSSREFS

Cf. A000010, A007617, A005278.
Cf. A003434 (iterations of phi(n) needed to reach 1).
Sequence in context: A247374 A336512 A046994 * A101822 A088589 A319764
Adjacent sequences: A058808 A058809 A058810 * A058812 A058813 A058814


KEYWORD

nonn,more


AUTHOR

Labos Elemer, Jan 03 2001


EXTENSIONS

More terms from T. D. Noe, Mar 08 2004


STATUS

approved



