cp's OEIS Frontend

A065339 Number of primes congruent to 3 modulo 4 dividing n (with multiplicity).

%I A065339 #43 Feb 12 2025 10:46:47
%S A065339 0,0,1,0,0,1,1,0,2,0,1,1,0,1,1,0,0,2,1,0,2,1,1,1,0,0,3,1,0,1,1,0,2,0,
%T A065339 1,2,0,1,1,0,0,2,1,1,2,1,1,1,2,0,1,0,0,3,1,1,2,0,1,1,0,1,3,0,0,2,1,0,
%U A065339 2,1,1,2,0,0,1,1,2,1,1,0,4,0,1,2,0,1,1,1,0,2,1,1,2,1,1,1,0,2,3,0,0,1,1,0,2
%N A065339 Number of primes congruent to 3 modulo 4 dividing n (with multiplicity).
%H A065339 T. D. Noe, <a href="/A065339/b065339.txt">Table of n, a(n) for n=1..10000</a>
%F A065339 a(n) = A001222(n) - A007814(n) - A083025(n).
%F A065339 (2^A007814(n)) * (3^a(n)) = A065338(n).
%F A065339 From _Antti Karttunen_, Aug 14 2015: (Start)
%F A065339 a(1) = a(2) = 0; thereafter, if n is even, a(n) = a(n/2), otherwise a(n) = ((A020639(n) mod 4)-1)/2 + a(n/A020639(n)). [Where A020639(n) gives the smallest prime factor of n.]
%F A065339 Other identities and observations. For all n >= 1:
%F A065339 a(n) = A007949(A065338(n)).
%F A065339 a(n) = A001222(A097706(n)).
%F A065339 a(n) >= A260728(n). [See A260730 for the positions of differences.] (End)
%F A065339 Totally additive with a(2) = 0, a(p) = 1 if p == 3 (mod 4), and a(p) = 0 if p == 1 (mod 4). - _Amiram Eldar_, Jun 17 2024
%p A065339 A065339 := proc(n)
%p A065339     a := 0 ;
%p A065339     for f in ifactors(n)[2] do
%p A065339         if op(1,f) mod 4 = 3 then
%p A065339             a := a+op(2,f) ;
%p A065339         end if;
%p A065339     end do:
%p A065339     a ;
%p A065339 end proc: # _R. J. Mathar_, Dec 16 2011
%t A065339 f[n_]:=Plus@@Last/@Select[If[n==1,{},FactorInteger[n]],Mod[#[[1]],4]==3&]; Table[f[n],{n,100}] (* _Ray Chandler_, Dec 18 2011 *)
%o A065339 (Haskell)
%o A065339 a065339 1 = 0
%o A065339 a065339 n = length [x | x <- a027746_row n, mod x 4 == 3]
%o A065339 -- _Reinhard Zumkeller_, Jan 10 2012
%o A065339 (PARI) A065339(n)=sum(i=1,#n=factor(n)~,if(n[1,i]%4==3,n[2,i]))  \\ _M. F. Hasler_, Apr 16 2012
%o A065339 (Scheme)
%o A065339 ;; using memoization-macro definec
%o A065339 (definec (A065339 n) (cond ((< n 3) 0) ((even? n) (A065339 (/ n 2))) (else (+ (/ (- (modulo (A020639 n) 4) 1) 2) (A065339 (A032742 n))))))
%o A065339 ;; _Antti Karttunen_, Aug 14 2015
%o A065339 (Scheme)
%o A065339 ;; using memoization-macro definec
%o A065339 (definec (A065339 n) (cond ((< n 3) 0) ((even? n) (A065339 (/ n 2))) ((= 1 (modulo (A020639 n) 4)) (A065339 (A032742 n))) (else (+ (A067029 n) (A065339 (A028234 n))))))
%o A065339 ;; _Antti Karttunen_, Aug 14 2015
%Y A065339 Cf. A001222, A007814, A065338, A005091, A007949, A083025 (analogous for 4k+1 primes), A097706, A378194.
%Y A065339 Cf. A020639, A027746, A028234, A032742, A067029, A260728, A260730.
%K A065339 nonn
%O A065339 1,9
%A A065339 _Reinhard Zumkeller_, Oct 29 2001