%I #57 Oct 11 2019 15:19:15

%S 1,2,3,4,6,5,8,10,12,7,9,14,18,15,16,20,24,30,11,22,13,21,26,28,36,42,

%T 17,32,34,40,48,60,19,27,38,54,25,33,44,50,66,23,46,35,39,45,52,56,70,

%U 72,78,84,90,29,58,31,62,51,64,68,80,96,102,120,37,57,63,74,76,108,114,126

%N Inverse function of phi( ).

%C Arrange integers in order of increasing phi value; the phi values themselves form A007614.

%C Inverse of sequence A064275 considered as a permutation of the positive integers. - _Howard A. Landman_, Sep 25 2001

%C In the array shown in the example section row no. n gives exactly the N values for which the cyclotomic polynomials cyclotomic(N,x) have degree A002202(n). - _Wolfdieter Lang_, Feb 19 2012.

%D Sivaramakrishnan, The many facets of Euler's Totient, I. Nieuw Arch. Wisk. 4 (1986), 175-190.

%H T. D. Noe, <a href="/A032447/b032447.txt">Table of n, a(n) for n = 1..10000</a> (Corrected by _Dana Jacobsen_, Mar 04 2019)

%H D. Bressoud, <a href="http://www.macalester.edu/~bressoud/books/CNT.m">CNT.m</a> Computational Number Theory Mathematica package.

%H H. Gupta, <a href="http://www.insa.nic.in/writereaddata/UpLoadedFiles/IJPAM/20005a81_22.pdf">Euler’s totient function and its inverse</a>, Indian J. pure appl. Math., 12(1): 22-29(1981).

%H <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>

%e phi(1)=phi(2)=1, phi(3)=phi(4)=phi(6)=2, phi(5)=phi(8)=...=4, ...

%e From _Wolfdieter Lang_, Feb 19 2012: (Start)

%e Read as array a(n,m) with row length l(n):=A058277(v(n)) with v(n):= A002202(n), n>=1. a(n,m) = m-th element of the set {m from positive integers: phi(m)=v(n)} when read as an increasingly ordered list.

%e l(n): 2, 3, 4, 4, 5, 2, 6, 6, 4, 5, ...

%e n, v(n)\m 1 2 3 4 5 6 7 8 9 10 11 12 13 14

%e 1, 1: 1 2

%e 2, 2: 3 4 6

%e 3, 4: 5 8 10 12

%e 4, 6: 7 9 14 18

%e 5, 8: 15 16 20 24 30

%e 6, 10: 11 22

%e 7, 12: 13 21 26 28 36 42

%e 8, 16: 17 32 34 40 48 60

%e 9, 18: 19 27 38 54

%e 10, 20: 25 33 44 50 66

%e ...

%e Row no. n=4: The cyclotomic polynomials cyclotomic(N,x) with values N = 7,9,14, and 18 have degree 6, and only these.

%e (End)

%t Needs["CNT`"]; Flatten[Table[PhiInverse[n], {n, 40}]] (* _T. D. Noe_, Oct 15 2012 *)

%t Take[Values@ PositionIndex@ Array[EulerPhi, 10^3], 15] // Flatten (* _Michael De Vlieger_, Dec 29 2017 *)

%t SortBy[Table[{n,EulerPhi[n]},{n,150}],Last][[All,1]] (* _Harvey P. Dale_, Oct 11 2019 *)

%o (PARI)

%o M = 9660; /* choose a term of A036913 */

%o v = vector(M, n, [eulerphi(n),n] );

%o v = vecsort(v, (x, y)-> if( x[1]-y[1]!=0, sign(x[1]-y[1]), sign(x[2]-y[2]) ) );

%o P=eulerphi(M);

%o v = select( x->(x[1]<=P), v );

%o /* A007614 = vector(#v,n, v[n][1] ) */

%o A032447 = vector(#v,n, v[n][2] )

%o /* for (n=1,#v, print(n," ", A032447[n]) ); */ /* b-file */

%o /* _Joerg Arndt_, Oct 06 2012 */

%o (Haskell)

%o import Data.List.Ordered (insertBag)

%o a032447 n = a032447_list !! (n-1)

%o a032447_list = f [1..] a002110_list [] where

%o f xs'@(x:xs) ps'@(p:ps) us

%o | x < p = f xs ps' $ insertBag (a000010' x, x) us

%o | otherwise = map snd vs ++ f xs' ps ws

%o where (vs, ws) = span ((<= a000010' x) . fst) us

%o -- _Reinhard Zumkeller_, Nov 22 2015

%o (Perl) use ntheory ":all"; my($n,$k,$i,@v)=(10000,1,0); push @v,inverse_totient($k++) while @v<$n; $#v=$n-1; say ++$i," $_" for @v; # _Dana Jacobsen_, Mar 04 2019

%Y Cf. A000010, A007614.

%Y Cf. A002110, A064275.

%K nonn,easy,nice,look

%O 1,2

%A Ursula Gagelmann (gagelmann(AT)altavista.net)

%E Example corrected, more terms and program from _Olivier Gérard_, Feb 1999