A316985 Number of solutions to x^2 + y^2 - z^2 == 1 (mod n).

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

Robert Israel, Table of n, a(n) for n = 1..10000

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

Cf. A087784, A227553, A229179.

Sequence in context: A286040 A332608 A177464 * A353789 A273315 A301100

Adjacent sequences: A316982 A316983 A316984 * A316986 A316987 A316988

Keyword

nonn,mult

Author

Andrew Howroyd, Jul 18 2018

Status

approved