cp's OEIS Frontend

A032447 Inverse function of phi( ).

%I A032447 #57 Oct 11 2019 15:19:15
%S A032447 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 A032447 17,32,34,40,48,60,19,27,38,54,25,33,44,50,66,23,46,35,39,45,52,56,70,
%U A032447 72,78,84,90,29,58,31,62,51,64,68,80,96,102,120,37,57,63,74,76,108,114,126
%N A032447 Inverse function of phi( ).
%C A032447 Arrange integers in order of increasing phi value; the phi values themselves form A007614.
%C A032447 Inverse of sequence A064275 considered as a permutation of the positive integers. - _Howard A. Landman_, Sep 25 2001
%C A032447 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 A032447 Sivaramakrishnan, The many facets of Euler's Totient, I. Nieuw Arch. Wisk. 4 (1986), 175-190.
%H A032447 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 A032447 D. Bressoud, <a href="http://www.macalester.edu/~bressoud/books/CNT.m">CNT.m</a> Computational Number Theory Mathematica package.
%H A032447 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 A032447 <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>
%e A032447 phi(1)=phi(2)=1, phi(3)=phi(4)=phi(6)=2, phi(5)=phi(8)=...=4, ...
%e A032447 From _Wolfdieter Lang_, Feb 19 2012: (Start)
%e A032447 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 A032447   l(n): 2, 3, 4, 4, 5, 2, 6, 6, 4, 5, ...
%e A032447    n, v(n)\m 1  2  3  4  5  6  7  8  9  10 11  12  13  14
%e A032447    1,  1:    1  2
%e A032447    2,  2:    3  4  6
%e A032447    3,  4:    5  8 10 12
%e A032447    4,  6:    7  9 14 18
%e A032447    5,  8:   15 16 20 24 30
%e A032447    6, 10:   11 22
%e A032447    7, 12:   13 21 26 28 36 42
%e A032447    8, 16:   17 32 34 40 48 60
%e A032447    9, 18:   19 27 38 54
%e A032447   10, 20:   25 33 44 50 66
%e A032447   ...
%e A032447 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 A032447 (End)
%t A032447 Needs["CNT`"]; Flatten[Table[PhiInverse[n], {n, 40}]] (* _T. D. Noe_, Oct 15 2012 *)
%t A032447 Take[Values@ PositionIndex@ Array[EulerPhi, 10^3], 15] // Flatten (* _Michael De Vlieger_, Dec 29 2017 *)
%t A032447 SortBy[Table[{n,EulerPhi[n]},{n,150}],Last][[All,1]] (* _Harvey P. Dale_, Oct 11 2019 *)
%o A032447 (PARI)
%o A032447 M = 9660; /* choose a term of A036913 */
%o A032447 v = vector(M, n, [eulerphi(n),n] );
%o A032447 v = vecsort(v, (x, y)-> if( x[1]-y[1]!=0, sign(x[1]-y[1]), sign(x[2]-y[2]) ) );
%o A032447 P=eulerphi(M);
%o A032447 v = select( x->(x[1]<=P), v );
%o A032447 /* A007614 = vector(#v,n, v[n][1] ) */
%o A032447 A032447 = vector(#v,n, v[n][2] )
%o A032447 /* for (n=1,#v, print(n," ", A032447[n]) ); */ /* b-file */
%o A032447 /* _Joerg Arndt_, Oct 06 2012 */
%o A032447 (Haskell)
%o A032447 import Data.List.Ordered (insertBag)
%o A032447 a032447 n = a032447_list !! (n-1)
%o A032447 a032447_list = f [1..] a002110_list [] where
%o A032447    f xs'@(x:xs) ps'@(p:ps) us
%o A032447      | x < p = f xs ps' $ insertBag (a000010' x, x) us
%o A032447      | otherwise = map snd vs ++ f xs' ps ws
%o A032447      where (vs, ws) = span ((<= a000010' x) . fst) us
%o A032447 -- _Reinhard Zumkeller_, Nov 22 2015
%o A032447 (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 A032447 Cf. A000010, A007614.
%Y A032447 Cf. A002110, A064275.
%K A032447 nonn,easy,nice,look
%O A032447 1,2
%A A032447 Ursula Gagelmann (gagelmann(AT)altavista.net)
%E A032447 Example corrected, more terms and program from _Olivier Gérard_, Feb 1999