GCD array
(See also page 950.) There are various deviations from perfect randomness. The density of white squares is asymptotically 6/π2 ≃ 0.61. (The probability for s randomly chosen integers to be relatively prime is 1/Zeta[s].) No 2 × 2 or larger block of white squares can ever occur. An arrangement of black squares with any list of relative offsets will always eventually occur. (This follows from the Chinese Remainder Theorem.) The first 2 × 2 block of black squares occurs at {14, 20}, the first 3 × 3 block at {1274, 1308} and the first 4 × 4 block at {7247643,10199370}. The densities of such blocks are respectively about 0.002, 2 × 10-6 and 10-14. In general the density for an arrangement of white squares with offsets v is given in s dimensions by (no simple closed formula seems to exist except for the 1 × 1 case)
Product[With[{p = Prime[n]}, 1 - Length[Union[Mod[v, p]]]/ps], {n, ∞}]
White squares correspond to lattice points that are directly visible from the origin at the top left of the picture, so that lines to them do not pass through any other integer points. On row n the number of white squares encountered before reaching the leading diagonal is EulerPhi[n]. This function is shown below. Its computation is known in general to be equivalent in difficulty to factoring n (see page 1090). GCD can be computed using Euclid's algorithm as discussed on page 915.