A155918 Number of squared hypotenuses mod n in two dimensions.

1, 2, 3, 3, 5, 6, 7, 5, 7, 10, 11, 9, 13, 14, 15, 9, 17, 14, 19, 15, 21, 22, 23, 15, 25, 26, 21, 21, 29, 30, 31, 17, 33, 34, 35, 21, 37, 38, 39, 25, 41, 42, 43, 33, 35, 46, 47, 27, 43, 50, 51, 39, 53, 42, 55, 35, 57, 58, 59, 45, 61, 62, 49, 33, 65, 66, 67, 51, 69, 70, 71, 35, 73

Offset: 1

Author

Steven Finch, Jan 30 2009

Keywords

• mult
• nonn

Comments

Number of images of the map (x,y) -> x^2+y^2 in Z_n.

Let n = p^e and k = r*p^b (gcd(r,p) = 1). If p == 1 (mod 4), then x^2 + y^2 == k (mod p) always have solutions; if p == 3 (mod 4), then x^2 + y^2 == k (mod p) is solvable if and only if b is even or b >= e; if p = 2, then x^2 + y^2 == k (mod p) is solvable if and only if r == 1 (mod 4) or b >= e - 1. If 0 <= k < n, then the number of solutions to x^2 + y^2 == k (mod n) is A305191(n,k). - Jianing Song, Apr 20 2019

Links

• Jianing Song, Table of n, a(n) for n = 1..10000 (first 1000 terms from Michel Marcus)

Crossrefs

Cf. A305191, A334427, A334448.

Programs

Mathematica

(For[v = Table[0, {m, 1, n^2}]; m = 1; i = 0, i < n, i++, For[j = 0, j < n, j++, v[[m]] = Mod[i^2 + j^2, n]; m = m + 1]]; Length[Union[v]])
(* Second program: *)
a[n_] := Module[{p, e}, Product[{p, e} = pe; Which[Mod[p, 4] == 1, p^e, Mod[p, 4] == 3, Ceiling[p^(e+1)/(p+1)], p == 2, 2^(e-1) + 1, True, p], {pe, FactorInteger[n]}]];
Array[a, 100] (* Jean-François Alcover, Jul 30 2020 *)

PARI

a(n) = #Set(vector(n^2, i, ((i%n)^2 + (i\n)^2) % n)); \\ Michel Marcus, Jul 08 2017

PARI

a(n)=
{
    my(r=1, f=factor(n));
    for(j=1, #f[, 1], my(p=f[j, 1], e=f[j, 2]);
        if(p==2, r*=2^(e-1)+1);
        if(p%4==1, r*=p^e);
        if(p%4==3, r*=ceil(p^(e+1)/(p+1)));
    );
    return(r);
} \\ Jianing Song, Apr 20 2019

Formula

Multiplicative with a(p^e) = p^e if p == 1 (mod 4); ceiling(p^(e+1)/(p+1)) if p == 3 (mod 4); 2^(e-1) + 1 if p = 2. - Jianing Song, Apr 20 2019

Sum_{k=1..n} a(k) ~ c * n^2, where c = (11/24) * Product_{p prime == 3 (mod 4)} (1 - 1/p^3)/(1 - 1/p^4) = (11/24) * A334427/A334448 = 0.44532386516028771931... . - Amiram Eldar, Feb 17 2024