A005278 -id:A005278 - cp's OEIS frontend

A083536 First differences of noncototients A005278.

16, 8, 16, 2, 6, 28, 14, 16, 6, 8, 4, 12, 8, 16, 2, 14, 16, 4, 12, 4, 10, 12, 16, 6, 2, 6, 16, 2, 6, 12, 16, 14, 4, 2, 16, 4, 6, 14, 8, 10, 8, 24, 30, 4, 4, 8, 8, 28, 2, 12, 2, 2, 10, 8, 8, 4, 14, 4, 12, 30, 8, 16, 2, 14, 14, 6, 2, 10, 8, 16, 2, 6, 2, 14, 26, 6, 8, 8, 14, 10, 16, 8, 8, 22, 2, 28

Offset: 1

Labos Elemer, May 20 2003

nonn

			Missing terms from A051953 are 10,26,34,50,.. so their difference sequence starts with 16,8,16,...

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A051953, A005278.

t0[x_] := Table[j, {j, 1, x}] t=Table[w-EulerPhi[w], {w, 1, 10000}]; u=Union[%]; Delete[u-RotateRight[u], 1]; c=Complement[t0[10000], u]; Delete[c-RotateRight[c], 1];

a(n) = A005278(n+1) - A005278(n).

a(84)-a(85) corrected by David Ng, (an error that was noticed by Doug Phillips), Oct 31 2016

a(86) corrected and name simplified by Omar E. Pol, Nov 04 2016

A053474 Cototients of non-cototient numbers: A051953(A005278(n)).

Original entry on oeis.org

6, 14, 18, 30, 28, 30, 44, 60, 60, 62, 82, 68, 74, 94, 106, 88, 126, 102, 104, 110, 150, 120, 124, 164, 158, 136, 138, 178, 148, 150, 190, 164, 212, 176, 174, 182, 246, 252, 194, 198, 204, 208, 220, 234, 286, 318, 242, 322, 302, 328

Offset: 1

Labos Elemer, Jan 14 2000

nonn

The iteration-graph (rooted tree) of A051953 has initial vertices given by A005278. Sequence gives immediate successors of initial terms. The iteration ends at 0 fixed point.

			30, 60, 150 and 164 occur twice in the terms shown. These numbers occur in A051953, but their arguments do not: 50, 58 or 100, 116 or 222, 298 or 260, 326 are non-cototients, terms of A005278.

Michel Marcus, Table of n, a(n) for n = 1..10000

Cf. A005278, A051953.

A333101 Numbers k such that both k and k + 2 are noncototients (A005278).

Original entry on oeis.org

50, 170, 266, 290, 344, 518, 532, 534, 650, 686, 722, 730, 872, 962, 1036, 1158, 1166, 1332, 1394, 1462, 1464, 1586, 1634, 1682, 1804, 1864, 1922, 1946, 1970, 2034, 2072, 2074, 2116, 2134, 2262, 2314, 2316, 2318, 2330, 2420, 2534, 2598, 2666, 2668, 2772, 2822

Offset: 1

Amiram Eldar, Mar 07 2020

nonn

			50 is a term since both 50 and 52 are noncototients.

Eric Weisstein's World of Mathematics, Noncototient.
Wikipedia, Noncototient.

Cf. A005278, A072296, A231964, A306952, A333100.

