|
%I #95 Oct 11 2022 07:41:09
%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
%C For n > 1, number of positive solutions to n = a^2 + b^2 such that gcd(a, b) = 1. - _Haehun Yang_, Mar 20 2022
%D 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.
%D Goro 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 Michael Baake, <a href="http://arxiv.org/abs/math/0605222">Solution of the coincidence problem in dimensions d <= 4</a>, arxiv:math/0605222 [math.MG] (2006).
%H Michael Baake and Uwe Grimm, <a href="http://www.ma.utexas.edu/mp_arc-bin/mpa?yn=02-392">Quasicrystalline combinatorics</a>, 2002.
%H Harriet Fell, Morris Newman, and Edward Ordman, <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 Steven 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ászló Tóth, <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), Article 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 g.f.: (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
%F Asymptotic mean: Limit_{m->oo} (1/m) * Sum_{k=1..m} a(k) = 3/(2*Pi) = 0.477464... (A093582). - _Amiram Eldar_, Oct 11 2022
%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, A006278 (positions of records), A002654, A093582.
%K nonn,nice,mult
%O 1,5
%A _N. J. A. Sloane_
|
