A247074 - OEIS

%I #89 Aug 01 2019 03:49:14

%S 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,

%T 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,

%U 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

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

%C a(n) = A000010(n)/A063994(n). - _Eric Chen_, Nov 29 2014

%C Does every natural number appear in this sequence? If so, do they appear infinitely many times? - _Eric Chen_, Nov 26 2014

%C A063994(n) must be a factor of EulerPhi(n). - _Eric Chen_, Nov 26 2014

%C 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

%C a(n) = 1 if and only if n is 1, prime (A000040), or Carmichael number (A002997). - _Eric Chen_, Nov 26 2014

%C a(A191311(n)) = 2. - _Eric Chen_, Nov 26 2014

%C a(p^n) = p^(n-1), where p is a prime. - _Eric Chen_, Nov 26 2014

%C a(A209211(n)) = EulerPhi(A209211(n)), because A063994(A209211(n)) = 1. - _Eric Chen_, Nov 26 2014

%H Charles R Greathouse IV, <a href="/A247074/b247074.txt">Table of n, a(n) for n = 1..10000</a>

%H Gérard P. Michon, <a href="http://www.numericana.com/answer/pseudo.htm">Pseudoprimes</a>

%F A003557(n) <= a(n) <= n, and a(n) is a multiple of A003557(n). - _Charles R Greathouse IV_, Nov 17 2014

%e 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.

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

%o (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

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

%K nonn,easy,hear

%O 1,4

%A _Eric Chen_, Nov 16 2014