// Author: Manfred Scheucher // Date : 05.06.2015 // Note : this code is just a C-implementation of my python code #include <stdio.h> #include <stdlib.h> #include <assert.h> #define MAXN 32 #define GCD(a,b) GCD_[a][b] int n; long ct = 0; int F[MAXN]; int G[MAXN]; int GCD_[MAXN][MAXN]; int gcd(int a, int b) { if(a < b) return gcd(b,a); if(b==0) return a; else return gcd(a%b,b); } inline int valid(int x) { int y,d,r; memcpy(G,F,sizeof(int)*(n+1)); for(y=x;y>=1;y--) // reversed seems to be a bit faster (?) { d = GCD(x,y); r = GCD(G[x],G[y]); if(G[d]==0) { G[d] = r; } else { if(G[d]!=r) return 0; } } return 1; } void enum_(int x) { int y; if(!valid(x)) return; if(x==n) { ct++; } else { for(y=1;y<=n;y++) { F[x+1] = y; enum_(x+1); } } } int main(int argc, char** argv) { n = atoi(argv[1]); assert(n<MAXN); // init F with zeros int x,y; for(x=1;x<=n;x++) F[x]=0; // precalc GCD function for(x=0;x<MAXN;x++) { for(y=0;y<MAXN;y++) { GCD_[x][y] = gcd(x,y); } } enum_(0); printf("%d %ld\n",n,ct); }