/* C++ source of A160160, Richard J. Mathar, Jan 09 2010 */ #include <iostream> #include <vector> using namespace std ; /* define the macro PRINT_GNUPLOT if a gnuplot(1) file is to be created, like a160160.gp: 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 "a160160.out" ++ Gv a160160*.eps This assumes that a160160.nul contains gnuplot(1) axis coordinates: 0 -5 0 0 5 0 -5 0 0 5 0 0 0 0 -5 0 0 5 */ /** 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 toothpick that crosses the toothpick (which is from st to en) * at the point en. */ static vector<Tp> perp(const Pt & st, const Pt & en, int gen) { 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<Tp> res ; switch( gen % 3) { case 0: res.push_back(se) ; break; case 1: break ; case 2: res.push_back(fi) ; } 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<Tp> res ; switch( gen % 3) { case 0: res.push_back(fi) ; break; case 1: res.push_back(se) ; break ; case 2: break ; } 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<Tp> res ; switch( gen % 3) { case 0: break; case 1: res.push_back(se) ; break ; case 2: res.push_back(fi) ; } 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<Tp> ts; /* Construct it form a vector of known toothpicks */ TpS( vector<Tp> & 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 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(int gen) const { /* new generation, initially empty */ vector<Tp> 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 crossing toothpick * and add it to the new generation. */ if ( isExp( ts[i].a ) ) { vector<Tp> n = Tp::perp(ts[i].b,ts[i].a,gen) ; if ( n.size() > 0 ) res.push_back(n[0]) ; } if ( isExp( ts[i].b ) ) { vector<Tp> n = Tp::perp(ts[i].a,ts[i].b,gen) ; if ( n.size() > 0 ) res.push_back(n[0]) ; } } #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 << " nohead 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 << " nohead " << endl ; #endif } #ifdef PRINT_GNUPLOT cout << "splot \"a160160.nul\" notitle wi li" << endl ; cout << "unset arrow" << endl ; #endif return res ; } }; /* TpS */ /* Main function. No command line arguments. Makefile: a160160_2.eps: a160160.out a160160.gp a160160.nul a160160.gp a160160.out: a160160 $< > $@ a160160: a160160.cpp # $(CXX) -O -o $@ -DPRINT_GNUPLOT $< $(CXX) -O -o $@ $< */ 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<Tp> rot; rot.push_back(rol) ; /* Initialize the first generation with the toothpick set that * contains only this one toothpick */ TpS root(rot) ; /* loop over generations */ for(int gen=2 ; #ifdef PRINT_GNUPLOT gen < 12 ; #else gen < 80 ; #endif gen++) { /* print the current total count of toothpicks in that generation */ #ifndef PRINT_GNUPLOT cout << root.cnt() << ",\n" ; #else cout << "# gen= " << gen << " " << root.cnt() << endl ; cout << "set output \"a160160_" << gen << ".eps\n" ; #endif /* add toothpicks to the exposed points */ TpS g = root.nextg(gen); root = g ; } cout << endl ; }