A049559 a(n) = gcd(n - 1, phi(n)).

1, 1, 2, 1, 4, 1, 6, 1, 2, 1, 10, 1, 12, 1, 2, 1, 16, 1, 18, 1, 4, 1, 22, 1, 4, 1, 2, 3, 28, 1, 30, 1, 4, 1, 2, 1, 36, 1, 2, 1, 40, 1, 42, 1, 4, 1, 46, 1, 6, 1, 2, 3, 52, 1, 2, 1, 4, 1, 58, 1, 60, 1, 2, 1, 16, 5, 66, 1, 4, 3, 70, 1, 72, 1, 2, 3, 4, 1, 78, 1, 2, 1, 82, 1, 4, 1, 2, 1, 88, 1, 18, 1, 4

Offset: 1

Author

Labos Elemer, Dec 28 2000

Keywords

• nonn

Comments

For prime n, a(n) = n - 1. Question: do nonprimes exist with this property?

Answer: No. If n is composite then a(n) < n - 1. - Charles R Greathouse IV, Dec 09 2013

Lehmer's totient problem (1932): are there composite numbers n such that a(n) = phi(n)? - Thomas Ordowski, Nov 08 2015

a(n) = 1 for n in A209211. - Robert Israel, Nov 09 2015

Examples

			a(9) = 2 because phi(9) = 6 and gcd(8, 6) = 2.
a(10) = 1 because phi(10) = 4 and gcd(9, 4) = 1.
		

References

• Richard K. Guy, Unsolved Problems in Number Theory, B37.

Links

• Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
• Eric Weisstein's World of Mathematics, Lehmer's Totient Problem

Crossrefs

Cf. A000010, A002322, A039766, A063994, A160595, A209211, A219428, A264012, A264024, A280262, A283656, A283872, A284089, A284440, A318827, A318829, A318830, A330747 (ordinal transform), A340195.

Cf. also A009195, A058515, A058663, A187730, A258409, A339964, A340071, A340081, A340087 for more or less analogous sequences.

Programs

Magma

[Gcd(n-1, EulerPhi(n)): n in [1..80]]; // Vincenzo Librandi, Oct 13 2018

Maple

seq(igcd(n-1, numtheory:-phi(n)), n=1..100); # Robert Israel, Nov 09 2015

Mathematica

Table[GCD[n - 1, EulerPhi[n]], {n, 93}] (* Michael De Vlieger, Nov 09 2015 *)

PARI

a(n)=gcd(eulerphi(n),n-1) \\ Charles R Greathouse IV, Dec 09 2013

Python

from sympy import totient, gcd
print([gcd(totient(n), n - 1) for n in range(1, 101)]) # Indranil Ghosh, Mar 27 2017

Formula

a(p^m) = a(p) = p - 1 for prime p and m > 0. - Thomas Ordowski, Dec 10 2013

From Antti Karttunen, Sep 09 2018: (Start)

a(n) = A000010(n) / A160595(n) = A063994(n) / A318829(n).

a(n) = n - A318827(n) = A000010(n) - A318830(n).

(End)

a(n) = gcd(A000010(n), A219428(n)) = gcd(A000010(n), A318830(n)). - Antti Karttunen, Jan 05 2021