A007617 Values not in range of Euler phi function.

3, 5, 7, 9, 11, 13, 14, 15, 17, 19, 21, 23, 25, 26, 27, 29, 31, 33, 34, 35, 37, 38, 39, 41, 43, 45, 47, 49, 50, 51, 53, 55, 57, 59, 61, 62, 63, 65, 67, 68, 69, 71, 73, 74, 75, 76, 77, 79, 81, 83, 85, 86, 87, 89, 90, 91, 93, 94, 95, 97, 98, 99, 101, 103, 105, 107

Offset: 1

Author

Walter Nissen

Keywords

• nonn

Comments

Nontotient numbers.

All odd numbers > 2 are in the sequence.

The even numbers of the sequence are in A005277.

The asymptotic density of this sequence is 1. - Amiram Eldar, Mar 26 2021

Examples

			There are no solutions to phi(m)=14, so 14 is a member of the sequence.
		

References

• Richard K. Guy, Unsolved Problems in Number Theory, 3rd edition, Springer, 2004, section B36, page 138-142.

Links

• Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..1000 from T. D. Noe)
• Jerzy Browkin and Andrzej Schinzel, On integers not of the form n-phi(n), Colloq. Math., Vol. 58 (1995), pp. 55-58.
• Paul Erdős and R. R. Hall, Distinct values of Euler's phi-function, Mathematika, Vol. 23 (1976), pp. 1-3.
• Kevin Ford, The distribution of totients. Paul Erdős (1913-1996). Ramanujan J., Vol. 2 (1998) pp. 67-151; arXiv preprint, arXiv:1104.3264 [math.NT], 2011-2013.
• Kevin Ford, The distribution of totients, Electron. Res. Announc. Amer. Math. Soc., Vol. 4 (1998) pp. 27-34.
• Kevin Ford, The number of solutions of phi(x)=m, Ann. of Math.(2), Vol. 150, No. 1 (1999), pp. 283-311.
• Helmut Maier and Carl Pomerance, On the number of distinct values of Euler's phi-function, Acta Arithmetica, Vol. 49, No. 3 (1988), pp. 263-275.
• Passawan Noppakaew and Prapanpong Pongsriiam, Product of Some Polynomials and Arithmetic Functions, J. Int. Seq. (2023) Vol. 26, Art. 23.9.1.
• Maxim Rytin, Finding the Inverse of Euler Totient Function, Wolfram Library Archive, 1999.
• Zhang Ming-Zhi, On nontotients, J. Number Theory, Vol. 43, No. 2 (1993), pp. 168-173.

Crossrefs

Numbers not in A000010.

Complement of A002202.

Cf. A005277, A180639.

Cf. A083534 (first differences), A264739.

Programs

Haskell

import Data.List.Ordered (minus)
a007617 n = a007617_list !! (n-1)
a007617_list = [1..] `minus` a002202_list
-- Reinhard Zumkeller, Nov 22 2015

Maple

A007617 := n -> if invphi(n)=[] then n fi: seq(A007617(i),i=1..107); # Peter Luschny, Jun 26 2011

Mathematica

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 *)
Select[Range[107], invphi[#] == {}&] (* Jean-François Alcover, Mar 19 2019, using Maxim Rytin's much faster 'invphi' program *)

PARI

is(n)=!istotient(n) \\ Charles R Greathouse IV, Dec 28 2013

Formula

A264739(a(n)) = 0. - Reinhard Zumkeller, Nov 26 2015