A053579 -id:A053579 - cp's OEIS frontend

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

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)

A058764 Smallest number x such that cototient(x) = 2^n.

Original entry on oeis.org

2, 4, 6, 12, 24, 48, 96, 192, 384, 768, 1536, 3072, 6144, 12288, 24576, 49152, 98304, 196608, 393216, 786432, 1572864, 3145728, 6291456, 12582912, 25165824, 50331648, 100663296, 201326592, 402653184, 805306368, 1610612736, 3221225472

Offset: 0

Labos Elemer, Jan 02 2001

Since the cototient of 3*2^n is 2^(n+1), upper bounds are given by A007283(n-1). - R. J. Mathar, Oct 13 2008

A058764(n+1) is the number of different walks with n steps in the graph G = ({1,2,3,4}, {{1,2}, {2,3}, {3,4}}). - Aldo González Lorenzo, Feb 27 2012

			a(5) = 48, cototient(48) = 48-Phi(48) = 48-16 = 32. For n>2, a(n) = 3*2^(n-1); largest solutions = 2^(n+1). Prime factors of solutions: 2 and Mersenne-primes were found only.

Jud McCranie, Table of n, a(n) for n = 0..46

Cf. A051953, A053579, A053650.
Cf. A042950. - R. J. Mathar, Jan 30 2009
Cf. A007283.

Function[s, Flatten@ Map[First@ Position[s, #] &, 2^Range[0, Floor@ Log2@ Max@ s]]]@ Table[n - EulerPhi@ n, {n, 10^7}] (* Michael De Vlieger, Dec 17 2016 *)

a(n) = {x = 1; while(x - eulerphi(x) != 2^n, x++); x;} \\ Michel Marcus, Dec 11 2013

a(n) = if(n>1,3,4)<<(n-1) \\ M. F. Hasler, Nov 10 2016

a(n) = min { x | A051953(x) = 2^n }.

a(n) = (if n>1 then 3 else 4)*2^(n-1) = A007283(n-1) for n>1. (Conjectured.) - M. F. Hasler, Nov 10 2016

Edited by M. F. Hasler, Nov 10 2016

a(27)-a(31) from Jud McCranie, Jul 13 2017

A053159 Numbers n such that n+cototient(n) is a power of 2.

Original entry on oeis.org

1, 3, 7, 10, 20, 31, 40, 80, 127, 160, 320, 322, 640, 644, 1280, 1288, 2560, 2576, 5120, 5152, 8191, 10240, 10304, 20480, 20608, 40960, 41216, 81920, 82432, 131071, 163840, 164864, 327680, 329728, 333634, 524287, 655360, 659456, 667268, 1310720, 1318912

Offset: 1

Labos Elemer, Feb 29 2000

nonn

See especially A053579 and also A053576, A053577.

			Mersenne primes are a proper subset of this sequence: A(M)=2M-M+1=M+1=2^p

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

Cf. A000043, A000668, A001348.

print(1); for(n=3, 10^9, if(omega(2*n-eulerphi(n))==1, print(n))) /* Donovan Johnson, Apr 04 2013 */

a(n)+A051953(n) = 2*a(n)-A000010(n) = 2^w for some w.

More terms from Reiner Martin, Dec 24 2001

A053162 Nonprimes n such that n+cototient(n) is a power of 2.

Original entry on oeis.org

1, 10, 20, 40, 80, 160, 320, 322, 640, 644, 1280, 1288, 2560, 2576, 5120, 5152, 10240, 10304, 20480, 20608, 40960, 41216, 81920, 82432, 163840, 164864, 327680, 329728, 333634, 655360, 659456, 667268, 1310720, 1318912, 1334536, 1378114, 2621440

Offset: 1

Labos Elemer, Feb 29 2000

nonn

See especially A053579 and also A053576, A053577.

			Mersenne primes were deleted from set of numbers with similar property. An infinite subset here is m(r)=5*2^r, since Phi[m(r)]=2^(r+1) and a(m(r))=5*2^(r+1)-2^(r+1)=2^(r+3). A different subset includes m = 322,644,1288,.. = Set of {(2^s)*7*23} generating 2^(s+8)=2m-Phi(m) powers of 2.

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

Cf. A000043, A000668, A001348, A053159.

for(n=1, 2621440, if(isprime(n)==0, if(omega((2*n-eulerphi(n))*2)==1, print1(n ", ")))) \\ Donovan Johnson, Jan 09 2014

a(n)+A051953(n) = 2*a(n)-A000010(n) = 2^w for some w and a(n).

More terms from Olaf Voß, Feb 25 2008

A053163 n+cototient(n) produces these powers of 2 in order of magnitude.

Original entry on oeis.org

1, 4, 8, 16, 32, 32, 64, 128, 128, 256, 512, 512, 1024, 1024, 2048, 2048, 4096, 4096, 8192, 8192, 8192, 16384, 16384, 32768, 32768, 65536, 65536, 131072, 131072, 131072, 262144, 262144, 524288, 524288, 524288, 524288, 1048576, 1048576, 1048576, 2097152

Offset: 1

Labos Elemer, Feb 29 2000

See especially A053579 and also A053576, A053577.

			1+Mersenne primes powers of 2 are here, 2^p for special primes. Also because of other (infinite) subsequences, all 2-powers from 2^6 occurs at least twice.

Donovan Johnson, Table of n, a(n) for n = 1..100
Index to divisibility sequences

Cf. A000043, A000668, A001348.

Join[{1}, Reap[For[n=3, n<10^7, n++, If[PrimeNu[k = 2*n - EulerPhi[n]] == 1, Print[k]; Sow[k]]]][[2, 1]]] (* Jean-François Alcover, Jun 30 2015, after Donovan Johnson *)

print(1); for(n=3, 10^9, k=2*n-eulerphi(n); if(omega(k)==1, print(k))) /* Donovan Johnson, Apr 04 2013 */

a(n) = 2^w = m+A051953(m) = 2*m-A000010(m) for some m.

More terms from Olaf Voß, Feb 25 2008

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Formula

A058764 Smallest number x such that cototient(x) = 2^n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions

A053159 Numbers n such that n+cototient(n) is a power of 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A053162 Nonprimes n such that n+cototient(n) is a power of 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A053163 n+cototient(n) produces these powers of 2 in order of magnitude.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions