/* * A160808.c * Calculates the entries of Sloane's A160808 * * Created by Nathaniel Johnston (nathaniel@nathanieljohnston.com) * March 30, 2011 */ #include <math.h> #include <stdio.h> unsigned int prevPts = 2, numPts = 2, pt[268435455]; FILE *file; unsigned int getCoord (unsigned int pt, unsigned short coord) { unsigned short shift = 14*(coord-1); return (pt & (16383*(1 << shift))) >> shift; } unsigned char getOrien (unsigned int pt) { return (pt & (1 << 28)) >> 28; } unsigned int getPt (unsigned short x, unsigned short y, unsigned short orien) { return x | (y << 14) | (orien << 28); } unsigned char addOrien (unsigned short x, unsigned short y, unsigned short orien) { unsigned int j, nn = 0; unsigned short px, py, po; for(j=0;j<prevPts;j++) { px = getCoord(pt[j],1); py = getCoord(pt[j],2); po = getOrien(pt[j]); if(po == 1 && ((px == x && py == y+1) || (px == x && py == y-1))){ if(orien == 1)return 0;nn++; } else if(po == 0 && ((px == x-1 && py == y) || (px == x+1 && py == y))){ if(orien == 0)return 0;nn++; } } return (nn == 1); } unsigned char isOccupied (unsigned short x, unsigned short y) { unsigned int j; for(j=0;j<prevPts;j++) { if(x == getCoord(pt[j],1) && y == getCoord(pt[j],2))return 1; } return 0; } unsigned int makeSpiral (unsigned short numGens) { unsigned int j, k, f1 = 2, f2 = 2, f3, nfp = 2; int lcx = 1, lcy = 1, lco = 1, lcd = 1; int totSpir = (int)(3*log(numGens)); for(j=0;j<totSpir;j++){ f3 = f1 + f2; f1 = f2;f2 = f3; for(k=0;k<f1;k++){ if(lco==0)pt[nfp++] = getPt(8192+lcx + 2*lcd*k,8192+lcy,lco); else pt[nfp++] = getPt(8192+lcx,8192+lcy + 2*lcd*k,lco); numPts++; prevPts++; } if(lco==0){ lcx = lcx + lcd*(2*f1-1); lcy += lcd; }else{ lcx -= lcd; lcy = lcy + lcd*(2*f1-1); } if(lco==1)lcd*=-1; lco = (lco+1) % 2; } return nfp; } int main () { unsigned short xi, yi, oi, tOr, gen, maxGens; unsigned int negPts; pt[0] = getPt(8190,8192,0); pt[1] = getPt(8192,8192,0); printf("This tool will calculate the entries of Sloane's A160808.\nPlease enter the number of terms to compute (an integer from 1 to 8191). Smaller numbers will accelerate even the early computations: "); scanf("%d",&maxGens); negPts = makeSpiral(maxGens); file = fopen("b160808.txt","w"); fprintf(file,"0 0\n"); fclose(file); printf("0 0\n"); for(gen=1;gen<=maxGens;gen++){ for(xi=8189-(int)(gen/2);xi<=8189+(int)(gen/2);xi++){ for(yi=8192-(int)((gen+1)/2);yi<=8192+(int)((gen+1)/2);yi++){ tOr = isOccupied(xi,yi); for(oi=0;oi<2;oi++){ if(!tOr && addOrien(xi,yi,oi))pt[numPts++]=getPt(xi,yi,oi); } } } file = fopen("b160808.txt","a"); fprintf(file,"%d %d\n",gen,numPts-negPts); fclose(file); printf("%d %d\n",gen,numPts-negPts); prevPts = numPts; } printf("Done!"); getchar(); return 0; }