A087694 Number of solutions to x^2 + xy + y^2 == 0 (mod n).

1, 1, 3, 4, 1, 3, 13, 4, 9, 1, 1, 12, 25, 13, 3, 16, 1, 9, 37, 4, 39, 1, 1, 12, 25, 25, 27, 52, 1, 3, 61, 16, 3, 1, 13, 36, 73, 37, 75, 4, 1, 39, 85, 4, 9, 1, 1, 48, 133, 25, 3, 100, 1, 27, 1, 52, 111, 1, 1, 12, 121, 61, 117, 64, 25, 3, 133, 4, 3, 13

Offset: 1

Author

Yuval Dekel (dekelyuval(AT)hotmail.com), Sep 27 2003

Keywords

• mult
• nonn
• easy

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A000086, A073010, A086724.

Programs

Maple

A087694 := proc(n) option remember; local pf,p,f,e ; if n = 1 then 1; else pf := ifactors(n)[2] ; if nops(pf) = 1 then f := op(1,pf) ; p := op(1,f) ; e := op(2,f) ; if p = 3 then n ; elif p mod 3 =1 then ((p-1)*e+p)*p^(e-1) ; else p^(2*floor(e/2)) ; end if; else mul(procname(op(1,p)^op(2,p)),p=pf) ; end if; end if; end proc:
seq(A087694(n),n=1..70) ; # R. J. Mathar, Jan 07 2011

Mathematica

a[n_] := If[n==1, 1, Product[{p, e} = pe; Which[p==3, 3^e, Mod[p, 3] == 2, (p^2)^Quotient[e, 2], True, ((p-1) e + p) p^(e-1)], {pe, FactorInteger[n] }]];
a /@ Range[1, 100] (* Jean-François Alcover, Sep 20 2019, from PARI *)

PARI

a(n)={my(f=factor(n)); prod(i=1, #f~, my(p=f[i,1], e=f[i,2]); if(p==3, 3^e, if(p%3==2, (p^2)^(e\2), ((p-1)*e+p)*p^(e-1))))} \\ Andrew Howroyd, Jul 09 2018

Formula

Multiplicative with a(3^e) = 3^e, a(p^e) = ((p-1)*e+p)*p^(e-1) if p mod 3 = 1, a(p^e) = p^(2*floor(e/2)) if p mod 3 = 2. - Vladeta Jovovic, Sep 27 2003

Sum_{k=1..n} a(k) ~ c * n^2 / 2, where c = A073010/A086724 = 0.77383581325017004332... . - Amiram Eldar, Nov 21 2023