%I #27 Oct 23 2023 02:01:28
%S 1,0,0,0,2,0,0,0,0,0,0,0,2,0,0,0,2,0,0,0,0,0,0,0,2,0,0,0,2,0,0,0,0,0,
%T 0,0,2,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,2,0,0,0,4,0,0,0,
%U 0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0,4,0,0
%N Number of coincidence site lattices of index n in square lattice.
%C A coincidence site lattice (CSL), or coincidence sublattice, is a full-rank sublattice arising as an intersection of the parent lattice with its copy rotated around the origin. It is necessarily primitive.
%C A primitive sublattice of the square lattice is a CSL if it is square (i. e., similar to the parent lattice) and has odd index.
%C In this sequence, any two CSLs differing by any isometry are counted as distinct.
%C a(n) is also the number of ordered pairs of coprime integers (p, q) with p >= 0 and q > 0 such that p^2 + q^2 = n^2.
%H Amiram Eldar, <a href="/A350872/b350872.txt">Table of n, a(n) for n = 1..10000</a>
%H Michael Baake and Peter Zeiner, <a href="https://arxiv.org/abs/1709.07317">Geometric enumeration problems for lattices and embedded Z-modules</a>, arXiv:1709.07317 [math.MG], 2017; in: <a href="http://www.aperiodicorder.org">Aperiodic Order</a>, vol. 2: Crystallography and Almost Periodicity, eds. M. Baake and U. Grimm, Cambridge University Press, Cambridge (2017), pp. 73-172.
%H <a href="/index/Sq#sqlatt">Index entries for sequences related to square lattice</a>.
%H <a href="/index/Su#sublatts">Index entries for sequences related to sublattices</a>.
%F Multiplicative with a(p^e) = 2 if p == 1 (mod 4), otherwise 0.
%F a(4*n+1) = A031358(n), other terms are 0.
%F a(n) = 2 * A024362(n) for n > 1.
%F Dirichlet convolution of A000089 and A154269.
%F Dirichlet convolution of A338690 and A271102.
%F From _Amiram Eldar_, Oct 23 2023: (Start)
%F Dirichlet g.f.: Product_{primes p == 1 (mod 4)} (1 + 1/p^s)/(1 - 1/p^s).
%F Sum_{k=1..n} a(k) = (1/Pi) * n + O(sqrt(n)*log(n)).
%F (both from Baake and Zeiner, 2017) (End)
%e a(5) = 2 index-5 CSLs have bases (2, 1), (-1, 2) and (1, 2), (-2, 1).
%t csl[1] = 1;
%t csl[n_] := With[{f = First@Transpose@FactorInteger@n}, If[Union@Mod[f, 4] == {1}, 2^Length@f, 0]];
%t Array[csl, 87]
%o (PARI) a(n) = {my(f = factor(n)); prod(i = 1, #f~, if(f[i, 1]%4 == 1, 2, 0));} \\ _Amiram Eldar_, Oct 23 2023
%Y Cf. A031358 (nonzero quadrisection), A004613 (positions of nonzero terms), A024362, A154269, A338690, A271102.
%Y Cf. enumeration of wider classes of sublattices of Z^2: A000203 (all sublattices), A350871 (all well-rounded sublattices), A002654 (all square sublattices), A001615 (all primitive sublattices), A000089 (all primitive square sublattices).
%Y Cf. enumeration of CSLs in other lattices: A331140 (Z^4), A331139 (D_4), A331142 (A_4).
%K nonn,mult
%O 1,5
%A _Andrey Zabolotskiy_, Jan 20 2022