login
A316985
Number of solutions to x^2 + y^2 - z^2 == 1 (mod n).
1
1, 4, 12, 24, 30, 48, 56, 128, 108, 120, 132, 288, 182, 224, 360, 512, 306, 432, 380, 720, 672, 528, 552, 1536, 750, 728, 972, 1344, 870, 1440, 992, 2048, 1584, 1224, 1680, 2592, 1406, 1520, 2184, 3840, 1722, 2688, 1892, 3168, 3240, 2208, 2256, 6144, 2744, 3000
OFFSET
1,2
LINKS
László Tóth, Counting Solutions of Quadratic Congruences in Several Variables Revisited, J. Int. Seq. 17 (2014), Article 14.11.6.
FORMULA
Multiplicative with a(2^1) = 4, a(2^2) = 24, a(2^e) = 2^(2*e+1) for e > 2, a(p^e) = (p+1)*p^(2*e-1) for odd prime p.
a(n) = n^2*Sum_{d|n} mu(d)^2/d for n odd.
a(n) = A229179(n) for n mod 4 <> 0.
Sum_{k=1..n} a(k) ~ c * n^3, where c = 19/(4*Pi^2) = 0.4812756... . - Amiram Eldar, Oct 18 2022
MAPLE
g:= proc(t)
if t[1]=2 then 2^(2*t[2]+1)
else (t[1]+1)*t[1]^(2*t[2]-1)
fi
end proc:
g([2, 1]):= 4: g([2, 2]):= 24:
seq(convert(map(g, ifactors(n)[2]), `*`), n=1..100); # Robert Israel, Jul 20 2018
MATHEMATICA
a[n_] := a[n] = If[PrimeQ[n], n(n+1), Times @@ (Which[#[[1]] == 2 && #[[2]] == 1, 4, #[[1]] == 2 && #[[2]] == 2, 24, #[[1]] == 2, 2^(2 #[[2]]+1), True, (#[[1]]+1) #[[1]]^(2 #[[2]]-1)]& /@ FactorInteger[n])]; a[1] = 1; a[2] = 4; Array[a, 50] (* Jean-François Alcover, Jul 25 2018 and slightly modified by Robert G. Wilson v, Jul 25 2018 *)
PROG
(PARI)
M(n, f)={sum(i=0, n-1, Mod(x^(f(i)%n), x^n-1))}
a(n)={polcoeff(lift(M(n, i->i^2)^2 * M(n, i->-(i^2)) ), 1%n)}
(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, 2^(2*e+1), if(e==1, 4, 24)), (p+1)*p^(2*e-1)))}
CROSSREFS
KEYWORD
nonn,mult
AUTHOR
Andrew Howroyd, Jul 18 2018
STATUS
approved