login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000089 Number of solutions to x^2 + 1 == 0 (mod n). 28

%I

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

%T 0,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,

%U 0,0,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 Number of solutions to x^2 + 1 == 0 (mod n).

%C Number of elliptic points of order 2 for GAMMA_0(n).

%C The Dirichlet inverse, 1, -1, 0, 1, -2, 0, 0, -1, 0, 2, 0, 0, -2, 0,.. seems to equal A091400, apart from signs. - _R. J. Mathar_, Jul 15 2010

%C Shadow transform of A002522. - _Michel Marcus_, Jun 06 2013

%C a(n) != 0 iff n in A008784. - _Joerg Arndt_, Mar 26 2014

%D M. Baake, "Solution of coincidence problem...", in R. V. Moody, ed., Math. of Long-Range Aperiodic Order, Kluwer 1997, pp. 9-44.

%D G. Shimura, Introduction to the Arithmetic Theory of Automorphic Functions, Princeton, 1971, see p. 25, Eq. (2).

%H Seiichi Manyama, <a href="/A000089/b000089.txt">Table of n, a(n) for n = 1..10000</a> (terms 1..2000 from T. D. Noe)

%H M. Baake, <a href="http://arxiv.org/abs/math/0605222">Solution of the coincidence problem in dimensions d <= 4</a>, arxiv:math/0605222 (2006)

%H M. Baake and U. Grimm, <a href="http://www.ma.utexas.edu/mp_arc-bin/mpa?yn=02-392">Quasicrystalline combinatorics</a>

%H Fell, Harriet; Newman, Morris; Ordman, Edward; <a href="http://archive.org/details/jresv67Bn1p61">Tables of genera of groups of linear fractional transformations</a>, J. Res. Nat. Bur. Standards Sect. B 67B 1963 61-68.

%H S. R. Finch and Pascal Sebah, <a href="https://arxiv.org/abs/math/0604465">Squares and Cubes Modulo n</a>, arXiv:math/0604465 [math.NT], 2006-2016.

%H John S. Rutherford, <a href="http://dx.doi.org/10.1107/S010876730804333X">Sublattice enumeration. IV. Equivalence classes of plane sublattices by parent Patterson symmetry and colour lattice group type</a>, Acta Cryst. (2009). A65, 156-163. [See Table 4].

%H N. J. A. Sloane, <a href="/transforms.txt">Transforms</a>

%H L. Toth, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL17/Toth/toth12.html">Counting Solutions of Quadratic Congruences in Several Variables Revisited</a>, J. Int. Seq. 17 (2014) # 14.11.6.

%F 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 Dirichlet series: (1+2^(-s))*Product (1+p^(-s))/(1-p^(-s)) (p=1 mod 4).

%F 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_, Aug 01 2001

%F a(3*n) = a(4*n) = a(4*n + 3) = 0. a(4*n + 1) = A031358(n). - _Michael Somos_, Mar 24 2012

%e G.f. = x + x^2 + 2*x^5 + 2*x^10 + 2*x^13 + 2*x^17 + 2*x^25 + 2*x^26 + 2*x^29 + ...

%p 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 Ward Smith_, May 22 2006

%t Array[ Function[ n, If[ EvenQ[ n ] || Mod[ n, 3 ]==2, 0, Count[ Array[ Mod[ #^2+1, n ]&, n, 0 ], 0 ] ] ], 84 ]

%t a[ n_] := If[ n < 1, 0, Length @ Select[ (#^2 + 1)/n & /@ Range[n], IntegerQ]]; (* _Michael Somos_, Aug 15 2015 *)

%t a[n_] := a[n] = Product[{p, e} = pe; Which[p<3 && e==1, 1, p==2 && e>1, 0, Mod[p, 4]==1, 2, Mod[p, 4]==3, 0, True, a[p^e]], {pe, FactorInteger[n]}]; Array[a, 105] (* _Jean-Fran├žois Alcover_, Oct 18 2018, after _David W. Wilson_ *)

%o (PARI) {a(n) = if( n<1, 0, sum( x=0, n-1, (x^2 + 1)%n==0))}; /* _Michael Somos_, Mar 24 2012 */

%o (PARI) a(n)=my(o=valuation(n,2),f);if(o>1,0,n>>=o;f=factor(n)[,1]; prod(i=1,#f,kronecker(-1,f[i])+1)) \\ _Charles R Greathouse IV_, Jul 08 2013

%o (Haskell)

%o a000089 n = product $ zipWith f (a027748_row n) (a124010_row n) where

%o f 2 e = if e == 1 then 1 else 0

%o f p _ = if p `mod` 4 == 1 then 2 else 0

%o -- _Reinhard Zumkeller_, Mar 24 2012

%Y Cf. A031358, A027748, A124010, A000095.

%K nonn,nice,mult

%O 1,5

%A _N. J. A. Sloane_

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 14 19:07 EST 2018. Contains 317214 sequences. (Running on oeis4.)