|
|
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
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
|
|
|
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
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
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,nice,mult
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|