A340087 -id:A340087 - cp's OEIS frontend

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

Labos Elemer, Dec 28 2000

nonn

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

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

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

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

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.

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

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

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

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

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

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

A340088 a(n) = A091732(n) / gcd(n-1, A091732(n)), where A091732 is an infinitary analog of Euler's phi function.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 3, 1, 4, 1, 6, 1, 6, 4, 1, 1, 8, 1, 12, 3, 10, 1, 6, 1, 12, 8, 2, 1, 8, 1, 15, 5, 16, 12, 24, 1, 18, 12, 4, 1, 12, 1, 30, 8, 22, 1, 30, 1, 24, 16, 12, 1, 16, 20, 18, 9, 28, 1, 24, 1, 30, 24, 5, 3, 4, 1, 48, 11, 8, 1, 24, 1, 36, 24, 18, 15, 24, 1, 60, 1, 40, 1, 36, 16, 42, 28, 10, 1, 32, 4, 66

Offset: 1

Antti Karttunen, Dec 31 2020

nonn

Conjecture: a(n) = 1 iff n = 1 or in A050376. This is an infinitary analog of Lehmer's totient conjecture from 1932.

For all i, j > 1: a(i) = a(j) => A302777(i) = A302777(j), if the above conjecture holds.

Antti Karttunen, Table of n, a(n) for n = 1..65537
Wikipedia, Lehmer's totient problem

Cf. A050376, A084400, A091732, A302777, A340087, A340089.

Cf. also A160595.

ispow2(n) = (n && !bitand(n,n-1));
A302777(n) = ispow2(isprimepower(n));
A091732(n) = { my(m=1); while(n > 1, fordiv(n, d, if((dA302777(n/d), m *= ((n/d)-1); n = d; break))); (m); };
A340088(n) = { my(x=A091732(n)); (x/gcd(n-1, x)); };

a(n) = A091732(n) / A340087(n) = A091732(n) / gcd(n-1, A091732(n)).

For all n >= 1, a(A084400(n)) = 1.

A340089 a(n) = (n-1) / gcd(n-1, A091732(n)), where A091732 is an infinitary analog of Euler's phi function.

Original entry on oeis.org

0, 1, 1, 1, 1, 5, 1, 7, 1, 9, 1, 11, 1, 13, 7, 1, 1, 17, 1, 19, 5, 21, 1, 23, 1, 25, 13, 3, 1, 29, 1, 31, 8, 33, 17, 35, 1, 37, 19, 13, 1, 41, 1, 43, 11, 45, 1, 47, 1, 49, 25, 17, 1, 53, 27, 55, 14, 57, 1, 59, 1, 61, 31, 7, 4, 13, 1, 67, 17, 23, 1, 71, 1, 73, 37, 25, 19, 77, 1, 79, 1, 81, 1, 83, 21, 85, 43, 29, 1, 89

Offset: 1

Antti Karttunen, Dec 31 2020

nonn

Antti Karttunen, Table of n, a(n) for n = 1..65537

Cf. A091732, A340087, A340088.

Cf. also A160596.

ispow2(n) = (n && !bitand(n,n-1));
A302777(n) = ispow2(isprimepower(n));
A091732(n) = { my(m=1); while(n > 1, fordiv(n, d, if((dA302777(n/d), m *= ((n/d)-1); n = d; break))); (m); };
A340089(n) = ((n-1)/gcd(n-1, A091732(n)));

a(n) = (n-1) / A340087(n) = (n-1) / gcd(n-1, A091732(n)).

A345937 a(n) = gcd(n-1, uphi(n)), where uphi is unitary totient (or unitary phi) function, A047994.

Original entry on oeis.org

1, 1, 2, 3, 4, 1, 6, 7, 8, 1, 10, 1, 12, 1, 2, 15, 16, 1, 18, 1, 4, 1, 22, 1, 24, 1, 26, 9, 28, 1, 30, 31, 4, 1, 2, 1, 36, 1, 2, 1, 40, 1, 42, 1, 4, 1, 46, 1, 48, 1, 2, 3, 52, 1, 2, 1, 4, 1, 58, 1, 60, 1, 2, 63, 16, 5, 66, 1, 4, 3, 70, 1, 72, 1, 2, 3, 4, 1, 78, 1, 80, 1, 82, 1, 4, 1, 2, 1, 88, 1, 18, 1, 4, 1, 2, 1, 96

Offset: 1

Antti Karttunen, Jun 29 2021

nonn

Antti Karttunen, Table of n, a(n) for n = 1..16384

Cf. A047994, A345938, A345939.

Cf. also A049559, A340087, A323409, A345947.

A047994(n) = { my(f=factor(n)~); prod(i=1, #f, (f[1, i]^f[2, i])-1); };
A345937(n) = gcd(n-1, A047994(n));

a(n) = gcd(n-1, A047994(n)).
a(n) = A047994(n) / A345938(n).
a(n) = (n-1) / A345939(n), for n > 1.
a(2n-1) = A345947(2n-1), for n >= 1.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Python

Formula

A340088 a(n) = A091732(n) / gcd(n-1, A091732(n)), where A091732 is an infinitary analog of Euler's phi function.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A340089 a(n) = (n-1) / gcd(n-1, A091732(n)), where A091732 is an infinitary analog of Euler's phi function.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

A345937 a(n) = gcd(n-1, uphi(n)), where uphi is unitary totient (or unitary phi) function, A047994.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula