login
Number of solutions to x^2 == n (mod 2*n) for 0 <= x < 2*n.
4

%I #29 Jan 01 2023 02:29:13

%S 1,0,1,2,1,0,1,0,3,0,1,2,1,0,1,4,1,0,1,2,1,0,1,0,5,0,3,2,1,0,1,0,1,0,

%T 1,6,1,0,1,0,1,0,1,2,3,0,1,4,7,0,1,2,1,0,1,0,1,0,1,2,1,0,3,8,1,0,1,2,

%U 1,0,1,0,1,0,5,2,1,0,1,4,9,0,1,2,1,0

%N Number of solutions to x^2 == n (mod 2*n) for 0 <= x < 2*n.

%H Andrew Howroyd, <a href="/A229297/b229297.txt">Table of n, a(n) for n = 1..10000</a>

%F From _Andrew Howroyd_, Aug 07 2018: (Start)

%F Multiplicative with a(2^e) = 0 for odd e and 2^floor(e/2) for even e, and a(p^e) = p^floor(e/2) for p>=3. [corrected by _Georg Fischer_, Aug 01 2022].

%F a(n) = A000188(n) for odd n, a(2^k) = 1 + (-1)^k for k > 0. (End)

%F From _Amiram Eldar_, Jan 01 2023: (Start)

%F Dirichlet g.f.: zeta(2*s-1)*zeta(s)/(zeta(2*s)*(1+1/2^s)).

%F Sum_{k=1..n} a(k) ~ (n*log(n) + (3*gamma + log(2)/3 - 2*zeta'(2)/zeta(2) - 1)*n)*2/Pi^2, where gamma is Euler's constant (A001620). (End)

%t A[n_] := Sum[If[Mod[a^2, 2*n] == n, 1, 0], {a, 0, 2*n - 1}]; Array[A, 100]

%t f[p_, e_] := If[OddQ[e], p^((e - 1)/2), p^(e/2)]; f[2, e_] := If[OddQ[e], 0, 2^(e/2)]; a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* _Amiram Eldar_, Jan 01 2023 *)

%o (PARI) a(n)={sum(i=0, 2*n-1, i^2%(2*n)==n)} \\ _Andrew Howroyd_, Aug 06 2018

%o (PARI) a(n)={if(valuation(n,2)%2==1, 0, core(n, 1)[2])} \\ _Andrew Howroyd_, Aug 07 2018

%Y Cf. A000188, A001620, A229294, A229295, A229296.

%K nonn,mult

%O 1,4

%A _José María Grau Ribas_, Sep 22 2013