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,1

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

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.

Formula

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

Example

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

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 *)

Prog

(PARI) is(n)=!istotient(n) \\ Charles R Greathouse IV, Dec 28 2013
(Haskell)
import Data.List.Ordered (minus)
a007617 n = a007617_list !! (n-1)
a007617_list = [1..] `minus` a002202_list
-- Reinhard Zumkeller, Nov 22 2015

Crossrefs

Numbers not in A000010.

Complement of A002202.

Cf. A005277, A180639.

Cf. A083534 (first differences), A264739.

Sequence in context: A196546 A371179 A231773 * A065878 A186383 A284055

Adjacent sequences: A007614 A007615 A007616 * A007618 A007619 A007620

Keyword

nonn

Author

Walter Nissen

Status

approved