/* C++ source of A170876, Richard J. Mathar, Jan 08 2010 */ #include #include using namespace std ; /* define the macro PRINT_GNUPLOT if a gnuplot(1) file is to be created, like gnuplot <<++ set terminal postscript portrait enhanced color unset border set size 1,0.75 set view 70,60 set ticslevel 0 set xrange [-5:5] set yrange [-5:5] set zrange [-5:5] set format x "" set format y "" set format z "" unset tics load "a170876.out" ++ Gv a170876*.eps */ /** A point in the 3D simple cubic integer grid */ class Pt { public: /** The three Cartesian coordinates */ int x,y,z ; Pt(int X, int Y, int Z) : x(X), y(Y), z(Z) { } } ; /* Pt */ /** A toothpick of length 2 in the 3D simple cubic grid, * aligned with one of the 3 coordinate axes. */ class Tp { public: /* its two terminating points */ Pt a; Pt b; /* constructor from the three cartesian coordinates * of each of the 2 ends */ Tp(int x1, int y1, int z1, int x2, int y2, int z2) : a(x1,y1,z1), b(x2,y2,z2) { } /** Compute the two toothpicks that cross the toothpick (which is from st to en) * at the point en. */ static vector perp(const Pt & st, const Pt & en) { if ( st.x == en.x && st.y == en.y) /* original toothp is vertical */ { Tp fi(en.x-1, en.y, en.z, en.x+1, en.y, en.z) ; Tp se(en.x, en.y-1, en.z, en.x, en.y+1, en.z) ; vector res ; res.push_back(fi) ; res.push_back(se) ; return res ; } else if( st.y == en.y && st.z == en.z) /* is horizontal parallel to x */ { Tp fi(en.x, en.y-1, en.z, en.x, en.y+1, en.z) ; Tp se(en.x, en.y, en.z-1, en.x, en.y, en.z+1) ; vector res ; res.push_back(fi) ; res.push_back(se) ; return res ; } else /* is horizontal parallel to y */ { Tp fi(en.x-1, en.y, en.z, en.x+1, en.y, en.z) ; Tp se(en.x, en.y, en.z-1, en.x, en.y, en.z+1) ; vector res ; res.push_back(fi) ; res.push_back(se) ; return res ; } } /* return true if the point pt is one of the ends of this tootpick here. */ bool has(const Pt & pt) const { return ( pt.x == a.x && pt.y == a.y && pt.z == a.z || pt.x == b.x && pt.y == b.y && pt.z == b.z) ; } /* return true if the point pt is the mid point of this tootpick here. */ bool hasMid (const Pt & pt) const { return ( 2*pt.x == a.x+b.x && 2*pt.y == a.y+b.y && 2*pt.z == a.z+b.z) ; } }; /* Tp */ /** A toothpick set */ class TpS { public: /** The set of all toothpicks */ vector ts; /* Construct it form a vector of known toothpicks */ TpS( vector & in) : ts(in) { } /** OEIS main functionality: count toothpicks in the set */ int cnt() const { return ts.size() ; } /** return true if p is a terminal point or mid point of any toothpick of this set */ bool isExp(const Pt & p) const { /* scan all toothpicks in the set and increment the counter by * 1 each time p is an end, and by 2 if p is a mid point */ int cnt = 0; for(int i=0; i< ts.size() ; i++) { if ( ts[i].has(p) ) cnt++ ; if ( ts[i].hasMid(p) ) cnt += 2 ; } /* return true if the counter is 1, else false */ return ( cnt == 1) ; } /** return the next generation of toothpicks, including the * tootpick of the current set (generation). */ TpS nextg() const { /* new generation, initially empty */ vector res ; /* scan all tootpicks in the current set */ for(int i=0 ; i < ts.size() ; i++) { /* if one of the two ends of the tootpick in the current * set is an exposed point, construct the tootpick cross * and add its two tootpicks to the new generation. */ if ( isExp( ts[i].a ) ) { //cout << "is ex " << ts[i].a.x << " " << ts[i].a.y << endl ; vector n = Tp::perp(ts[i].b,ts[i].a) ; res.push_back(n[0]) ; res.push_back(n[1]) ; } if ( isExp( ts[i].b ) ) { //cout << "is ex " << ts[i].b.x << " " << ts[i].b.y << endl ; vector n = Tp::perp(ts[i].a,ts[i].b) ; res.push_back(n[0]) ; res.push_back(n[1]) ; } } #ifdef PRINT_GNUPLOT /* debug: print status for gnuplot(1) */ for(int i=0 ; i < res.size() ; i++) { cout << "set arrow from " << res[i].a.x << "," << res[i].a.y << "," << res[i].a.z << " to " << res[i].b.x << "," << res[i].b.y << "," << res[i].b.z << " heads lt 2 " << endl ; } #endif /* append the toothpicks of the current set */ for(int i=0 ; i < ts.size() ; i++) { res.push_back( ts[i] ) ; #ifdef PRINT_GNUPLOT cout << "set arrow from " << ts[i].a.x << "," << ts[i].a.y << "," << ts[i].a.z << " to " << ts[i].b.x << "," << ts[i].b.y << "," << ts[i].b.z << " heads " << endl ; #endif } #ifdef PRINT_GNUPLOT cout << "splot \"a170876.nul\" notitle wi li" << endl ; cout << "unset arrow" << endl ; #endif return res ; } }; /* Main function. No command line arguments. Shell commands: * gcc -o a170876 a170876.cpp # creates a170876 given a170876.cpp * a170876 > a170876.out * a170876.gp # creates a170876_2.eps, a170876_3.eps a170876_4.eps */ int main(int argc, char *argv[]) { #ifndef PRINT_GNUPLOT cout << "0," ; #endif /* Start with a single tootpick pointing from (0,0,-1) to (0,0,1) */ Tp rol(0,0,-1,0,0,1) ; vector rot; rot.push_back(rol) ; /* Initialize the first generation with the toothpick set that * contains only this one toothpick */ TpS root(rot) ; /* increment generations */ for(int g=2 ;g < 30 ; g++) { /* print the current total count of toothpicks in that generation */ #ifndef PRINT_GNUPLOT cout << root.cnt() << ",\n" ; #else cout << "# g= " << g << " " << root.cnt() << endl ; cout << "set output \"a170876_" << g << ".eps\n" ; #endif /* add toothpicks to the exposed points */ TpS g = root.nextg(); root = g ; } cout << endl ; }