OFFSET
1,2
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.
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).
EXAMPLE
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)
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 *)
PROG
(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 */
(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
(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
CROSSREFS
KEYWORD
AUTHOR
Ursula Gagelmann (gagelmann(AT)altavista.net)
EXTENSIONS
Example corrected, more terms and program from Olivier Gérard, Feb 1999
STATUS
approved