// A308468 - "Trapezoidal numbers": numbers k such that the integers from 1 to k can be arranged in // a trapezoid of H lines containing respectively L, L-1, L-2, ..., L-H+1 numbers from top to bottom. // The rule is that from the second line, each integer is equal to the absolute value of the // difference between the two numbers above it. // C++ program by Bert Dobbelaere #include <cstdio> #include <cassert> #include <cstring> // Max problem dimensions #define MAXK 100 #define MAXL 32 #define MAXH 16 #define SKIP_ODD_K_SEARCH // comment out to show odd value solutions // #define SHOW_ALL_SOLUTIONS // uncomment if needed // Current problem dimensions int K, H, L; // Playing field and 'used' markers. int c[MAXH][MAXL]; bool isused[MAXK+1]; // Set H and return true iff we can arrange n numbers in a trapezoid of width l. bool findH(int n, int l) { H=2; n-= 2*l - 1; l-=2; while((n>0) && (l>0)) { n-=l; H++; l--; } return (n==0); } // Absolute difference int diff(int a, int b) { return (a>b) ? a-b : b-a; } void dumpSolution() { assert(L>0); if(c[0][0]>c[0][L-1]) return; // We already encountered a symmetric solution - don't report. for(int h=0;h<H;h++) { for(int i=0;i<h;i++) printf(" "); for(int l=0;l<(L-h);l++) printf("%2d ",c[h][l]); printf("\n"); } printf("\n"); } // Recursive core routine: attempt to add an element to the top row and its implied differences on the other rows // 'lvl' is the number of elements that are already filled. // returns true iff one or more solutions were found bool solve(int lvl) { bool found=false;; if(lvl==L) { dumpSolution(); return true; } for(int v=1;v<=K;v++) if(!isused[v]) { c[0][lvl]=v; // Fill top row number isused[v]=true; int h=1; int l=lvl-1; bool ok=true; while((h<H) && (l>=0)) // Fill differences and mark them 'used' { int d=diff(c[h-1][l+1], c[h-1][l]); if(isused[d]) { ok=false; break; } c[h][l]=d; isused[d]=true; h++;l--; } if(ok) // No conflicts with previously filled numbers { found |= solve(lvl+1); // Go one level deeper h=0; l=lvl; while((h<H) && (l>=0)) // Clean up the 'used' markers { isused[c[h][l]]=false; h++;l--; } } else // Just clean up what we already marked { int hstop=h; h=0; l=lvl; while((h<hstop) && (l>=0)) { isused[c[h][l]]=false; h++;l--; } } #ifndef SHOW_ALL_SOLUTIONS if(found) break; #endif } return found; } int main() { int n=0; // sequence index for(K=2;K<=MAXK;K++) { bool foundsolution=false; #ifdef SKIP_ODD_K_SEARCH if(K%2) // Shortcut. Solution must exist for all odd k>=3. { foundsolution=true; } else #endif { // Attempt all trapezoid dimensions. Show 1st solution only. for(L=1;L<=((K+1)/2);L++) if(findH(K,L)) { assert(H<=MAXH); assert(L<=MAXL); printf("Searching k=%d H=%d L=%d\n",K,H,L); memset(isused,false,sizeof(isused)); foundsolution |= solve(0); #ifndef SHOW_ALL_SOLUTIONS if(foundsolution) break; #endif } } if(foundsolution) { n++; printf("A308468(%d) = %d\n",n,K); } } return 0; }