login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A058811 Number of terms on the n-th level of the Inverse-Totient-Tree (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 n-th level as the union of the inverse phi sets of the terms occurring earlier on the n-th level. 3
1, 1, 3, 8, 17, 41, 92, 215, 487, 1126, 2583, 5981, 13698, 31647, 72678, 167474, 385021, 887133, 2041375, 4700526, 10817997, 24908164, 57334111, 131995229 (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 level-set may have entries either from A007617, A005278 (initial nodes of the tree) or from A000010 (invphi-continuable numbers).
Results of Shapiro show that largest number in the n-th level is 2*3^(n-1). The Mathematica code first computes A003434(k) for k <= 2*3^(n-1); then it gives the number of numbers k for which A003434(k) = n. - T. D. Noe, Mar 08 2004
LINKS
Harold Shapiro, An arithmetic function arising from the phi function, Amer. Math. Monthly, Vol. 50, No. 1 (1943), 18-30.
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 i-th 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^(nMax-1); 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. A003434 (iterations of phi(n) needed to reach 1).
Sequence in context: A247374 A336512 A046994 * A101822 A354538 A088589
KEYWORD
nonn,more
AUTHOR
Labos Elemer, Jan 03 2001
EXTENSIONS
a(13)-a(16) from T. D. Noe, Mar 08 2004
a(17)-a(23) from Sean A. Irvine, Aug 28 2022
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 18 22:56 EDT 2024. Contains 370952 sequences. (Running on oeis4.)