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
(Python)
from math import prod
from sympy import primefactors
def A000089(n): return prod(1 if p==2 else 2 if p&3==1 else 0 for p in primefactors(n)) if n&3 else 0 # Chai Wah Wu, Oct 13 2024
CROSSREFS
KEYWORD
nonn,nice,mult
AUTHOR
STATUS
approved