GCD array

(See also page950.) There are various deviations from perfect randomness. The density of white squares is asymptotically6/π²≃ 0.61. (The probability fors randomly chosen integers to be relatively prime is1/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 offsetsv is given ins 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]]]/p^s], {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 rown the number of white squares encountered before reaching the leading diagonal isEulerPhi[n]. This function is shown below. Its computation is known in general to be equivalent in difficulty to factoringn (see page1090).GCD can be computed using Euclid's algorithm as discussed on page915.