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

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, 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, 14, 13, 14, 15, 14, 15, 15, 13, 15, 16, 15, 14, 16, 17

Offset: 0

Author

Peter Luschny, Nov 17 2010

Keywords

• nonn

Comments

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

Examples

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

Links

• Peter Luschny, Strong coprimality.

Crossrefs

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

Programs

Maple

with(numtheory):
Primes := n -> select(k->isprime(k),{$1..n}):
StrongCoprimes := n -> select(k->igcd(k,n)=1,{$1..n}) minus divisors(n-1):
StrongCoprimePrimes := n -> Primes(n) intersect StrongCoprimes(n):
A181834 := n -> nops(StrongCoprimePrimes(n)):

Mathematica

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 *)