login
The number of primes <= n that are strongly prime to n.
10

%I #8 Jul 23 2013 06:23:18

%S 0,0,0,0,0,1,0,1,2,2,1,2,2,3,3,2,3,5,4,5,5,4,4,6,6,6,6,6,6,7,6,7,9,8,

%T 7,7,7,9,9,8,8,10,9,10,11,10,10,12,12,12,12,11,11,13,13,12,12,12,12,

%U 14,13,14,15,14,15,15,13,15,16,15,14,16,17

%N The number of primes <= n that are strongly prime to n.

%C k is strongly prime to n iff k is relatively prime to n and k does not divide n-1.

%H Peter Luschny, <a href="http://www.oeis.org/wiki/User:Peter_Luschny/StrongCoprimality">Strong coprimality</a>.

%e a(11) = card(primes in {3, 4, 6, 7, 8, 9}) = card({3, 7}) = 2.

%p with(numtheory):

%p Primes := n -> select(k->isprime(k),{$1..n}):

%p StrongCoprimes := n -> select(k->igcd(k,n)=1,{$1..n}) minus divisors(n-1):

%p StrongCoprimePrimes := n -> Primes(n) intersect StrongCoprimes(n):

%p A181834 := n -> nops(StrongCoprimePrimes(n)):

%t strongCoprimeQ[k_, n_] := PrimeQ[k] && CoprimeQ[n, k] && !Divisible[n-1, k]; a[n_] := Select[Range[n], strongCoprimeQ[#, n]&] // Length; Table[a[n], {n, 0, 72}] (* _Jean-François Alcover_, Jul 23 2013 *)

%Y Cf. A181830, A181831, A181832, A181833, A181835, A181836, A048865.

%K nonn

%O 0,9

%A _Peter Luschny_, Nov 17 2010