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

A001494 Numbers k such that phi(k) = phi(k+2).

Original entry on oeis.org

4, 7, 8, 10, 26, 32, 70, 74, 122, 146, 308, 314, 386, 512, 554, 572, 626, 635, 728, 794, 842, 910, 914, 1015, 1082, 1226, 1322, 1330, 1346, 1466, 1514, 1608, 1754, 1994, 2132, 2170, 2186, 2306, 2402, 2426, 2474, 2590, 2642, 2695, 2762, 2906, 3242, 3314

Offset: 1

N. J. A. Sloane

If p and 2p-1 are odd primes then 2*(2p-1) is a solution of the equation. Other terms (7,8,32,70,...) are not of this form.
There are 506764111 terms under 10^12. - Jud McCranie, Feb 13 2012
If 2^(2^m) + 1 is a Fermat prime in A019434, so, m = 0, 1, 2, 3, 4, then k = 2^(2^m + 1) is a term; this subsequence consists of {4, 8, 32, 512, 131072} and, in this case, phi(k) = phi(k+2) = 2^(2^m). - Bernard Schott, Apr 22 2022

D. M. Burton, Elementary Number Theory, section 7-2.
R. K. Guy, Unsolved Problems Number Theory, Sect. B36.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Jud McCranie, Table of n, a(n) for n = 1..10000 (first 1000 terms from T. D. Noe)
Kevin Ford, Solutions of phi(n)=phi(n+k) and sigma(n)=sigma(n+k), arXiv:2002.12155 [math.NT], 2020.
M. F. Hasler, Table of n, a(n) for n = 1..17286. (Terms up to 10^7.)
V. L. Klee, Jr., Some remarks on Euler's totient function, Amer. Math. Monthly, 54 (1947), 332.
Leo Moser, Some equations involving Euler's totient function, Amer. Math. Monthly, 56 (1949), 22-23.

Cf. A000010, A001274, A007015, A179186, A179187, A179188, A179189, A179202, A217139.

import Data.List (elemIndices)
a001494 n = a001494_list !! (n-1)
a001494_list = map (+ 1) $ elemIndices 0 $
               zipWith (-) (drop 2 a000010_list) a000010_list
-- Reinhard Zumkeller, Feb 08 2013

[n: n in [1..4000] | EulerPhi(n) eq EulerPhi(n+2)]; // Vincenzo Librandi, Sep 07 2016