nmax = 3000; cototientQ[n_?EvenQ] := (x = n; While[test = x - EulerPhi[x] == n ; Not[test || x > 2*nmax], x++]; test); cototientQ[n_?OddQ] = True; nonc = Select[Range[nmax], !cototientQ[#]&]; nonc[[Flatten[Position[Differences[nonc], 2]]]] (* after Jean-François Alcover at A005278 *)

A126887 a(n) = A005278(n)/2.

Original entry on oeis.org

5, 13, 17, 25, 26, 29, 43, 50, 58, 61, 65, 67, 73, 77, 85, 86, 93, 101, 103, 109, 111, 116, 122, 130, 133, 134, 137, 145, 146, 149, 155, 163, 170, 172, 173, 181, 183, 186, 193, 197, 202, 206, 218, 233, 235, 237, 241, 245, 259, 260, 266, 267, 268, 273, 277, 281

Offset: 1

Artur Jasinski, Dec 30 2006

nonn

Cf. A005278.

More terms from Amiram Eldar, Sep 05 2019

A051953 Cototient(n) := n - phi(n).

Original entry on oeis.org

0, 1, 1, 2, 1, 4, 1, 4, 3, 6, 1, 8, 1, 8, 7, 8, 1, 12, 1, 12, 9, 12, 1, 16, 5, 14, 9, 16, 1, 22, 1, 16, 13, 18, 11, 24, 1, 20, 15, 24, 1, 30, 1, 24, 21, 24, 1, 32, 7, 30, 19, 28, 1, 36, 15, 32, 21, 30, 1, 44, 1, 32, 27, 32, 17, 46, 1, 36, 25, 46, 1, 48, 1, 38, 35, 40, 17, 54, 1, 48, 27

Offset: 1

Labos Elemer, Dec 21 1999

Unlike totients, cototient(n+1) = cototient(n) never holds -- except 2-phi(2) = 3 - phi(3) = 1 -- because cototient(n) is congruent to n modulo 2. - Labos Elemer, Aug 08 2001
Theorem (L. Redei): b^a(n) == b^n (mod n) for every integer b. - Thomas Ordowski and Robert Israel, Mar 11 2016
Let S be the sum of the cototients of the divisors of n (A001065). S < n iff n is deficient, S = n iff n is perfect, and S > n iff n is abundant. - Ivan N. Ianakiev, Oct 06 2023

			n = 12, phi(12) = 4 = |{1, 5, 7, 11}|, a(12) = 12 - phi(12) = 8, numbers not exceeding 12 and not coprime to 12: {2, 3, 4, 6, 8, 9, 10, 12}.

T. D. Noe, Table of n, a(n) for n = 1..10000
J. Browkin and A. Schinzel, On integers not of the form n-phi(n), Colloq. Math., 68 (1995), 55-58.
R. E. Jamison, The Helly bound for singular sums, Discrete Math., 249 (2002), 117-133.
Paul Pollack and Carl Pomerance, Some problems of Erdős on the sum-of-divisors function, Trans. Amer. Math. Soc. Ser. B 3 (2016), 1-26. For Richard Guy on his 99th birthday. May his sequence be unbounded.
Carl Pomerance and Hee-Sung Yang, Variant of a theorem of Erdős on the sum-of-proper-divisors function, Math. Comp. 83 (2014), 1903-1913.
N. J. A. Sloane, Families of Essentially Identical Sequences, Mar 24 2021 (Includes this sequence)
Eric Weisstein's World of Mathematics, Cototient

Cf. A000010, A001065 (inverse Möbius transform), A005278, A001274, A083254, A098006, A049586, A051612, A053579, A054525, A062790 (Möbius transform), A063985 (partial sums), A063986, A290087.
Records: A065385, A065386.
Number of zeros in the n-th row of triangle A054521. - Omar E. Pol, May 13 2016
Cf. A063740 (number of k such that cototient(k) = n). - M. F. Hasler, Jan 11 2018

a051953 n = n - a000010 n  -- Reinhard Zumkeller, Jan 21 2014

with(numtheory); A051953 := n->n-phi(n);

Table[n - EulerPhi[n], {n, 1, 80}] (* Carl Najafi, Aug 16 2011 *)

A051953(n) = n - eulerphi(n); \\ Michael B. Porter, Jan 28 2010

from sympy.ntheory import totient
print([i - totient(i) for i in range(1, 101)]) # Indranil Ghosh, Mar 17 2017

a(n) = n - A000010(n).
Equals Mobius transform (A054525) of A001065. - Gary W. Adamson, Jul 11 2008
a(A006881(n)) = sopf(A006881(n)) - 1; a(A000040(n)) = 1. - Wesley Ivan Hurt, May 18 2013
G.f.: sum(n>=1, A000010(n)*x^(2*n)/(1-x^n) ). - Mircea Merca, Feb 23 2014
From Ilya Gutkovskiy, Apr 13 2017: (Start)
G.f.: -Sum_{k>=2} mu(k)*x^k/(1 - x^k)^2.
Dirichlet g.f.: zeta(s-1)*(1 - 1/zeta(s)). (End)
From Antti Karttunen, Sep 05 2018 & Apr 29 2022: (Start)
Dirichlet convolution square of A317846/A046644 gives this sequence + A063524.
a(n) = A003557(n) * A318305(n).
a(n) = A000010(n) - A083254(n).
a(n) = A318325(n) - A318326(n).
a(n) = Sum_{d|n} A062790(d) = Sum_{d|n, dA007431(d)*(A000005(n/d)-1).
a(n) = A048675(A318834(n)) = A276085(A353564(n)). [These follow from the formula below]
a(n) = Sum_{d|n, dA000010(d).
a(n) = A051612(n) - A001065(n).
(End)

A063740 Number of integers k such that cototient(k) = n.

Original entry on oeis.org

1, 1, 2, 1, 1, 2, 3, 2, 0, 2, 3, 2, 1, 2, 3, 3, 1, 3, 1, 3, 1, 4, 4, 3, 0, 4, 1, 4, 3, 3, 4, 3, 0, 5, 2, 2, 1, 4, 1, 5, 1, 4, 2, 4, 2, 6, 5, 5, 0, 3, 0, 6, 2, 4, 2, 5, 0, 7, 4, 3, 1, 8, 4, 6, 1, 3, 1, 5, 2, 7, 3, 5, 1, 7, 1, 8, 1, 5, 2, 6, 1, 9, 2, 6, 0, 4, 2, 10, 2, 4, 2, 5, 2, 7, 5, 4, 1, 8, 0, 9, 1, 6, 1, 7

Offset: 2

Labos Elemer, Aug 13 2001

nonn

Note that a(0) is also well-defined to be 1 because the only solution to x - phi(x) = 0 is x = 1. - Jianing Song, Dec 25 2018

			Cototient(x) = 101 for x in {485, 1157, 1577, 1817, 2117, 2201, 2501, 2537, 10201}, with a(101) = 8 terms; e.g. 485 - phi(485) = 485 - 384 = 101. Cototient(x) = 102 only for x = 202 so a(102) = 1.

T. D. Noe, Table of n, a(n) for n = 2..10000

Cf. A000010, A051953, A063507.
Cf. A063748 (greatest solution to x-phi(x)=n).
Cf. A005278, A063741, A131825.

Table[Count[Range[n^2], k_ /; k - EulerPhi@ k == n], {n, 2, 105}] (* Michael De Vlieger, Mar 17 2017 *)

first(n)=my(v=vector(n),t); forcomposite(k=4,n^2, t=k-eulerphi(k); if(t<=n, v[t]++)); v[2..n] \\ Charles R Greathouse IV, Mar 17 2017

From Amiram Eldar, Apr 08 2023 (Start)
a(A005278(n)) = 0.
a(A131825(n)) = 1.
a(A063741(n)) = n. (End)

Name edited by Charles R Greathouse IV, Mar 17 2017

A050530 Numbers k such that k - phi(k) is prime.

Original entry on oeis.org

4, 9, 15, 25, 33, 35, 49, 51, 65, 77, 87, 91, 95, 119, 121, 123, 143, 161, 169, 177, 185, 209, 213, 215, 217, 221, 247, 255, 259, 287, 289, 303, 321, 329, 335, 341, 361, 371, 377, 395, 403, 407, 411, 427, 435, 437, 447, 455, 469, 473, 485, 511, 515, 527, 529

Offset: 1

Labos Elemer, Dec 29 1999

nonn

If k = p^2 is the square of a prime, then p^2 - phi(p^2) = p, so this sequence is infinite and generates all primes.

No prime p is a term of this sequence because A051953(p)=1. Other cases exist; e.g., k - phi(k) = 23 if k = 95, 119, 143, 529.

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A051953, A005278.

[n: n in [1..600] | IsPrime(n-EulerPhi(n))]; // Vincenzo Librandi, Dec 18 2015

Select[Range[600],PrimeQ[#-EulerPhi[#]]&] (* Harvey P. Dale, Jun 23 2013 *)

Numbers k such that A051953(k) is prime.

A063507 Least k such that k - phi(k) = n, or 0 if no such k exists.

Original entry on oeis.org

2, 4, 9, 6, 25, 10, 15, 12, 21, 0, 35, 18, 33, 26, 39, 24, 65, 34, 51, 38, 45, 30, 95, 36, 69, 0, 63, 52, 161, 42, 87, 48, 93, 0, 75, 54, 217, 74, 99, 76, 185, 82, 123, 60, 117, 66, 215, 72, 141, 0, 235, 0, 329, 78, 159, 98, 105, 0, 371, 84, 177, 122, 135, 96, 305, 90, 427

Offset: 1

Labos Elemer, Aug 09 2001

nonn

Inverse cototient (A051953) sets represented by their minimum, as in A002181 for totient function. Impossible values (A005278) are replaced by zero.

If a(n) > 0, then it appears that a(n) > 1.26n. - T. D. Noe, Dec 06 2006

			x = InvCototient[24] = {36, 40, 44, 46}; Phi[x] = Phi[{36, 40, 44, 46}] = {12, 16, 20, 22}; x-Phi[x] = {24, 24, 24, 24}, so a(24) = Min[InvCototient[24]]; a(10) = 0 because 10 is in A005278.

T. D. Noe, Table of n, a(n) for n=1..10000

Cf. A051953, A000010, A002181, A005277, A005278.
Cf. A063748 (greatest solution to x-phi(x)=n).
Cf. A063740 (number of k such that cototient(k) = n).

Table[SelectFirst[Range[n^2 + 1], # - EulerPhi[#] == n &] /. k_ /; ! IntegerQ@ k -> 0, {n, 67}] (* Michael De Vlieger, Jan 11 2018 *)

a(n)-A051953(a(n)) = n if possible and a(n)=0 if n belongs to A005278.

Edited by N. J. A. Sloane, Oct 25 2008 at the suggestion of R. J. Mathar

A063742 Cototients: numbers k such that x - phi(x) = k has at least one solution.

Original entry on oeis.org

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 27, 28, 29, 30, 31, 32, 33, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 51, 53, 54, 55, 56, 57, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78

Offset: 1

Labos Elemer, Aug 13 2001, corrected May 20 2003

nonn

Numbers in range of A051953, the cototients. Complement of non-cototients, A005278 with respect to natural numbers A000027.

			First missing numbers are: 10,26,34,50,52,... These missing values are collected in A005278.

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A000010, A005278, A051953, A083533, A083534, A083536.

Analogous to A002202.

Union[Table[w-EulerPhi[w], {w, 1, A}]] (* taken for sufficiently large A. *)

Edited by N. J. A. Sloane, Nov 17 2008 at the suggestion of R. J. Mathar

A058763 Integers which are neither totient nor cototient.

Original entry on oeis.org

26, 34, 50, 86, 122, 134, 146, 154, 170, 186, 202, 206, 218, 244, 266, 274, 290, 298, 326, 340, 362, 386, 394, 404, 412, 436, 470, 474, 482, 518, 532, 534, 554, 566, 596, 626, 634, 650, 666, 680, 686, 698, 706, 722, 724, 730, 746, 778, 794, 818, 834, 842

Offset: 1

Labos Elemer, Jan 02 2001

nonn

Donovan Johnson, Table of n, a(n) for n = 1..10000

Cf. A000010, A051953, A005277, A005278.

Intersection(A005277, A005278).

More terms from David Wasserman, May 14 2002

Offset corrected by Donovan Johnson, Sep 07 2013

cp's OEIS Frontend

A083536 First differences of noncototients A005278.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A053474 Cototients of non-cototient numbers: A051953(A005278(n)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A333101 Numbers k such that both k and k + 2 are noncototients (A005278).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

A126887 a(n) = A005278(n)/2.

Views

Author

Keywords

Crossrefs

Extensions

A051953 Cototient(n) := n - phi(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Formula

A063740 Number of integers k such that cototient(k) = n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A050530 Numbers k such that k - phi(k) is prime.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

Formula

A063507 Least k such that k - phi(k) = n, or 0 if no such k exists.

Views

Author

Keywords

Comments

Examples