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

A065386 Successive record values of the cototient function (A051953).

Original entry on oeis.org

0, 1, 2, 4, 6, 8, 12, 16, 22, 24, 30, 32, 36, 44, 46, 48, 54, 60, 66, 70, 72, 78, 88, 90, 92, 94, 96, 110, 120, 132, 138, 140, 162, 176, 180, 184, 198, 210, 220, 250, 264, 270, 294, 324, 330, 342, 352, 360, 382, 396, 402, 426, 440, 486, 500, 514, 522, 528, 550, 588

Offset: 1

Labos Elemer, Nov 05 2001

nonn

			a(8)=22 because for m = 1...29 the cototient values are all smaller than cototient(30)=22, where 30=A065385(8) and 22 is the 8th term in the sequence of such local records.

Harry J. Smith, Table of n, a(n) for n = 1..1000

Cototient(A065385(n)).
A006093 gives similar records for the totient function. A002093, A002182, A015702, A005250 are analogous sequences for other functions.
a(n) = A051953(A065385(n)).
Cf. A051953, A065386, A000010.

a=0; s=0; Do[s = n-EulerPhi[n]; If[s>a, a=s; Print[s]], {n, 1, 10000}]
(* Second program: *)
With[{s = Array[# - EulerPhi@ # &, 10^3]}, Union@ FoldList[Max, s]] (* Michael De Vlieger, Nov 03 2017 *)

r=-1; for(n=1,1000,d=n-eulerphi(n); if(r

{ n=0; x=-1; for (m=1, 10^9, c=m - eulerphi(m); if (c > x, x=c; write("b065386.txt", n++, " ", c); if (n==1000, return)) ) } \\ Harry J. Smith, Oct 17 2009

A303753 Ordinal transform of cototient (A051953).

Original entry on oeis.org

1, 1, 2, 1, 3, 1, 4, 2, 1, 1, 5, 1, 6, 2, 1, 3, 7, 1, 8, 2, 1, 3, 9, 1, 1, 1, 2, 2, 10, 1, 11, 3, 1, 1, 1, 1, 12, 1, 1, 2, 13, 1, 14, 3, 1, 4, 15, 1, 2, 2, 1, 1, 16, 1, 2, 2, 2, 3, 17, 1, 18, 3, 1, 4, 1, 1, 19, 2, 1, 2, 20, 1, 21, 1, 1, 1, 2, 1, 22, 2, 2, 1, 23, 1, 3, 2, 1, 3, 24, 1, 2, 4, 1, 5, 1, 1, 25, 1, 1, 2, 26, 1, 27, 2, 1

Offset: 1

Antti Karttunen, Apr 30 2018

nonn

Number of values of k, 1 <= k <= n, with A051953(k) = A051953(n).

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

Cf. A051953, A065385 (gives a subset of the positions of ones).

Cf. also A081373, A303754.

b:= proc() 0 end:
a:= proc(n) option remember; local t;
      t:= numtheory[phi](n)-n; b(t):= b(t)+1
    end:
seq(a(n), n=1..120);  # Alois P. Heinz, Apr 30 2018

b[_] = 0;
a[n_] := a[n] = With[{t = EulerPhi[n]-n}, b[t] = b[t]+1];
Array[a, 120] (* Jean-François Alcover, Dec 19 2021, after Alois P. Heinz *)

up_to = 65537;
ordinal_transform(invec) = { my(om = Map(), outvec = vector(length(invec)), pt); for(i=1, length(invec), if(mapisdefined(om,invec[i]), pt = mapget(om, invec[i]), pt = 0); outvec[i] = (1+pt); mapput(om,invec[i],(1+pt))); outvec; };
A051953(n) = (n - eulerphi(n));
v303753 = ordinal_transform(vector(up_to,n,A051953(n)));
A303753(n) = v303753[n];

For all n >= 1, a(A000040(n)) = n.

A076249 Distance between maxima of the cototient function.

Original entry on oeis.org

1, 2, 2, 4, 2, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 12, 6, 6, 6, 6, 6, 6, 6, 6, 18, 12, 18, 6, 6, 30, 12, 12, 6, 24, 6, 30, 30, 18, 12, 30, 30, 12, 18, 24, 6, 30, 6, 24, 30, 30, 30, 30, 24, 6, 30, 30, 30, 30, 60, 24, 6, 30, 30, 30, 30, 60, 30, 30, 60, 30, 60, 60, 30, 18, 12, 30, 60

Offset: 0

Olivier Gérard

nonn

First differences of A065385, indices of records in A051953. - Michael De Vlieger, Oct 25 2023

Michael De Vlieger, Table of n, a(n) for n = 0..1386
Michael De Vlieger, Prime decomposition of a(n), n = 1..1386.

Cf. A051953, A065385, A076250.

j = 1; r = 0; Reap[Do[If[# > r, Sow[(i - j)]; Set[{j, r}, {i, #}]] &[i - EulerPhi[i]], {i, 2000}]][[-1, 1]] (* Michael De Vlieger, Oct 25 2023 *)

A076250 Distance between maxima of the cototient function, divided by 6, starting at n=5.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 3, 2, 3, 1, 1, 5, 2, 2, 1, 4, 1, 5, 5, 3, 2, 5, 5, 2, 3, 4, 1, 5, 1, 4, 5, 5, 5, 5, 4, 1, 5, 5, 5, 5, 10, 4, 1, 5, 5, 5, 5, 10, 5, 5, 10, 5, 10, 10, 5, 3, 2, 5, 10, 5, 10, 3, 2, 5, 15, 5, 5, 3, 2, 5, 10, 5, 10, 5, 5, 20, 5, 5, 5, 30, 5, 20

Offset: 5

Olivier Gérard

nonn

Michael De Vlieger, Table of n, a(n) for n = 5..1024

Cf. A051953, A065385, A076249.

s = Array[# - EulerPhi[#] &, 2^12]; 1/6*Differences[Map[FirstPosition[s, #][[1]] &, Union@ FoldList[Max, s] ][[6 ;; -1]] ] (* Michael De Vlieger, Oct 25 2023 *)

A144761 Integers n such that Phi(2, a(n)) = A144741(a(n)) > Phi(2, k) for 0 < k < a(n).

Original entry on oeis.org

4, 6, 10, 12, 18, 24, 30, 36, 42, 54, 60, 78, 84, 90, 120, 150, 168, 180, 210, 240, 270, 300, 330, 390, 420, 510, 546, 570, 630, 780, 840, 990, 1050, 1170, 1260, 1320, 1470, 1650, 1680, 1890, 2100, 2310, 2730, 3150, 3360, 3570, 3990, 4290, 4620, 4830

Offset: 1

Reikku Kulon, Sep 20 2008

Subset of A065385.

The first three terms are semiprimes and the number of factors gradually increases. All except four and ten are multiples of six.

Cf. A051953, A065385, A144741, A144742

A328549 1, together with the numbers that are simultaneously superior highly composite (A002201), colossally abundant (A004490), deeply composite (A095848), and miserable average divisor numbers (A263572).

Original entry on oeis.org

1, 2, 6, 12, 60, 120, 360, 2520, 5040, 55440, 720720, 1441440

Offset: 1

N. J. A. Sloane, Oct 20 2019

Presumably there are no further terms.
From Hal M. Switkay, Nov 04 2019: (Start)
1. a(n+1) is the product of the first n terms of A328852.
2. This sequence is most rapidly constructed as the intersection of A095849 and A224078. It is designed to list all potential solutions to a question. Let n be a natural number, k real <= 0, e real > 0. Let P(n,k,e) state: on the domain of natural numbers, sigma_k(x)/x^e reaches a maximum at x = n. This implies Q(n,k): sigma_k(n) > sigma_k(m) for m < n a natural number. We ask: for which natural numbers n is it true for all real k <= 0 that there is a real e > 0 such that P(n,k,e)?
If any such n exist, they must belong to the present sequence. A095849 consists of all natural numbers n such that for all real k <= 0, Q(n,k) holds. A224078 consists of all natural numbers n such that for some real e0 and e1 both > 0, P(n,0,e0) and P(n,-1,e1) hold. It would be interesting to see the list of n for which there is an e2 > 0 such that P(n,-2,e2) holds.
Conjecture: the solutions to this problem, if any, form an initial sequence of the present sequence. (End)
Every term of this sequence is also in A065385: a record for the cototient function. - Hal M. Switkay, Feb 27 2021
Every term of this sequence, except the first, is also in A210594: factor-dense numbers. - Hal M. Switkay, Mar 29 2021

Hal M. Switkay, Email to N. J. A. Sloane, Oct 20 2019

1 together with the intersection of A002201, A004490, A095848, A263572.

Cf. A095849, A224078, A328852, A210594.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Formula

A065386 Successive record values of the cototient function (A051953).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

A303753 Ordinal transform of cototient (A051953).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A076249 Distance between maxima of the cototient function.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A076250 Distance between maxima of the cototient function, divided by 6, starting at n=5.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

A144761 Integers n such that Phi(2, a(n)) = A144741(a(n)) > Phi(2, k) for 0 < k < a(n).

Views

Author

Keywords

Comments

Crossrefs

A328549 1, together with the numbers that are simultaneously superior highly composite (A002201), colossally abundant (A004490), deeply composite (A095848), and miserable average divisor numbers (A263572).

Views

Author

Keywords

Comments

References

Crossrefs