cp's OEIS Frontend

A087625 Number of primes in the ring Z_n.

%I A087625 #11 Mar 04 2018 17:48:31
%S A087625 0,0,0,1,0,3,0,2,2,5,0,4,0,7,6,4,0,8,0,6,8,11,0,8,4,13,6,8,0,14,0,8,
%T A087625 12,17,10,10,0,19,14,12,0,20,0,12,14,23,0,16,6,24,18,14,0,24,14,16,20,
%U A087625 29,0,20,0,31,18,16,16,32,0,18,24,34,0,20,0,37,28,20,16,38,0,24,18,41,0,28,20,43,30,24,0,38,18,24,32,47,22,32,0,48
%N A087625 Number of primes in the ring Z_n.
%C A087625 a(n) <= n-phi(n)-1.
%H A087625 Antti Karttunen, <a href="/A087625/b087625.txt">Table of n, a(n) for n = 1..65537</a>
%F A087625 a(n)=Sum'_{p|n} A087623(p, n), where the sum is over all primes p < n, p | n.
%F A087625 a(p)=0 if p prime.
%F A087625 a(p^k)=p^{k-2}(p-1) if p prime, k>=2.
%F A087625 a(p^k q)=p^{k-2}(p-1)(p+q-1) if p, q primes (q!=p), k>=2.
%F A087625 a(pq)=p+q-2 if p, q primes, p!=q.
%F A087625 A(p^k q^h)=p^{k-2}q^{h-2}(p-1)(q-1)(p+q) if p, q primes (q!=p),
%e A087625 a(6)=3 because the three primes in Z_6 are 2,3,4, being 2 and 4 associates. a(500)=5(2-1)(5-1)(2+5)=140.
%o A087625 (PARI) A087625(n) = sumdiv(n,p,if((p<n)&&isprime(p),sum(k=1,n-1,(gcd(k,n)==p)),0)); \\ _Antti Karttunen_, Mar 04 2018
%Y A087625 Cf. A000010, A087623-A087624.
%K A087625 nonn,easy
%O A087625 1,6
%A A087625 Michele Dondi (bik.mido(AT)tiscalinet.it), Sep 14 2003
%E A087625 More terms from _Antti Karttunen_, Mar 04 2018