A086933 Number of solutions to x^2 + y^2 = 0 mod n.

1, 2, 1, 4, 9, 2, 1, 8, 9, 18, 1, 4, 25, 2, 9, 16, 33, 18, 1, 36, 1, 2, 1, 8, 65, 50, 9, 4, 57, 18, 1, 32, 1, 66, 9, 36, 73, 2, 25, 72, 81, 2, 1, 4, 81, 2, 1, 16, 49, 130, 33, 100, 105, 18, 9, 8, 1, 114, 1, 36, 121, 2, 9, 64, 225, 2, 1, 132, 1, 18, 1, 72, 145, 146, 65, 4, 1, 50, 1, 144, 81

Offset

1,2

Comments

Sum_{n<N} a(n) ~ (Pi/(8*G))*N^2 as N approaches infinity, where G is Catalan's constant. - Steven Finch, Feb 05 2007

Links

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

S. R. Finch, Series involving arithmetric functions.

N. Gafurov, On the number of divisors of a quadratic form, Proc. Steklov Inst. Math. 200 (1993) 137-148.

L. Tóth, Counting solutions of quadratic congruences in several variables revisited, arXiv preprint arXiv:1404.4214 [math.NT], 2014.

L. Toth, Counting Solutions of Quadratic Congruences in Several Variables Revisited, J. Int. Seq. 17 (2014) # 14.11.6.

G. Yu, On the number of divisors of the quadratic form m^2+n^2, Canad. Math. Bull. 43 (2000) 239-256.

Formula

Multiplicative with a(2^e)=2^e, a(p^e)=p^(e-(e mod 2)) if p mod 4=3, a(p^e)=((p-1)*e+p)*p^(e-1) if p mod 4<>3 and p<>2. - Vladeta Jovovic, Sep 22 2003

From Peter Bala, Mar 24 2019: (Start)

a(n) = n*Sum_{d|n, d odd} (-1)^((d-1)/2)*phi(d)/d.

O.g.f.: Sum_{n odd} (-1)^((n-1)/2)*phi(n)*x^n/(1 - x^n)^2. (End)

Mathematica

a[n_] := a[n] = Module[{f, p, e}, f = FactorInteger[n]; Switch[f, {{2, _}}, Return[n], {{_, _}}, {p, e} = f[[1]]; If[Mod[p, 4] == 3, Return[p^(e - Mod[e, 2])], Return[((p-1)*e+p)*p^(e-1)]], _, Times @@ (a[#[[1]]^#[[2]]]& /@ f)]];
Array[a, 81] (* Jean-François Alcover, Aug 21 2018, after Vladeta Jovovic *)

Prog

(PARI) ap(p, e)=if(p%4<2, ((p-1)*e+p)*p^(e-1), p^(e - e%2))
a(n)=my(o=valuation(n, 2), f=factor(n>>o)); prod(i=1, #f~, ap(f[i, 1], f[i, 2]))<<o \\ Charles R Greathouse IV, Dec 06 2016

Crossrefs

Cf. A062803.

Sequence in context: A076014 A120458 A183244 * A077878 A128058 A163236

Adjacent sequences: A086930 A086931 A086932 * A086934 A086935 A086936

Keyword

mult,nonn

Author

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

Extensions

More terms from John W. Layman, Sep 22 2003

Status

approved