The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A002202 Values taken by totient function phi(m) (A000010).
(Formerly M0987 N0371)

%I M0987 N0371

%S 1,2,4,6,8,10,12,16,18,20,22,24,28,30,32,36,40,42,44,46,48,52,54,56,

%T 58,60,64,66,70,72,78,80,82,84,88,92,96,100,102,104,106,108,110,112,

%U 116,120,126,128,130,132,136,138,140,144,148,150,156,160,162,164,166,168,172,176

%N Values taken by totient function phi(m) (A000010).

%C These are the numbers n such that for some m the multiplicative group mod m has order n.

%C Maier & Pomerance show that there are about x * exp(c (log log log x)^2)/log x members of this sequence up to x, with c = 0.81781465... (A234614); see the paper for details on making this precise. - _Charles R Greathouse IV_, Dec 28 2013

%C A264739(a(n)) = 1; a(n) occurs A058277(n) times in A007614. - _Reinhard Zumkeller_, Nov 26 2015

%C There are no odd numbers > 2 in the sequence and the even numbers that are not in the sequence are in A005277. - _Bernard Schott_, May 13 2020

%D J. W. L. Glaisher, Number-Divisor Tables. British Assoc. Math. Tables, Vol. 8, Camb. Univ. Press, 1940, p. 64.

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H T. D. Noe, <a href="/A002202/b002202.txt">Table of n, a(n) for n = 1..10000</a>

%H André Contiero, and Davi Lima, <a href="https://arxiv.org/abs/2005.05475">2-Adic Stratification of Totients</a>, arXiv:2005.05475 [math.NT], 2020.

%H K. Ford, <a href="http://www.ams.org/era/1998-04-05/S1079-6762-98-00043-2/home.html">The distribution of totients</a>, Electron. Res. Announc. Amer. Math. Soc. 4 (1998), 27-34.

%H Helmut Maier and Carl Pomerance, <a href="http://matwbn.icm.edu.pl/ksiazki/aa/aa49/aa4934.pdf">On the number of distinct values of Euler's phi-function</a>, Acta Arithmetica 49:3 (1988), pp. 263-275.

%H Maxim Rytin, <a href="http://library.wolfram.com/infocenter/MathSource/696/"> Finding the Inverse of Euler Totient Function </a> (1999).

%H S. Sivasankaranarayana Pillai, <a href="http://dx.doi.org/10.1090/S0002-9904-1929-04799-2">On some functions connected with phi(n)</a>, Bull. Amer. Math. Soc. 35 (1929), 832-836.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/TotientValenceFunction.html">Totient Valence Function</a>

%p with(numtheory); t1 := [seq(nops(invphi(n)), n=1..300)]; t2 := []: for n from 1 to 300 do if t1[n] <> 0 then t2 := [op(t2), n]; fi; od: t2;

%t phiQ[m_] := Select[Range[m+1, 2m*Product[(1-1/(k*Log[k]))^(-1), {k, 2, DivisorSigma[0, m]}]], EulerPhi[#] == m &, 1 ] != {}; Select[Range[176], phiQ] (* _Jean-François Alcover_, May 23 2011, after Maxim Rytin *)

%o (PARI) lst(lim)=my(P=1,q,v);forprime(p=2,default(primelimit), if(eulerphi(P*=p)>=lim,q=p;break));v=vecsort(vector(P/q*lim\eulerphi(P/q),k,eulerphi(k)),,8);select(n->n<=lim,v) \\ _Charles R Greathouse IV_, Apr 16 2012

%o (PARI) select(istotient,vector(100,i,i)) \\ _Charles R Greathouse IV_, Dec 28 2012

%o (Haskell)

%o import Data.List.Ordered (insertSet)

%o a002202 n = a002202_list !! (n-1)

%o a002202_list = f [1..] (tail a002110_list) [] where

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

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

%o | otherwise = vs ++ f xs ps ws

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

%o -- _Reinhard Zumkeller_, Nov 22 2015

%Y Cf. A000010, A002180, A032446, A058277.

%Y Cf. A002110, A005277, A007614, A007617 (complement).

%Y Cf. A083533 (first differences), A264739.

%K nonn,nice

%O 1,2

%A _N. J. A. Sloane_

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 9 22:46 EDT 2020. Contains 335570 sequences. (Running on oeis4.)