%I #119 Oct 06 2023 10:57:41

%S 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,

%T 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,

%U 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

%N Cototient(n) := n - phi(n).

%C 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

%C Theorem (L. Redei): b^a(n) == b^n (mod n) for every integer b. - _Thomas Ordowski_ and _Robert Israel_, Mar 11 2016

%C 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

%H T. D. Noe, <a href="/A051953/b051953.txt">Table of n, a(n) for n = 1..10000</a>

%H J. Browkin and A. 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., 68 (1995), 55-58.

%H R. E. Jamison, <a href="http://dx.doi.org/10.1016/S0012-365X(01)00240-0">The Helly bound for singular sums</a>, Discrete Math., 249 (2002), 117-133.

%H Paul Pollack and Carl Pomerance, <a href="https://doi.org/10.1090/btran/10">Some problems of Erdős on the sum-of-divisors function</a>, Trans. Amer. Math. Soc. Ser. B 3 (2016), 1-26. For Richard Guy on his 99th birthday. May his sequence be unbounded.

%H Carl Pomerance and Hee-Sung Yang, <a href="https://doi.org/10.1090/S0025-5718-2013-02775-5">Variant of a theorem of Erdős on the sum-of-proper-divisors function</a>, Math. Comp. 83 (2014), 1903-1913.

%H N. J. A. Sloane, <a href="/A115004/a115004.txt">Families of Essentially Identical Sequences</a>, Mar 24 2021 (Includes this sequence)

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Cototient.html">Cototient</a>

%F a(n) = n - A000010(n).

%F Equals Mobius transform (A054525) of A001065. - _Gary W. Adamson_, Jul 11 2008

%F a(A006881(n)) = sopf(A006881(n)) - 1; a(A000040(n)) = 1. - _Wesley Ivan Hurt_, May 18 2013

%F G.f.: sum(n>=1, A000010(n)*x^(2*n)/(1-x^n) ). - _Mircea Merca_, Feb 23 2014

%F From _Ilya Gutkovskiy_, Apr 13 2017: (Start)

%F G.f.: -Sum_{k>=2} mu(k)*x^k/(1 - x^k)^2.

%F Dirichlet g.f.: zeta(s-1)*(1 - 1/zeta(s)). (End)

%F From _Antti Karttunen_, Sep 05 2018 & Apr 29 2022: (Start)

%F Dirichlet convolution square of A317846/A046644 gives this sequence + A063524.

%F a(n) = A003557(n) * A318305(n).

%F a(n) = A000010(n) - A083254(n).

%F a(n) = A318325(n) - A318326(n).

%F a(n) = Sum_{d|n} A062790(d) = Sum_{d|n, d<n} A007431(d)*(A000005(n/d)-1).

%F a(n) = A048675(A318834(n)) = A276085(A353564(n)). [These follow from the formula below]

%F a(n) = Sum_{d|n, d<n} A000010(d).

%F a(n) = A051612(n) - A001065(n).

%F (End)

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

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

%t Table[n - EulerPhi[n], {n, 1, 80}] (* _Carl Najafi_, Aug 16 2011 *)

%o (PARI) A051953(n) = n - eulerphi(n); \\ _Michael B. Porter_, Jan 28 2010

%o (Haskell)

%o a051953 n = n - a000010 n -- _Reinhard Zumkeller_, Jan 21 2014

%o (Python)

%o from sympy.ntheory import totient

%o print([i - totient(i) for i in range(1, 101)]) # _Indranil Ghosh_, Mar 17 2017

%Y Cf. A000010, A001065 (inverse Möbius transform), A005278, A001274, A083254, A098006, A049586, A051612, A053579, A054525, A062790 (Möbius transform), A063985 (partial sums), A063986, A290087.

%Y Records: A065385, A065386.

%Y Number of zeros in the n-th row of triangle A054521. - _Omar E. Pol_, May 13 2016

%Y Cf. A063740 (number of k such that cototient(k) = n). - _M. F. Hasler_, Jan 11 2018

%K nonn,easy,nice

%O 1,4

%A _Labos Elemer_, Dec 21 1999