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
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.
Crossrefs
Cf. A062803.
Programs
-
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 *) -
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]))<
Charles R Greathouse IV, Dec 06 2016
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)
Extensions
More terms from John W. Layman, Sep 22 2003
Comments