A001274 Numbers k such that phi(k) = phi(k+1).

1, 3, 15, 104, 164, 194, 255, 495, 584, 975, 2204, 2625, 2834, 3255, 3705, 5186, 5187, 10604, 11715, 13365, 18315, 22935, 25545, 32864, 38804, 39524, 46215, 48704, 49215, 49335, 56864, 57584, 57645, 64004, 65535, 73124, 105524, 107864, 123824, 131144, 164175, 184635

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• nice

Comments

Unlike totients, cototient(x + 1) = cototient(x) never holds (except 2 - phi(2) = 3 - phi(3) = 1) because cototient(x) is congruent to x modulo 2. - Labos Elemer, Aug 08 2001

Lal-Gillard and Firoozbakht ask whether there is another pair of consecutive integers in this sequence, apart from a(16) + 1 = a(17) = 5187, see link. - M. F. Hasler, Jan 05 2011

There are 5236 terms less than 10^12. - Jud McCranie, Feb 13 2012

Up to 10^13 there are 10755 terms, and no further consecutive pairs like (5186, 5187). - Giovanni Resta, Feb 27 2014

A051179(k) for k from 0 to 5 are in the sequence. No other members of A051179 are in the sequence, because phi(2^(2^k)-1) = Product_{j=1..k-1} phi(2^(2^j)+1) and phi(2^(2^5)+1) < 2^(2^5) so if k > 5, phi(2^(2^k)-1) < Product_{j=1..k-1} 2^(2^j) = 2^(2^k-1) = phi(2^(2^k)). - Robert Israel, Mar 31 2015

Number of terms < 10^k, k=1,2,3,...: 2, 3, 10, 17, 36, 68, 142, 306, 651, 1267, 2567, 5236, 10755, ..., . - Robert G. Wilson v, Apr 10 2019

Conjecture: Except for the first two terms, all terms are composite and congruent to either 2 or 3 (mod 6). - Robert G. Wilson v, Apr 10 2019

Paul Kinlaw has noticed that up to 10^13 the only counterexample to the above conjecture is a(7424) = 3044760173455. - Giovanni Resta, May 23 2019

Examples

			phi(3) = phi(4) = 2, so 3 is in the sequence.
phi(15) = phi(16) = 8, so 15 is in the sequence.
		

References

• J.-M. De Koninck, Ces nombres qui nous fascinent, Entry 15, pp 5, Ellipses, Paris 2008.
• 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).

Links

• Giovanni Resta, Table of n, a(n) for n = 1..10755 (terms < 10^13, a(1)-a(2567) from T. D. Noe, a(2568)-a(5236) from J. McCranie)
• R. Baillie, Table of phi(n) = phi(n+1), Math. Comp., 30 (1976), 189-190.
• Jonathan Bayless and Paul Kinlaw, Consecutive coincidences of Euler's function, International Journal of Number Theory, Vol. 12, No. 4 (2016), pp. 1011-1026.
• Farideh 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.
• Dov Jarden, Recurring Sequences, Riveon Lematematika, Jerusalem, 1966. [Annotated scanned copy] See p. 66.
• Paul Kinlaw, Mitsuo Kobayashi and Carl Pomerance, On the equation phi(n) = phi(n+1), Acta Arithmetica, Vol. 196 (2020), pp. 69-92, alternative link.
• V. L. Klee, Jr., Some remarks on Euler's totient function, Amer. Math. Monthly, 54 (1947), 332.
• M. Lal and P. Gillard, On the equation phi(n) = phi(n+k), Math. Comp., 26 (1972), 579-583.
• K. Miller, Solutions of phi(n) = phi(n+1) for 1 <= n <= 500000. Unpublished, 1972. [ Cf. (Untitled), Math. Comp., Vol. 27, p. 447, 1973 ].
• Leo Moser, Some equations involving Euler's totient function, Amer. Math. Monthly, 56 (1949), 22-23.
• J. Shallit, Letter to N. J. A. Sloane, Jul 17 1975.

Crossrefs

Cf. A000010, A001494, A051953, A003276, A003275, A007015, A179186, A179187, A179188, A179189, A179202, A217139.

Programs

Haskell

import Data.List (elemIndices)
a001274 n = a001274_list !! (n-1)
a001274_list = map (+ 1) $ elemIndices 0 $
                           zipWith (-) (tail a000010_list) a000010_list
-- Reinhard Zumkeller, May 20 2014, Mar 31 2011

Magma

[n: n in [1..3*10^5] | EulerPhi(n) eq EulerPhi(n+1)]; // Vincenzo Librandi, Apr 14 2015

Maple

select(n -> numtheory:-phi(n) = numtheory:-phi(n+1), [$1..10^5]); # Robert Israel, Mar 31 2015

Mathematica

Reap[For[n = 1; k = 2; f1 = 1, k <= 10^9, k++, f2 = EulerPhi[k]; If[f1 == f2, Print["a(", n, ") = ", k - 1]; Sow[k - 1]; n++]; f1 = f2]][[2, 1]] (* Jean-François Alcover, Mar 29 2011, revised Dec 26 2013 *)
Flatten[Position[Partition[EulerPhi[Range[200000]],2,1],{x_,x_}]] (* Harvey P. Dale, Dec 27 2015 *)
Select[Range[1000], EulerPhi[#] == EulerPhi[# + 1] &] (* Alonso del Arte, Oct 03 2014 *)
SequencePosition[EulerPhi[Range[200000]],{x_,x_}][[All,1]] (* Requires Mathematica version 10 or later *) (* Harvey P. Dale, May 01 2018 *)
k = 8; lst = {1, 3}; While[k < 200000, If[ !PrimeQ[k +1], ep = EulerPhi[k +1]; If[ EulerPhi[k] == ep, AppendTo[lst, k]]; If[ep == EulerPhi[k +2], AppendTo[lst, k +1]]]; k += 6]; lst (* Robert G. Wilson v, Apr 10 2019 *)

PARI

is(n)=eulerphi(n)==eulerphi(n+1) \\ Charles R Greathouse IV, Feb 27 2014

PARI

list(lim)=my(v=List(),old=1); forfactored(n=2,lim\1+1, my(new=eulerphi(n)); if(old==new, listput(v,n[1]-1)); old=new); Vec(v) \\ Charles R Greathouse IV, Jul 17 2022

Formula

Conjecture: a(n) ~ C*n^3*log(n), where C = 9/Pi^2 = 0.91189... - Thomas Ordowski, Oct 21 2014

Sum_{n>=1} 1/a(n) is in the interval (1.4324884, 7.8358) (Kinlaw et al., 2020; an upper bound 441702 was given by Bayless and Kinlaw, 2016). - Amiram Eldar, Oct 15 2020

Extensions

More terms from David W. Wilson