/* * A159944.c * Calculates the entries of Sloane's A159944 (counting convex kites on an n X n grid distinct up to congruence) * * Created by Nathaniel Johnston (nathaniel@nathanieljohnston.com) * May 11, 2011 */ #include <math.h> #include <stdio.h> unsigned long long numPts; unsigned char pt[256][256]; unsigned int kiteArr[100000][3]; FILE *file; unsigned char hasKite (unsigned int sd1, unsigned int sd2, unsigned int ang1, unsigned int ang2) { unsigned int j; for(j=0;j<numPts;j++){ if((kiteArr[j][2]==ang1 || kiteArr[j][2]==ang2) && ((kiteArr[j][0]==sd1 && kiteArr[j][1]==sd2) || (kiteArr[j][0]==sd2 && kiteArr[j][1]==sd1)))return 1; } return 0; } unsigned char isKite (unsigned short a1, unsigned short a2, unsigned short b1, unsigned short b2, unsigned short c1, unsigned short c2, unsigned short d1, unsigned short d2) { int s11,s12,s21,s22,s31,s32,s41,s42,t11,t12,t21,t22,t31,t32,t41,t42; unsigned int sd1,sd2,ang1,ang2; s11 = b1-a1; s12 = b2-a2; s21 = d1-b1; s22 = d2-b2; s31 = c1-d1; s32 = c2-d2; s41 = a1-c1; s42 = a2-c2; t11 = b1-a1; t12 = b2-a2; t21 = c1-b1; t22 = c2-b2; t31 = d1-c1; t32 = d2-c2; t41 = a1-d1; t42 = a2-d2; unsigned int j,k; if((s11*s22 != s12*s21) && (s31*s22 != s32*s21) && (s31*s42 != s32*s41) && (s11*s42 != s12*s41) && ((s11*s11+s12*s12==s21*s21+s22*s22 && s31*s31+s32*s32==s41*s41+s42*s42) || (s31*s31+s32*s32==s21*s21+s22*s22 && s11*s11+s12*s12==s41*s41+s42*s42)) && fabs(2*M_PI - (acos((s11*s21 + s12*s22)/sqrt((s11*s11 + s12*s12)*(s21*s21 + s22*s22))) + acos((s21*s31 + s22*s32)/sqrt((s21*s21 + s22*s22)*(s31*s31 + s32*s32))) + acos((s31*s41 + s32*s42)/sqrt((s31*s31 + s32*s32)*(s41*s41 + s42*s42))) + acos((s41*s11 + s42*s12)/sqrt((s41*s41 + s42*s42)*(s11*s11 + s12*s12))))) < 0.0001){ sd1 = s11*s11+s12*s12; if(s21*s21+s22*s22 != sd1){sd2=s21*s21+s22*s22;ang1=s11*s41+s12*s42;ang2=s21*s31+s22*s32;}else{sd2=s31*s31+s32*s32;ang1=s11*s21+s12*s22;ang2=s31*s41+s32*s42;} if(hasKite(sd1,sd2,ang1,ang2))return 0; else{ kiteArr[numPts][0] = sd1; kiteArr[numPts][1] = sd2; kiteArr[numPts][2] = ang1; return 1; } } if((t11*t22 != t12*t21) && (t31*t22 != t32*t21) && (t31*t42 != t32*t41) && (t11*t42 != t12*t41) && ((t11*t11+t12*t12==t21*t21+t22*t22 && t31*t31+t32*t32==t41*t41+t42*t42) || (t31*t31+t32*t32==t21*t21+t22*t22 && t11*t11+t12*t12==t41*t41+t42*t42)) && fabs(2*M_PI - (acos((t11*t21 + t12*t22)/sqrt((t11*t11 + t12*t12)*(t21*t21 + t22*t22))) + acos((t21*t31 + t22*t32)/sqrt((t21*t21 + t22*t22)*(t31*t31 + t32*t32))) + acos((t31*t41 + t32*t42)/sqrt((t31*t31 + t32*t32)*(t41*t41 + t42*t42))) + acos((t41*t11 + t42*t12)/sqrt((t41*t41 + t42*t42)*(t11*t11 + t12*t12))))) < 0.0001){ sd1 = t11*t11+t12*t12; if(t21*t21+t22*t22 != sd1){sd2=t21*t21+t22*t22;ang1=t11*t41+t12*t42;ang2=t21*t31+t22*t32;}else{sd2=t31*t31+t32*t32;ang1=t11*t21+t12*t22;ang2=t31*t41+t32*t42;} if(hasKite(sd1,sd2,ang1,ang2))return 0; else{ kiteArr[numPts][0] = sd1; kiteArr[numPts][1] = sd2; kiteArr[numPts][2] = ang1; return 1; } } return 0; } int main () { unsigned short a, b, c, d, a1, a2, b1, b2, c1, c2, d1, d2, maxsz, sz, sz2; printf("This tool will calculate the entries of Sloane's A159944 (number of convex kites on an n X n grid distinct up to congruence).\nPlease enter the number of terms to compute (an integer from 1 to 255): "); scanf("%d",&maxsz); numPts = 0; file = fopen("b159944.txt","w"); fprintf(file,"1 0\n"); fclose(file); printf("1 0\n"); for(sz=2;sz<=maxsz;sz++){ numPts = 0; sz2 = sz*sz; for(a=0;a<=floor(sz/2);a++){ a1 = a % sz; a2 = floor(a/sz); for(b=a+1;b<sz2;b++){ b1 = b % sz; b2 = floor(b/sz); for(c=b+1;c<sz2;c++){ c1 = c % sz; c2 = floor(c/sz); for(d=c+1;d<sz2;d++){ if(isKite(a1, a2, b1, b2, c1, c2, d % sz, floor(d/sz))){ numPts++; } } } } } file = fopen("b159944.txt","a"); fprintf(file,"%d %d\n",sz,numPts); fclose(file); printf("%d %d\n",sz,numPts); } printf("Done!"); getchar(); return 0; }