cp's OEIS Frontend

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

%I A051953 #120 Feb 16 2025 08:32:41
%S A051953 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 A051953 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 A051953 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 A051953 Cototient(n) := n - phi(n).
%C A051953 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 A051953 Theorem (L. Redei): b^a(n) == b^n (mod n) for every integer b. - _Thomas Ordowski_ and _Robert Israel_, Mar 11 2016
%C A051953 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 A051953 T. D. Noe, <a href="/A051953/b051953.txt">Table of n, a(n) for n = 1..10000</a>
%H A051953 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 A051953 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 A051953 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 A051953 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 A051953 N. J. A. Sloane, <a href="/A115004/a115004.txt">Families of Essentially Identical Sequences</a>, Mar 24 2021 (Includes this sequence)
%H A051953 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Cototient.html">Cototient</a>
%F A051953 a(n) = n - A000010(n).
%F A051953 Equals Mobius transform (A054525) of A001065. - _Gary W. Adamson_, Jul 11 2008
%F A051953 a(A006881(n)) = sopf(A006881(n)) - 1; a(A000040(n)) = 1. - _Wesley Ivan Hurt_, May 18 2013
%F A051953 G.f.: sum(n>=1, A000010(n)*x^(2*n)/(1-x^n) ). - _Mircea Merca_, Feb 23 2014
%F A051953 From _Ilya Gutkovskiy_, Apr 13 2017: (Start)
%F A051953 G.f.: -Sum_{k>=2} mu(k)*x^k/(1 - x^k)^2.
%F A051953 Dirichlet g.f.: zeta(s-1)*(1 - 1/zeta(s)). (End)
%F A051953 From _Antti Karttunen_, Sep 05 2018 & Apr 29 2022: (Start)
%F A051953 Dirichlet convolution square of A317846/A046644 gives this sequence + A063524.
%F A051953 a(n) = A003557(n) * A318305(n).
%F A051953 a(n) = A000010(n) - A083254(n).
%F A051953 a(n) = A318325(n) - A318326(n).
%F A051953 a(n) = Sum_{d|n} A062790(d) = Sum_{d|n, d<n} A007431(d)*(A000005(n/d)-1).
%F A051953 a(n) = A048675(A318834(n)) = A276085(A353564(n)). [These follow from the formula below]
%F A051953 a(n) = Sum_{d|n, d<n} A000010(d).
%F A051953 a(n) = A051612(n) - A001065(n).
%F A051953 (End)
%e A051953 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 A051953 with(numtheory); A051953 := n->n-phi(n);
%t A051953 Table[n - EulerPhi[n], {n, 1, 80}] (* _Carl Najafi_, Aug 16 2011 *)
%o A051953 (PARI) A051953(n) = n - eulerphi(n); \\ _Michael B. Porter_, Jan 28 2010
%o A051953 (Haskell)
%o A051953 a051953 n = n - a000010 n  -- _Reinhard Zumkeller_, Jan 21 2014
%o A051953 (Python)
%o A051953 from sympy.ntheory import totient
%o A051953 print([i - totient(i) for i in range(1, 101)]) # _Indranil Ghosh_, Mar 17 2017
%Y A051953 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 A051953 Records: A065385, A065386.
%Y A051953 Number of zeros in the n-th row of triangle A054521. - _Omar E. Pol_, May 13 2016
%Y A051953 Cf. A063740 (number of k such that cototient(k) = n). - _M. F. Hasler_, Jan 11 2018
%K A051953 nonn,easy,nice
%O A051953 1,4
%A A051953 _Labos Elemer_, Dec 21 1999