cp's OEIS Frontend

A007617 Values not in range of Euler phi function.

%I A007617 #75 Nov 17 2023 11:49:47
%S A007617 3,5,7,9,11,13,14,15,17,19,21,23,25,26,27,29,31,33,34,35,37,38,39,41,
%T A007617 43,45,47,49,50,51,53,55,57,59,61,62,63,65,67,68,69,71,73,74,75,76,77,
%U A007617 79,81,83,85,86,87,89,90,91,93,94,95,97,98,99,101,103,105,107
%N A007617 Values not in range of Euler phi function.
%C A007617 Nontotient numbers.
%C A007617 All odd numbers > 2 are in the sequence.
%C A007617 The even numbers of the sequence are in A005277.
%C A007617 The asymptotic density of this sequence is 1. - _Amiram Eldar_, Mar 26 2021
%D A007617 Richard K. Guy, Unsolved Problems in Number Theory, 3rd edition, Springer, 2004, section B36, page 138-142.
%H A007617 Amiram Eldar, <a href="/A007617/b007617.txt">Table of n, a(n) for n = 1..10000</a> (terms 1..1000 from T. D. Noe)
%H A007617 Jerzy Browkin and Andrzej Schinzel, <a href="http://matwbn.icm.edu.pl/ksiazki/cm/cm68/cm6817.pdf">On integers not of the form n-phi(n)</a>, Colloq. Math., Vol. 58 (1995), pp. 55-58.
%H A007617 Paul Erdős and R. R. Hall, <a href="http://dx.doi.org/10.1112/S0025579300006100">Distinct values of Euler's phi-function</a>, Mathematika, Vol. 23 (1976), pp. 1-3.
%H A007617 Kevin Ford, <a href="http://dx.doi.org/10.1023/A:1009761909132">The distribution of totients</a>. Paul Erdős (1913-1996). Ramanujan J., Vol. 2 (1998) pp. 67-151; <a href="http://arxiv.org/abs/1104.3264">arXiv preprint</a>, arXiv:1104.3264 [math.NT], 2011-2013.
%H A007617 Kevin Ford, <a href="http://dx.doi.org/10.1090/S1079-6762-98-00043-2">The distribution of totients</a>, Electron. Res. Announc. Amer. Math. Soc., Vol. 4 (1998) pp. 27-34.
%H A007617 Kevin Ford, <a href="http://www.jstor.org/stable/121103">The number of solutions of phi(x)=m</a>, Ann. of Math.(2), Vol. 150, No. 1 (1999), pp. 283-311.
%H A007617 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, Vol. 49, No. 3 (1988), pp. 263-275.
%H A007617 Passawan Noppakaew and Prapanpong Pongsriiam, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL26/Pongsriiam/pong43.html">Product of Some Polynomials and Arithmetic Functions</a>, J. Int. Seq. (2023) Vol. 26, Art. 23.9.1.
%H A007617 Maxim Rytin, <a href="http://library.wolfram.com/infocenter/MathSource/696/">Finding the Inverse of Euler Totient Function</a>, Wolfram Library Archive, 1999.
%H A007617 Zhang Ming-Zhi, <a href="http://dx.doi.org/10.1006/jnth.1993.1014">On nontotients</a>, J. Number Theory, Vol. 43, No. 2 (1993), pp. 168-173.
%F A007617 A264739(a(n)) = 0. - _Reinhard Zumkeller_, Nov 26 2015
%e A007617 There are no solutions to phi(m)=14, so 14 is a member of the sequence.
%p A007617 A007617 := n -> if invphi(n)=[] then n fi: seq(A007617(i),i=1..107); # _Peter Luschny_, Jun 26 2011
%t A007617 inversePhi[m_?OddQ] = {}; inversePhi[1] = {1, 2}; inversePhi[m_] := Module[{p, nmax, n, nn}, p = Select[Divisors[m] + 1, PrimeQ]; nmax = m*Times @@ (p/(p - 1)); n = m; nn = {}; While[n <= nmax, If[EulerPhi[n] == m, AppendTo[nn, n]]; n++]; nn]; Select[Range[107], inversePhi[#] == {} &] (* _Jean-François Alcover_, Jan 03 2012 *)
%t A007617 Select[Range[107], invphi[#] == {}&] (* _Jean-François Alcover_, Mar 19 2019, using Maxim Rytin's much faster 'invphi' program *)
%o A007617 (PARI) is(n)=!istotient(n) \\ _Charles R Greathouse IV_, Dec 28 2013
%o A007617 (Haskell)
%o A007617 import Data.List.Ordered (minus)
%o A007617 a007617 n = a007617_list !! (n-1)
%o A007617 a007617_list = [1..] `minus` a002202_list
%o A007617 -- _Reinhard Zumkeller_, Nov 22 2015
%Y A007617 Numbers not in A000010.
%Y A007617 Complement of A002202.
%Y A007617 Cf. A005277, A180639.
%Y A007617 Cf. A083534 (first differences), A264739.
%K A007617 nonn
%O A007617 1,1
%A A007617 _Walter Nissen_