A373749 Triangle read by rows: T(n, k) = MOD(k^2, n) where MOD(a, n) = a if n = 0 and otherwise a - n*floor(a/n). (Quadratic residue.)

0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 4, 4, 1, 0, 0, 1, 4, 3, 4, 1, 0, 0, 1, 4, 2, 2, 4, 1, 0, 0, 1, 4, 1, 0, 1, 4, 1, 0, 0, 1, 4, 0, 7, 7, 0, 4, 1, 0, 0, 1, 4, 9, 6, 5, 6, 9, 4, 1, 0, 0, 1, 4, 9, 5, 3, 3, 5, 9, 4, 1, 0, 0, 1, 4, 9, 4, 1, 0, 1, 4, 9, 4, 1, 0

Offset: 0

Author

Peter Luschny, Jun 23 2024

Keywords

• nonn
• tabl

Comments

The definition of the binary operation MOD in the name follows CMath (Graham et al.) and Bach & Shallit. This is important because some CAS unfortunately do not follow this definition and throw a 'division by zero' error if n = 0.

Row n reduced to a set is the set of the quadratic residues mod n.

Examples

			Triangle starts:
  [0] 0;
  [1] 0, 0;
  [2] 0, 1, 0;
  [3] 0, 1, 1, 0;
  [4] 0, 1, 0, 1, 0;
  [5] 0, 1, 4, 4, 1, 0;
  [6] 0, 1, 4, 3, 4, 1, 0;
  [7] 0, 1, 4, 2, 2, 4, 1, 0;
  [8] 0, 1, 4, 1, 0, 1, 4, 1, 0;
  [9] 0, 1, 4, 0, 7, 7, 0, 4, 1, 0;
 [10] 0, 1, 4, 9, 6, 5, 6, 9, 4, 1, 0;
		

References

• Eric Bach and Jeffrey Shallit, Algorithmic Number Theory, p. 21.
• R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, Addison-Wesley, 2nd ed., pp. 81f.

Crossrefs

Variants: A048152, A096008.

Cf. A048153 (row sums), A373750 (middle terms).

Programs

Julia

Mod(n, k) = k == 0 ? n : mod(n, k)
T(n, k) = Mod(k^2, n)
for n in 0:10
    [T(n, k) for k in 0:n] |> println
end

Maple

REM := (n, k) -> ifelse(k = 0, n, irem(n, k)):
T := n -> local k; seq(REM(k^2, n), k = 0..n):
seq(T(n), n = 0..12);

Mathematica

MOD[n_, k_] := If[k == 0, n, Mod[n, k]];
Table[MOD[k^2, n], {n, 0, 10}, {k, 0, n}]

SageMath

def A373749(n, k): return mod(k^2, n)
for n in range(11): print([A373749(n, k) for k in range(n + 1)])