|
%I #18 Oct 18 2022 07:27:00
%S 1,2,4,0,4,8,8,0,12,8,12,0,12,16,16,0,16,24,20,0,32,24,24,0,20,24,36,
%T 0,28,32,32,0,48,32,32,0,36,40,48,0,40,64,44,0,48,48,48,0,56,40,64,0,
%U 52,72,48,0,80,56,60,0,60,64,96,0,48,96,68,0,96,64,72,0,72,72,80,0,96,96
%N Number of non-congruent solutions of x^2 + y^2 == -1 (mod n).
%H Andrew Howroyd, <a href="/A086932/b086932.txt">Table of n, a(n) for n = 1..10000</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 Multiplicative, with a(2^e) = 2 if e = 1 or 0 if e > 1, a(p^e) = (p-1)p^(e-1) if p == 1 (mod 4), a(p^e) = (p+1)p^(e-1) if p == 3 (mod 4). - _Vladeta Jovovic_, Sep 24 2003
%F Sum_{k=1..n} a(k) ~ c * n^2, where c = 3/(8*G) = 0.409404..., where G is Catalan's constant (A006752). - _Amiram Eldar_, Oct 18 2022
%t a[n_] := If[n == 1, 1, Module[{p, e}, Product[{p, e} = pe; Which[p == 2 && e == 1, 2, p == 2 && e > 1, 0, Mod[p, 4] == 1, (p - 1) p^(e - 1), Mod[p, 4] == 3, (p + 1) p^(e - 1)], {pe, FactorInteger[n]}]]];
%t a /@ Range[1, 100] (* _Jean-François Alcover_, Sep 14 2019 *)
%o (PARI) a(n)={my(v=vector(n)); for(i=0, n-1, v[i^2%n + 1]++); sum(i=0, n-1, v[i+1]*v[(-1-i)%n + 1])} \\ _Andrew Howroyd_, Jul 15 2018
%o (PARI) a(n)={my(f=factor(n)); prod(i=1, #f~, my(p=f[i,1], e=f[i,2]); if(p==2, if(e>1, 0, 2), p^(e-1)*if(p%4==1, p-1, p+1)))} \\ _Andrew Howroyd_, Jul 15 2018
%Y Cf. A060968, A006752.
%K mult,nonn
%O 1,2
%A Yuval Dekel (dekelyuval(AT)hotmail.com), Sep 21 2003
%E More terms from _John W. Layman_, Sep 25 2003
|
