A247074 a(n) = phi(n)/(Product_{primes p dividing n } gcd(p - 1, n - 1)).

1, 1, 1, 2, 1, 2, 1, 4, 3, 4, 1, 4, 1, 6, 2, 8, 1, 6, 1, 8, 3, 10, 1, 8, 5, 12, 9, 4, 1, 8, 1, 16, 5, 16, 6, 12, 1, 18, 6, 16, 1, 12, 1, 20, 3, 22, 1, 16, 7, 20, 8, 8, 1, 18, 10, 24, 9, 28, 1, 16, 1, 30, 9, 32, 3, 4, 1, 32, 11, 8, 1, 24, 1, 36, 10, 12, 15, 24, 1, 32, 27, 40, 1, 24, 4, 42, 14, 40, 1, 24, 2, 44, 15, 46

Offset: 1

Author

Eric Chen, Nov 16 2014

Keywords

• nonn
• easy
• hear

Comments

a(n) = A000010(n)/A063994(n). - Eric Chen, Nov 29 2014

Does every natural number appear in this sequence? If so, do they appear infinitely many times? - Eric Chen, Nov 26 2014

A063994(n) must be a factor of EulerPhi(n). - Eric Chen, Nov 26 2014

Number n is (Fermat) pseudoprimes (or prime) to one in a(n) of its coprime bases. That is, b^(n-1) = 1 (mod n) for one in a(n) of numbers b coprime to n. - Eric Chen, Nov 26 2014

a(n) = 1 if and only if n is 1, prime (A000040), or Carmichael number (A002997). - Eric Chen, Nov 26 2014

a(A191311(n)) = 2. - Eric Chen, Nov 26 2014

a(p^n) = p^(n-1), where p is a prime. - Eric Chen, Nov 26 2014

a(A209211(n)) = EulerPhi(A209211(n)), because A063994(A209211(n)) = 1. - Eric Chen, Nov 26 2014

Examples

			EulerPhi(15) = 8, and that 15 is a Fermat pseudoprime in base 1, 4, 11, and 14, the total is 4 bases, so a(15) = 8/4 = 2.
		

Links

• Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
• Gérard P. Michon, Pseudoprimes

Crossrefs

Cf. A063994, A182816, A002997, A191311, A064234, A000010, A063994, A003557, A209211.

Programs

Mathematica

a063994[n_] := Times @@ GCD[n - 1, First /@ FactorInteger@ n - 1]; a063994[1] = 1; a247074[n_] := EulerPhi[n]/a063994[n]; Array[a247074, 150]

PARI

a(n)=my(f=factor(n));eulerphi(f)/prod(i=1,#f~,gcd(f[i,1]-1,n-1)) \\ Charles R Greathouse IV, Nov 17 2014

Formula

A003557(n) <= a(n) <= n, and a(n) is a multiple of A003557(n). - Charles R Greathouse IV, Nov 17 2014