# Sum of squares mod n uniformly distributed

Let s be an integer equal to at least 5 and let n be a positive integer.

Look at all tuples ofÂ s integers, each integer being between 0 and n-1 inclusive, and look at the sum of their squares mod n. About 1/n will fall into each possible value.

So, for example, if you look at a lists of 6 digits, sum the squares of the digits in each list, then about 1/10 of the results will end in 0, about 1/10 will end in 1, about 1/10 will end in 2, etc.

This is the gist of a theorem discussed on Math Overflow here.

And here is Python code to demonstrate it.

```    from itertools import product

n = 10
s = 6

counts = [0]*n
for p in product(range(n), repeat=s):
counts[ sum(x**2 for x in p) % n ] += 1

print(counts)
```

The result is

```    [103200, 99200, 99200, 99200, 99200,
103200, 99200, 99200, 99200, 99200]```

and so between 99,200 and 103,200 sums end in each digit.

Let’s run it again with n = 11 and s = 5. Now we get

```    [14641, 14762, 14520, 14762, 14762, 14762,
14520, 14520, 14520, 14762, 14520]```

which shows the counts are between 14,520 and 14,762. If they were perfectly uniformly distributed we’d expect 114 = 14,641 in each bin. The maximum deviation from a uniform distribution is 0.83%.

The code becomes impractical as s or n get larger, but we can try s = 7 and keep n = 11. Then we get a maximum deviation from uniformity of 0.075%, i.e. about 10 times closer to being uniform.