A032447 Inverse function of phi( ).

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, 17, 32, 34, 40, 48, 60, 19, 27, 38, 54, 25, 33, 44, 50, 66, 23, 46, 35, 39, 45, 52, 56, 70, 72, 78, 84, 90, 29, 58, 31, 62, 51, 64, 68, 80, 96, 102, 120, 37, 57, 63, 74, 76, 108, 114, 126

Offset: 1

Author

Ursula Gagelmann (gagelmann(AT)altavista.net)

Keywords

• nonn
• easy
• nice
• look

Comments

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

Inverse of sequence A064275 considered as a permutation of the positive integers. - Howard A. Landman, Sep 25 2001

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.

Examples

			phi(1)=phi(2)=1, phi(3)=phi(4)=phi(6)=2, phi(5)=phi(8)=...=4, ...
From _Wolfdieter Lang_, Feb 19 2012: (Start)
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.
  l(n): 2, 3, 4, 4, 5, 2, 6, 6, 4, 5, ...
   n, v(n)\m 1  2  3  4  5  6  7  8  9  10 11  12  13  14
   1,  1:    1  2
   2,  2:    3  4  6
   3,  4:    5  8 10 12
   4,  6:    7  9 14 18
   5,  8:   15 16 20 24 30
   6, 10:   11 22
   7, 12:   13 21 26 28 36 42
   8, 16:   17 32 34 40 48 60
   9, 18:   19 27 38 54
  10, 20:   25 33 44 50 66
  ...
Row no. n=4: The cyclotomic polynomials cyclotomic(N,x) with values N = 7,9,14, and 18 have degree 6, and only these.
(End)
		

References

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

Links

• T. D. Noe, Table of n, a(n) for n = 1..10000 (Corrected by _Dana Jacobsen_, Mar 04 2019)
• D. Bressoud, CNT.m Computational Number Theory Mathematica package.
• H. Gupta, Euler’s totient function and its inverse, Indian J. pure appl. Math., 12(1): 22-29(1981).
• Index entries for sequences that are permutations of the natural numbers

Crossrefs

Cf. A000010, A007614.

Cf. A002110, A064275.

Programs

Haskell

import Data.List.Ordered (insertBag)
a032447 n = a032447_list !! (n-1)
a032447_list = f [1..] a002110_list [] where
   f xs'@(x:xs) ps'@(p:ps) us
     | x < p = f xs ps' $ insertBag (a000010' x, x) us
     | otherwise = map snd vs ++ f xs' ps ws
     where (vs, ws) = span ((<= a000010' x) . fst) us
-- Reinhard Zumkeller, Nov 22 2015

Mathematica

Needs["CNT`"]; Flatten[Table[PhiInverse[n], {n, 40}]] (* T. D. Noe, Oct 15 2012 *)
Take[Values@ PositionIndex@ Array[EulerPhi, 10^3], 15] // Flatten (* Michael De Vlieger, Dec 29 2017 *)
SortBy[Table[{n,EulerPhi[n]},{n,150}],Last][[All,1]] (* Harvey P. Dale, Oct 11 2019 *)

PARI

M = 9660; /* choose a term of A036913 */
v = vector(M, n, [eulerphi(n),n] );
v = vecsort(v, (x, y)-> if( x[1]-y[1]!=0, sign(x[1]-y[1]), sign(x[2]-y[2]) ) );
P=eulerphi(M);
v = select( x->(x[1]<=P), v );
/* A007614 = vector(#v,n, v[n][1] ) */
A032447 = vector(#v,n, v[n][2] )
/* for (n=1,#v, print(n," ", A032447[n]) ); */ /* b-file */
/* Joerg Arndt, Oct 06 2012 */

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

Extensions

Example corrected, more terms and program from Olivier Gérard, Feb 1999