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

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

Offset

1,9

Links

T. D. Noe, Table of n, a(n) for n=1..10000

Formula

a(n) = A001222(n) - A007814(n) - A083025(n).

(2^A007814(n)) * (3^a(n)) = A065338(n).

From Antti Karttunen, Aug 14 2015: (Start)

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.]

Other identities and observations. For all n >= 1:

a(n) = A007949(A065338(n)).

a(n) = A001222(A097706(n)).

a(n) >= A260728(n). [See A260730 for the positions of differences.] (End)

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

Maple

A065339 := proc(n)
    a := 0 ;
    for f in ifactors(n)[2] do
        if op(1, f) mod 4 = 3 then
            a := a+op(2, f) ;
        end if;
    end do:
    a ;
end proc: # R. J. Mathar, Dec 16 2011

Mathematica

f[n_]:=Plus@@Last/@Select[If[n==1, {}, FactorInteger[n]], Mod[#[[1]], 4]==3&]; Table[f[n], {n, 100}] (* Ray Chandler, Dec 18 2011 *)

Prog

(Haskell)
a065339 1 = 0
a065339 n = length [x | x <- a027746_row n, mod x 4 == 3]
-- Reinhard Zumkeller, Jan 10 2012
(PARI) A065339(n)=sum(i=1, #n=factor(n)~, if(n[1, i]%4==3, n[2, i]))  \\ M. F. Hasler, Apr 16 2012
(Scheme, two variants using memoization-macro definec)
(definec (A065339 n) (cond ((< n 3) 0) ((even? n) (A065339 (/ n 2))) (else (+ (/ (- (modulo (A020639 n) 4) 1) 2) (A065339 (A032742 n))))))
(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))))))
;; Antti Karttunen, Aug 14 2015

Crossrefs

Cf. A001222, A007814, A065338, A005091, A007949, A083025 (analogous for 4k+1 primes), A097706.

Cf. A020639, A027746, A028234, A032742, A067029, A260728, A260730.

Sequence in context: A091430 A362221 A260728 * A122434 A141571 A164067

Adjacent sequences: A065336 A065337 A065338 * A065340 A065341 A065342

Keyword

nonn

Author

Reinhard Zumkeller, Oct 29 2001

Status

approved