%I A000089
%S A000089 1,1,0,0,2,0,0,0,0,2,0,0,2,0,0,0,2,0,0,0,0,0,0,0,2,2,0,0,2,0,0,0,0,2,0,
%T A000089 0,2,0,0,0,2,0,0,0,0,0,0,0,0,2,0,0,2,0,0,0,0,2,0,0,2,0,0,0,4,0,0,0,0,0,
%U A000089 0,0,2,2,0,0,0,0,0,0,0,2,0,0,4,0,0,0,2,0,0,0,0,0,0,0,2,0,0,0,2,0,0,0,0
%N A000089 Number of solutions to x^2 + 1 == 0 (mod n).
%C A000089 Number of elliptic points of order 2 for GAMMA_0 (n).
%D A000089 M. Baake, "Solution of coincidence problem...", in R. V. Moody, ed., 
               Math. of Long-Range Aperiodic Order, Kluwer 1997, pp. 9-44.
%D A000089 Fell, Harriet; Newman, Morris; Ordman, Edward; Tables of genera of groups 
               of linear fractional transformations. J. Res. Nat. Bur. Standards 
               Sect. B 67B 1963 61-68.
%D A000089 G. Shimura, Introduction to the Arithmetic Theory of Automorphic Functions, 
               Princeton, 1971, see p. 25, Eq. (2).
%D A000089 John S. Rutherford, Sublattice enumeration. IV. Equivalence classes of 
               plane sublattices by parent Patterson symmetry and colour lattice 
               group type, Acta Cryst. (2009). A65, 156163. [See Table 4].
%H A000089 T. D. Noe, <a href="b000089.txt">Table of n, a(n) for n=1..2000</a>
%H A000089 M. Baake and U. Grimm, <a href="http://www.ma.utexas.edu/mp_arc-bin/mpa?yn=02-392">
               Quasicrystalline combinatorics</a>
%H A000089 S. R. Finch and Pascal Sebah, <a href="http://arXiv.org/abs/math.NT/0604465">
               Squares and Cubes Modulo n</a> (arXiv:math.NT/0604465).
%F A000089 a(n) = 0 if 4|n, else a(n) = Product_{ p | N } (1 + Legendre(-1, p) ), 
               where we use the definition that Legendre(-1, 2) = 0, Legendre(-1, 
               p) = 1 if p == 1 mod 4, = -1 if p == 3 mod 4. This is Shimura's definition, 
               which is different from Maple's.
%F A000089 Dirichlet series: (1+2^(-s))*Product (1+p^(-s))/(1-p^(-s)) (p=1 mod 4).
%F A000089 Multiplicative with a(p^e) = 1 if p = 2 and e = 1; 0 if p = 2 and e > 
               1; 2 if p == 1 (mod 4); 0 if p == 3 (mod 4). - David W. Wilson (davidwwilson(AT)comcast.net), 
               Aug 01, 2001.
%p A000089 with(numtheory); A000089 := proc (n) local i, s; if modp(n,4) = 0 then 
               RETURN(0) fi; s := 1; for i in divisors(n) do if isprime(i) and i 
               > 2 then s := s*(1+eval(legendre(-1,i))) fi od; s end: (Gene Smith, 
               May 22 2006)
%t A000089 Array[ Function[ n, If[ EvenQ[ n ] || Mod[ n, 3 ]==2, 0, Count[ Array[ 
               Mod[ #^2+1, n ]&, n, 0 ], 0 ] ] ], 84 ]
%Y A000089 Sequence in context: A037134 A001343 A022882 this_sequence A051907 A093569 
               A073091
%Y A000089 Adjacent sequences: A000086 A000087 A000088 this_sequence A000090 A000091 
               A000092
%K A000089 nonn,nice,mult
%O A000089 1,5
%A A000089 N. J. A. Sloane (njas(AT)research.att.com).