cp's OEIS Frontend

A372218 a(n) is the number of ways to select three distinct points of an n X n grid forming a triangle whose sides do not pass through a grid point.

%I A372218 #21 Jun 17 2024 15:25:29
%S A372218 0,4,36,184,592,1828,4164,9360,18592,34948,59636,102096,161496,255700,
%T A372218 385292,562336,796344,1131996,1552780,2133368,2855632,3765492,4876444,
%U A372218 6328104,8049744,10203820,12766508,15870744,19496392,23984444,29090340,35318968,42535496,50936036
%N A372218 a(n) is the number of ways to select three distinct points of an n X n grid forming a triangle whose sides do not pass through a grid point.
%C A372218 a(n) is 1/6 of the number of ways to select three points (x,y), (u,v), (p,q) with gcd(x-u,y-v) = gcd(u-p,v-q) = gcd(p-x,q-y) = 1 and 0 <= x, y, u, v, p, q <= n in an n X n grid.
%H A372218 Felix Huber, <a href="/A372218/a372218.pdf">Illustration of a(2)</a>
%e A372218 See the linked illustration: a(2) = 36 because there are 36 ways to select three distinct points in a square grid with side length n that satisfy the condition.
%p A372218 A372218:=proc(n)
%p A372218   local x,y,u,v,p,q,a;
%p A372218   a:=0;
%p A372218   for x from 0 to n do
%p A372218     for y from 0 to n do
%p A372218       for u from 0 to n do
%p A372218         for v from 0 to n do
%p A372218           if gcd(x-u,y-v)=1 then
%p A372218             for p from 0 to n do
%p A372218               for q from 0 to n do
%p A372218                 if gcd(x-p,y-q)=1 and gcd(p-u,q-v)=1 then a:=a+1 fi;
%p A372218               od;
%p A372218             od;
%p A372218           fi;
%p A372218         od;
%p A372218       od;
%p A372218     od;
%p A372218   od;
%p A372218   a:=a/6;
%p A372218   return a;
%p A372218 end proc;
%p A372218 seq(A372218(n),n=0..33);
%Y A372218 Cf. A115004, A141224, A141255, A320540, A320541, A320544, A372217.
%K A372218 nonn
%O A372218 0,2
%A A372218 _Felix Huber_, Apr 28 2024