Select[Range[3500], EulerPhi[#]==EulerPhi[#+2]&] (* Harvey P. Dale, Apr 24 2011 *)
Flatten[Position[Partition[EulerPhi[Range[3500]],3,1],?(#[[1]]==#[[3]]&),{1},Heads->False]] (* This program is more efficient than the first program above because it only has to calculate phi of each number once. *) (* _Harvey P. Dale, Aug 20 2014 *)
SequencePosition[EulerPhi[Range[4300]],{x_,,x}][[All,1]] (* Requires Mathematica version 10 or later *) (* Harvey P. Dale, Sep 04 2020 *)

op=[0,c=0]; for( n=1,1e7,if( op[bittest(n,0)+1]+0==op[bittest(n,0)+1]=eulerphi(n), write("b001494.txt",c++," "n-2))) \\ M. F. Hasler, Jan 05 2011

A000010(a(n)) = A000010(a(n) + 2). - Reinhard Zumkeller, Feb 08 2013

More terms from Jud McCranie, Dec 24 1999

A179188 Numbers n such that phi(n) = phi(n+6), with Euler's totient function phi=A000010.

Original entry on oeis.org

24, 34, 36, 39, 43, 44, 57, 72, 78, 82, 84, 93, 96, 108, 111, 146, 178, 201, 216, 222, 225, 226, 228, 306, 327, 364, 366, 381, 399, 417, 432, 438, 442, 466, 471, 482, 516, 527, 540, 543, 562, 576, 597, 610, 626, 633, 648, 706, 714, 732, 738, 802, 818, 866, 898, 912, 921, 924, 942, 948, 972, 1011

Offset: 1

M. F. Hasler, Jan 05 2011

nonn

There are 1385502728 terms under 10^12. - Jud McCranie, Feb 13 2012

Jud McCranie, Table of n, a(n) for n = 1..10000 (first 1000 terms from T. D. Noe)
F. Firoozbakht, Puzzle 466. phi(n-1)=phi(n)=phi(n+1), in C. Rivera's Primepuzzles.
Kevin Ford, Solutions of phi(n)=phi(n+k) and sigma(n)=sigma(n+k), arXiv:2002.12155 [math.NT], 2020.

Cf. A000010, A001274, A001494, A179186, A179187, A007015.

[n: n in [1..1000] | EulerPhi(n) eq EulerPhi(n+6)]; // Vincenzo Librandi, Sep 08 2016

Flatten[Position[Partition[EulerPhi[Range[1200]],7,1],?(#[[1]] == #[[7]]&),{1},Heads->False]] (* _Harvey P. Dale, Jan 30 2016 *)
Select[Range[1000], EulerPhi[#] == EulerPhi[# + 6] &] (* Vincenzo Librandi, Sep 08 2016 *)

{op=vector(N=6); for( n=1,1e4,if( op[n%N+1]+0==op[n%N+1]=eulerphi(n),print1(n-N,",")))}

A000010(a(n)) = A000010(a(n)+6).

A179186 Numbers k such that phi(k) = phi(k+4), with Euler's totient function phi = A000010.

Original entry on oeis.org

8, 14, 16, 20, 35, 52, 64, 91, 140, 148, 244, 292, 403, 455, 616, 628, 772, 801, 1011, 1024, 1108, 1144, 1252, 1270, 1295, 1456, 1588, 1684, 1820, 1828, 2030, 2164, 2452, 2623, 2644, 2660, 2692, 2932, 3028, 3216, 3321, 3508, 3988, 4264, 4340, 4372, 4612, 4804, 4852, 4948

Offset: 1

M. F. Hasler, Jan 05 2011

nonn

Is there some k > 5 such that phi(k) = phi(k+3)?
None up to 500000. - Harvey P. Dale, Feb 16 2011
No further solutions to the phi(k) = phi(k+3) problem less than 10^12. On the other hand, this sequence has 267797240 terms under 10^12. - Jud McCranie, Feb 13 2012
No reason is known that would prevent other solutions of phi(k) = phi(k+3), see Graham, Holt, & Pomerance. - Jud McCranie, Jan 03 2013
If a(n) is even then a(n)/2 is in A001494 - see comment at A217139. - Jud McCranie, Dec 31 2012

S. W. Graham, J. J. Holt, and C. Pomerance, "On the solutions to phi(n)=phi(n+k)", Number Theory in Progress, Proc. Intern. Conf. in Honor of 60th Birthday of A. Schinzel, Poland, 1997. Walter de Gruyter, 1999, pp. 867-82.

Jud McCranie, Table of n, a(n) for n = 1..10000 (first 1000 terms from T. D. Noe)
F. Firoozbakht, Puzzle 466: phi(n-1)=phi(n)=phi(n+1), in C. Rivera's Primepuzzles.
Kevin Ford, Solutions of phi(n)=phi(n+k) and sigma(n)=sigma(n+k), arXiv:2002.12155 [math.NT], 2020.

Cf. A000010, A001274, A001494, A179187, A007015.

[n: n in [1..5000] | EulerPhi(n) eq EulerPhi(n+4)]; // Vincenzo Librandi, Sep 08 2016

Select[Range[5000],EulerPhi[#]==EulerPhi[#+4]&]  (* Harvey P. Dale, Feb 16 2011 *)
SequencePosition[EulerPhi[Range[5000]],{x_,,,_,x_}][[;;,1]] (* Harvey P. Dale, Sep 12 2024 *)

{op=vector(N=4); for( n=1,1e4,if( op[n%N+1]+0==op[n%N+1]=eulerphi(n),print1(n-N,",")))}

A287055 Numbers n such that uphi(n) = uphi(n+1), where uphi(n) is the unitary totient function (A047994).

Original entry on oeis.org

1, 20, 35, 143, 194, 208, 740, 1119, 1220, 1299, 1419, 1803, 1892, 2232, 2623, 3705, 3716, 3843, 4995, 5031, 5183, 5186, 5635, 7868, 10659, 17948, 18507, 18914, 21007, 23616, 25388, 25545, 30380, 30744, 31599, 32304, 34595, 37820, 38024, 47067, 60767, 70394

Offset: 1

Amiram Eldar, May 18 2017

nonn

The unitary version of A001274 (phi(n) = phi(n+1)). The first terms that are common to both sequences are: 1, 194, 3705, 5186, 25545, 388245, 1659585, 2200694, 2521694, 2619705, 3289934, 4002405, 5781434, 6245546, 6372794, 8338394.

			uphi(20) = uphi(21) = 12, thus 20 is in the sequence.

Chai Wah Wu, Table of n, a(n) for n = 1..2198 (terms 1..207 from Amiram Eldar)

Cf. A001274, A047994.

uphi[n_] := If[n==1,1,(Times @@ (Table[#[[1]]^#[[2]] - 1, {1}] & /@ FactorInteger[n]))[[1]]]; a={}; u1=0; For[k=0, k<10^5, k++; u2=uphi[k]; If[u1==u2, a = AppendTo[a, k-1]]; u1=u2]; a

uphi(n) = my(f = factor(n)); prod(i=1, #f~, f[i,1]^f[i,2]-1);
isok(n) = uphi(n+1) == uphi(n); \\ Michel Marcus, May 20 2017

from math import prod
from sympy import factorint
A287055_list, a, n = [], 1, 1
while n < 10**5:
    b = prod(p**e-1 for p, e in factorint(n+1).items())
    if a == b:
        A287055_list.append(n)
    a, n = b, n+1 # Chai Wah Wu, Sep 24 2021

A179187 Numbers n such that phi(n)=phi(n+5), with Euler's totient function phi=A000010.

Original entry on oeis.org

5, 9, 15, 21, 15556, 21016, 25930, 25935, 27027, 36304, 46683, 129675, 266128, 307923, 329175, 430348, 503139, 636400, 684411, 812170, 1014778, 1252713, 1777545, 1871788, 1892452, 1911987, 2622160, 2629930, 2731360, 2947035, 3397480, 4200100, 5451537

Offset: 1

M. F. Hasler, Jan 05 2011

nonn

There are only 43 terms below 10^7, and 1843 terms below 10^12. [Jud McCranie, Feb 13 2012]

Jud McCranie, Table of n, a(n) for n = 1..1843 (terms < 10^12)
F. Firoozbakht, Puzzle 466. phi(n-1)=phi(n)=phi(n+1), in C. Rivera's Primepuzzles.
Kevin Ford, Solutions of phi(n)=phi(n+k) and sigma(n)=sigma(n+k), arXiv:2002.12155 [math.NT], 2020.

Cf. A000010, A001274, A001494, A179186, A007015.

[n: n in [1..5000000] | EulerPhi(n) eq EulerPhi(n+5)]; // Vincenzo Librandi, Sep 08 2016

Select[Range[5000000], EulerPhi[#] == EulerPhi[# + 5] &] (* Vincenzo Librandi, Sep 08 2016 *)
Position[Partition[EulerPhi[Range[55*10^5]],6,1],?(#[[1]] == #[[6]]&), {1}, Heads->False]//Flatten (* _Harvey P. Dale, Nov 10 2016 *)

{op=vector(N=5); for( n=1,1e7,if( op[n%N+1]+0==op[n%N+1]=eulerphi(n),print1(n-N,",")))}

A000010(a(n)) = A000010(a(n)+5).

A050472 Numbers m such that 2*phi(m) = phi(m+1).

Original entry on oeis.org

2, 4, 16, 154, 256, 286, 364, 804, 1066, 2146, 3382, 4550, 6106, 7700, 8176, 9268, 11284, 12556, 12970, 16402, 19228, 19276, 20272, 25132, 26404, 27346, 29154, 29574, 35644, 36418, 38368, 39646, 40494, 47214, 52234, 54652, 65536, 84862

Offset: 1

Jud McCranie, Dec 24 1999

nonn

			phi(256)=128, phi(256+1)=2*128, so 256 is a member of the sequence.

R. K. Guy, Unsolved Problems Number Theory, Sect. B36.

Giovanni Resta, Table of n, a(n) for n = 1..10000 (first 1000 terms from Donovan Johnson)

Cf. A000010, A001274, A050473, A171271.

Select[Range[85000], 2EulerPhi[#]==EulerPhi[#+1] &] (* Stefano Spezia, Apr 07 2025 *)

isok(n) = 2*eulerphi(n) == eulerphi(n+1); \\ Michel Marcus, Aug 02 2018

Conjecture : a(n)/n^3 is bounded. Does lim n -> infinity a(n)/n^3 = 2 ? - Benoit Cloitre, Aug 07 2002

a(n) = A171271(n) - 1. - Ray Chandler, May 01 2015

A293184 Numbers k such that bphi(k) = bphi(k+1), where bphi(k) is the bi-unitary analog of Euler's totient function (A116550).

Original entry on oeis.org

1, 14, 20, 57, 187, 188, 916, 1603, 93928, 142891, 432976, 549815, 692259, 773887, 872191, 4297168, 9478088, 127162432, 127991488, 129015616, 132527167

Offset: 1

Amiram Eldar, Oct 01 2017

187 is the first solution to bphi(k) = bphi(k+1) = bphi(k+2).

a(22) > 1.6*10^9, if it exists. - Amiram Eldar, Jul 16 2022

			14 is in the sequence since bphi(14) = bphi(15) = 9.

Cf. A001274, A116550, A287055, A294030.

bphi[1] = 1; bphi[n_] := With[{pp = Power @@@ FactorInteger[n]},   Count[Range[n], m_ /; Intersection[pp, Power @@@ FactorInteger[m]] == {}]]; a={}; b1=0; Do[b2 = bphi[k];If[b1 == b2, a = AppendTo[a, k - 1]]; b1 = b2, {k, 1, 10^3}]; a (* after Jean-François Alcover at A116550 *)

udivs(n) = {my(d = divisors(n)); select(x->(gcd(x, n/x)==1), d); }
gcud(n, m) = vecmax(setintersect(udivs(n), udivs(m)));
biuphi(n) = if (n==1, 1, sum(k=1, n-1, gcud(n, k) == 1));
isok(n) = biuphi(n) == biuphi(n+1);
lista(nn) = {x = biuphi(1); for (n=2, nn, y = biuphi(n); if (x==y, print1(n-1, ", ")); x = y;);} \\ Michel Marcus, Nov 09 2017

a(10) from Michel Marcus, Nov 11 2017
a(11) from Michel Marcus, Nov 12 2017
a(12)-a(21) from Amiram Eldar, Jul 16 2022

A179189 Numbers n such that phi(n) = phi(n+7), with Euler's totient function phi = A000010.

Original entry on oeis.org

5, 7, 21, 45, 75, 105, 285, 488, 585, 765, 1148, 1275, 1358, 1785, 2528, 3465, 4088, 6825, 9405, 12375, 14348, 15345, 16208, 16988, 23648, 25905, 25935, 42698, 50018, 52845, 54615, 61448, 62865, 68445, 78195, 80025, 82005, 88328, 93555, 98475

Offset: 1

M. F. Hasler, Jan 05 2011

nonn

There are 40 terms below 10^5, 81 terms below 10^6 and 162 terms below 10^7.  There are 6606 terms below 10^12. [Jud McCranie, Feb 13 2012]
Farideh Firoozbakht asks whether there is some a(n+1) = a(n)+7, cf. link.
For n < 10^13, the only n such that phi(n-7) = phi(n) = phi(n+7) is 30057431145. - Giovanni Resta, Feb 27 2014

Jud McCranie, Table of n, a(n) for n = 1..6606 (terms < 10^12)
F. Firoozbakht, Puzzle 466. phi(n-1)=phi(n)=phi(n+1), in C. Rivera's Primepuzzles.
Kevin Ford, Solutions of phi(n) = phi(n+k) and sigma(n) = sigma(n + k), arXiv:2002.12155 [math.NT], 2020.

Cf. A000010, A001274, A001494, A179186, A179187, A179188, A007015.

[n: n in [1..100000] | EulerPhi(n) eq EulerPhi(n+7)]; // Vincenzo Librandi, Sep 08 2016

Select[Range[100000], EulerPhi[#] == EulerPhi[# + 7] &] (* Vincenzo Librandi, Sep 08 2016 *)

{op=vector(N=7); for( n=1, 1e5, if( op[n%N+1]+0==op[n%N+1]=eulerphi(n), print1(n-N, ", ")))}

A000010(a(n)) = A000010(a(n)+7).

A179202 Numbers n such that phi(n) = phi(n+8), with Euler's totient function phi=A000010.

Original entry on oeis.org

13, 16, 19, 25, 28, 32, 40, 70, 104, 128, 175, 182, 209, 280, 296, 488, 551, 584, 657, 715, 806, 910, 1232, 1256, 1544, 1602, 2022, 2048, 2216, 2288, 2504, 2540, 2590, 2717, 2912, 3176, 3368, 3640, 3656, 4060, 4328, 4904, 5246, 5288, 5320, 5384, 5864, 5969

Offset: 1

M. F. Hasler, Jan 05 2011

nonn

Among the 5596 terms below 10^7, a(6)=32 is the only term such that a(n+1) = a(n)+8.
There are 141741552 terms under 10^12. - Jud McCranie, Feb 13 2012
If a(n) is even then a(n)/2 is in A179186 - see comment at A217139. - Jud McCranie, Dec 31 2012

M. F. Hasler and Jud McCranie, Table of n, a(n) for n = 1..10000 (first 5596 terms from M. F. Hasler)
F. Firoozbakht, Puzzle 466. phi(n-1)=phi(n)=phi(n+1), in C. Rivera's Primepuzzles.
Kevin Ford, Solutions of phi(n)=phi(n+k) and sigma(n)=sigma(n+k), arXiv:2002.12155 [math.NT], 2020.

Cf. A000010, A001274, A001494, A179186, A179187, A179188, A179189, A007015.

[n: n in [1..10000] | EulerPhi(n) eq EulerPhi(n+8)]; // Vincenzo Librandi, Sep 08 2016

Select[Range[6000], EulerPhi[#] == EulerPhi[# + 8] &] (* Vincenzo Librandi, Sep 08 2016 *)

{op=vector(N=8); for( n=1, 1e4, if( op[n%N+1]+0==op[n%N+1]=eulerphi(n), print1(n-N, ", ")))}

A000010(a(n)) = A000010(a(n)+8).

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Formula

A001494 Numbers k such that phi(k) = phi(k+2).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Magma

Mathematica

PARI

Formula

Extensions

A179188 Numbers n such that phi(n) = phi(n+6), with Euler's totient function phi=A000010.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

A179186 Numbers k such that phi(k) = phi(k+4), with Euler's totient function phi = A000010.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Mathematica

PARI

A287055 Numbers n such that uphi(n) = uphi(n+1), where uphi(n) is the unitary totient function (A047994).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

A179187 Numbers n such that phi(n)=phi(n+5), with Euler's totient function phi=A000010.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

A050472 Numbers m such that 2*phi(m) = phi(m+1).