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). 15
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, 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, 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 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,5

COMMENTS

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

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

Shadow transform of A002522. - Michel Marcus, Jun 06 2013

a(n) != 0 iff n in A008784. - Joerg Arndt, Mar 26 2014

REFERENCES

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

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

LINKS

T. D. Noe, Table of n, a(n) for n = 1..2000

M. Baake and U. Grimm, Quasicrystalline combinatorics

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.

S. R. Finch and Pascal Sebah, Squares and Cubes Modulo n (arXiv:math.NT/0604465).

John S. Rutherford, Sublattice enumeration. IV. Equivalence classes of plane sublattices by parent Patterson symmetry and colour lattice group type, Acta Cryst. (2009). A65, 156-163. [See Table 4].

N. J. A. Sloane, Transforms

FORMULA

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.

Dirichlet series: (1+2^(-s))*Product (1+p^(-s))/(1-p^(-s)) (p=1 mod 4).

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

a(3*n) = a(4*n) = a(4*n + 3) = 0. a(4*n + 1) = A031358(n). - Michael Somos, Mar 24 2012

EXAMPLE

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 + ...

MAPLE

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

MATHEMATICA

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

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

PROG

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

(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

(Haskell)

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

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

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

-- Reinhard Zumkeller, Mar 24 2012

CROSSREFS

Cf. A031358, A027748, A124010, A000095.

Sequence in context: A001343 A022882 A171919 * A051907 A178176 A093569

Adjacent sequences:  A000086 A000087 A000088 * A000090 A000091 A000092

KEYWORD

nonn,nice,mult

AUTHOR

N. J. A. Sloane

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy .

Last modified July 30 23:28 EDT 2016. Contains 275189 sequences.