The OEIS is supported by the many generous donors to the OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A000089 Number of solutions to x^2 + 1 == 0 (mod n). 31
 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 For n > 1, number of positive solutions to n = a^2 + b^2 such that gcd(a, b) = 1. - Haehun Yang, Mar 20 2022 REFERENCES Michael Baake, "Solution of the coincidence problem in dimensions d <= 4", in R. V. Moody, ed., Mathematics of Long-Range Aperiodic Order, Kluwer, 1997, pp. 9-44. Goro Shimura, Introduction to the Arithmetic Theory of Automorphic Functions, Princeton, 1971, see p. 25, Eq. (2). LINKS Seiichi Manyama, Table of n, a(n) for n = 1..10000 (terms 1..2000 from T. D. Noe) Michael Baake, Solution of the coincidence problem in dimensions d <= 4, arxiv:math/0605222 [math.MG] (2006). Michael Baake and Uwe Grimm, Quasicrystalline combinatorics, 2002. Harriet Fell, Morris Newman, and Edward Ordman, Tables of genera of groups of linear fractional transformations, J. Res. Nat. Bur. Standards Sect. B 67B 1963 61-68. Steven R. Finch and Pascal Sebah, Squares and Cubes Modulo n, arXiv:math/0604465 [math.NT], 2006-2016. 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 László Tóth, Counting Solutions of Quadratic Congruences in Several Variables Revisited, J. Int. Seq. 17 (2014), Article 14.11.6. 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 g.f.: (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 Asymptotic mean: Limit_{m->oo} (1/m) * Sum_{k=1..m} a(k) = 3/(2*Pi) = 0.477464... (A093582). - Amiram Eldar, Oct 11 2022 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 *) 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 *) 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, A006278 (positions of records), A002654, A093582. Sequence in context: A001343 A022882 A171919 * A339430 A350386 A352550 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 | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified February 27 21:03 EST 2024. Contains 370378 sequences. (Running on oeis4.)