cp's OEIS Frontend

A189412 Number of concave quadrilaterals on an n X n grid (or geoboard).

%I A189412 #33 Feb 16 2025 08:33:14
%S A189412 0,0,24,720,6300,34812,135552,436944,1198968,2929656,6516984,13502448,
%T A189412 26208516,48407988,85481280,145200888,238502808,380729160,591761304,
%U A189412 899049096,1336994100,1950873276,2798226336,3952174032,5500597632,7555866072,10253438688
%N A189412 Number of concave quadrilaterals on an n X n grid (or geoboard).
%H A189412 Michal Forišek, <a href="/A189412/b189412.txt">Table of n, a(n) for n = 1..50</a>
%H A189412 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/ConcavePolygon.html">Concave Polygon</a>.
%H A189412 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Quadrilateral.html">Quadrilateral</a>.
%o A189412 (Python)
%o A189412 def gcd(x, y):
%o A189412   x, y = abs(x), abs(y)
%o A189412   while y: x, y = y, x%y
%o A189412   return x
%o A189412 def concave(N):
%o A189412   V = [ (r, c) for r in range(-N+1, N) for c in range(N) if (c>0 or r>0) ]
%o A189412   answer = 0
%o A189412   for i in range(len(V)):
%o A189412     for j in range(i):
%o A189412       r1, c1, r2, c2 = V[i]+V[j]
%o A189412       rr, cr, ta = N-max(r1, r2, 0)+min(r1, r2, 0), N-max(c1, c2), abs(r1*c2-r2*c1)
%o A189412       if rr>0 and cr>0 and ta>0:
%o A189412         answer += 3*rr*cr*(ta+2-gcd(r1, c1)-gcd(r2, c2)-gcd(r1-r2, c1-c2))/2
%o A189412   return answer
%o A189412 for N in range(1, 28):
%o A189412     print(int(concave(N)), end=', ')
%Y A189412 Cf. A175383, A189345, A189413, A189414.
%K A189412 nonn
%O A189412 1,3
%A A189412 _Martin Renner_, Apr 21 2011
%E A189412 a(6)-a(22) from _Nathaniel Johnston_, Apr 25 2011
%E A189412 Terms a(7)-a(22) corrected by _Michal Forisek_, Sep 06 2011
%E A189412 Terms a(23)-a(50) added by _Michal Forisek_, Sep 06 2011