|
%I #27 Nov 21 2023 05:27:13
%S 1,2,2,4,6,4,8,0,6,12,10,8,14,16,12,0,16,12,18,24,16,20,24,0,30,28,18,
%T 32,30,24,32,0,20,32,48,24,38,36,28,0,40,32,42,40,36,48,48,0,56,60,32,
%U 56,54,36,60,0,36,60,58,48,62,64,48,0,84,40,66,64,48,96
%N Number of non-congruent solutions to x^2 + 2y^2 == -1 (mod n).
%H Andrew Howroyd, <a href="/A089002/b089002.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^e for e <= 2, a(2^e) = 0 for e > 2, a(p^e) = (p-1)*p^(e-1) for p-2 mod 8 = +-1, a(p^e) = (p+1)*p^(e-1) for p-2 mod 8 = +-3. - _Andrew Howroyd_, Jul 15 2018
%F Sum_{k=1..n} a(k) ~ c * n^2, where c = 7/(16*A309710) = 0.410900684788977656... . - _Amiram Eldar_, Nov 21 2023
%t f[2, e_] := If[e < 3, 2^e, 0]; f[p_, e_] := If[MemberQ[{1, 7}, Mod[p - 2, 8]], (p - 1), (p + 1)] * p^(e - 1); a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* _Amiram Eldar_, Sep 11 2020 *)
%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-2*i)%n + 1])} \\ _Andrew Howroyd_, Jul 09 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>2, 0, 2^e), p^(e-1)*if(abs(p%8-2)==1, p-1, p+1)))} \\ _Andrew Howroyd_, Jul 09 2018
%Y Cf. A088965, A086932, A309710.
%K mult,nonn,easy
%O 1,2
%A Yuval Dekel (dekelyuval(AT)hotmail.com), Nov 02 2003
|
