login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A049559 a(n) = gcd(n - 1, phi(n)). 29
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 (list; graph; refs; listen; history; text; internal format)
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 4 11:05 EST 2021. Contains 341791 sequences. (Running on oeis4.)