A049586 -id:A049586 - 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)

A058515 GCD of totients of consecutive integers.

Original entry on oeis.org

1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 4, 6, 2, 8, 8, 2, 6, 2, 4, 2, 2, 2, 4, 4, 6, 6, 4, 4, 2, 2, 4, 4, 8, 12, 12, 18, 6, 8, 8, 4, 6, 2, 4, 2, 2, 2, 2, 2, 4, 8, 4, 2, 2, 8, 12, 4, 2, 2, 4, 30, 6, 4, 16, 4, 2, 2, 4, 4, 2, 2, 24, 36, 4, 4, 12, 12, 6, 2, 2, 2, 2, 2, 8, 2, 14, 8, 8, 8, 24, 4, 4, 2, 2, 8, 32, 6

Offset: 1

Labos Elemer, Dec 21 2000

			For n = 61, gcd(phi(62), phi(61)) = gcd(30, 60) = 30, so a(61) = 30.

Antti Karttunen, Table of n, a(n) for n = 1..10000

Cf. A000010, A049586, A060778, A066813, A083542.

Map[GCD @@ # &, Partition[EulerPhi@ Range@ 98, 2, 1]] (* Michael De Vlieger, Aug 22 2017 *)

a(n) = gcd(eulerphi(n), eulerphi(n+1)); \\ Michel Marcus, Dec 10 2013

a(n) = gcd(phi(n+1), phi(n)), where phi = A000010.

a(n) = A083542(n)/A066813(n). - Amiram Eldar, May 07 2025

Offset corrected to 1 by Michel Marcus, Dec 10 2013

A083548 Least common multiple of cototient values of consecutive integers.

Original entry on oeis.org

0, 1, 2, 2, 4, 4, 4, 12, 6, 6, 8, 8, 8, 56, 56, 8, 12, 12, 12, 36, 36, 12, 16, 80, 70, 126, 144, 16, 22, 22, 16, 208, 234, 198, 264, 24, 20, 60, 120, 24, 30, 30, 24, 168, 168, 24, 32, 224, 210, 570, 532, 28, 36, 180, 480, 672, 210, 30, 44, 44, 32, 864, 864, 544, 782, 46, 36

Offset: 1

Labos Elemer, May 22 2003

nonn

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000

Cf. A051953, A083538-A083555, A049586.

f[x_] := x-EulerPhi[x] Table[LCM[f[w+1], f[w]], {w, 1, b}]
LCM@@#&/@Partition[Table[n-EulerPhi[n],{n,70}],2,1] (* Harvey P. Dale, Feb 01 2015 *)

a(n)=lcm(n-eulerphi(n),n+1-eulerphi(n+1)) \\ Charles R Greathouse IV, Nov 16 2012

a(n) = lcm(A051953(n), A051953(n+1)).

A083549 Quotient if least common multiple (lcm) of cototient values of consecutive integers is divided by the greatest common divisor (gcd) of the same pair of consecutive numbers.

Original entry on oeis.org

0, 1, 2, 2, 4, 4, 4, 12, 2, 6, 8, 8, 8, 56, 56, 8, 12, 12, 12, 12, 12, 12, 16, 80, 70, 126, 144, 16, 22, 22, 16, 208, 234, 198, 264, 24, 20, 12, 40, 24, 30, 30, 24, 56, 56, 24, 32, 224, 210, 570, 532, 28, 36, 60, 480, 672, 70, 30, 44, 44, 32, 864, 864, 544, 782, 46, 36, 900

Offset: 1

Labos Elemer, May 22 2003

nonn

			n=33: cototient(33) = 33-20 = 13, cototient(34) = 34-16 = 18;
lcm(13,18) = 234, gcd(13,18) = 1, so a(34) = 234.

Michael De Vlieger, Table of n, a(n) for n = 1..10000

Cf. A051953, A083538, A083539, A083540, A083541, A083542, A083543, A083544, A083545, A083546, A083547, A083548, A083549, A083550, A083551, A083552, A083553, A083554, A083555, A049586.

f[x_] := x-EulerPhi[x]; Table[LCM[f[w+1], f[w]]/GCD[f[w+1], f[w]], {w, 69}]
(* Second program: *)
Map[Apply[LCM, #]/Apply[GCD, #] &@ Map[# - EulerPhi@ # &, #] &, Partition[Range[69], 2, 1]] (* Michael De Vlieger, Mar 17 2018 *)

a(n) = lcm(A051953(n), A051952(n+1))/gcd(A051953(n), A051952(n+1)) = lcm(cototient(n+1), cototient(n))/A049586(n).

A070017 Least numbers m such that GCD of two consecutive values of cototients, i.e., gcd(cototient(m+1), cototient(m)) equals 2n - 1.

Original entry on oeis.org

2, 9, 38, 392, 135, 120, 362, 116, 745, 1183, 294, 528, 1395, 428, 1378, 2602, 1185, 203, 2313, 3042, 1966, 3549, 1431, 551, 7838, 4076, 473, 2635, 903, 2044, 13178, 942, 6819, 12418, 1188, 2264, 3282, 1775, 1517, 2127, 24380, 2884, 2035, 11481

Offset: 1

Labos Elemer and Benoit Cloitre, Apr 12 2002

nonn

			For n=104: 2n - 1 = 207, a(104) = 235148 because A049586(235148) = 207 and it is the smallest such number. Remark that Count[t=Table[f[w],{w,1,100000}],1]=83132. This suggests that majority of values in A049586 equals one.

Cf. A051953.

With[{s = Array[# - EulerPhi@ # &, 10^5]}, Function[t, MapAt[# + 1 &, TakeWhile[#, # > 0 &], 1] &@ Table[First[FirstPosition[t, n] /. k_ /; MissingQ@ k -> {0}], {n, 1, Max@ t, 2}]]@ Map[GCD @@ # &@ # &, Partition[s, 2, 1]]] (* Michael De Vlieger, Jul 30 2017 *)

a(n) = min{x; A049586(x) = 2n - 1}.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Formula

A058515 GCD of totients of consecutive integers.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A083548 Least common multiple of cototient values of consecutive integers.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A083549 Quotient if least common multiple (lcm) of cototient values of consecutive integers is divided by the greatest common divisor (gcd) of the same pair of consecutive numbers.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A070017 Least numbers m such that GCD of two consecutive values of cototients, i.e., gcd(cototient(m+1), cototient(m)) equals 2n - 1.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Formula