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

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

Author

Labos Elemer, Dec 21 1999

Keywords

• nonn
• easy
• nice

Comments

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

Examples

			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}.
		

Links

• 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

Crossrefs

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

Programs

Haskell

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

Maple

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

Mathematica

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

PARI

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

Python

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

Formula

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)