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,3

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

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

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

Example

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

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 *)

Prog

(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
(Magma) [Gcd(n-1, EulerPhi(n)): n in [1..80]]; // Vincenzo Librandi, Oct 13 2018

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.

Sequence in context: A060680 A057237 A187730 * A063994 A268336 A295127

Adjacent sequences: A049556 A049557 A049558 * A049560 A049561 A049562

Keyword

nonn

Author

Labos Elemer, Dec 28 2000

Status

approved