/** Rortatable partitions. * @author R. J. Mathar * @since 2016-05-28 */ class Rpart3 { /* dimensionality. Here d=3 means solid paritions. */ static final int d = 3 ; /* the number to be partitioned */ int n ; /* the solid partition with indices the cartesian coords 0..n-1. */ short[][][] y; /* ctor. * @param n The number to be partitioned */ Rpart3(int n) { y = new short[n][n][n] ; this.n = n ; } /** Convert serialized index into Cartesian coords vector * Inverse functionality to x2piv(). * @param piv The serialized index in the range 0.. n^d-1. * @return The three cartesian coordinates, each 0<=xi<n. */ int[] piv2x(int piv) { /* piv = x1+x2*n+x3^n^2 */ int[] cart = new int[d] ; for(int i=0 ; i < d ; i++) { cart[i] = piv % n; piv /= n ; } return cart ; } /** Convert cartesian xi vector (i=0..n-1) to serialized index * @param cart The coordinates. * @return The serialized index. */ int x2piv(int[] cart) { int piv= cart[cart.length-1] ; for(int i=cart.length-2; i >=0 ; i--) piv = piv*n+cart[i] ; return piv ; } /** Check if the y are a rotatable partition * @return true if they are */ boolean isrot() { /* check all n^3 positions */ for(int piv=0 ; piv < n*n*n; piv++) { /* locate this in the d coordinate system */ final int[] cart = piv2x(piv) ; /* find the rotated position */ int[] rot = new int[cart.length] ; for(int i=0 ; i < rot.length ; i++) rot[i] = cart[(i+1) % d] ; if ( y[rot[0]][rot[1]][rot[2]] != y[cart[0]][cart[1]][cart[2]]) return false; } return true; } /* isrot */ /** Check if the y at a position is compatible with its rotated part. * @param piv The serlized position now settled. * @return true if compatible with the rotated part or if the rotated part is not yet settled. */ boolean isrotat(int piv) { /* locate this in the d coordinate system */ final int[] cart = piv2x(piv) ; /* find the rotated position */ int[] rot = new int[cart.length] ; for(int i=0 ; i < rot.length ; i++) rot[i] = cart[(i+1) % d] ; int pivrot = x2piv(rot) ; if (pivrot >= piv) /* rotated position not yet settled . y[] comparison impossible. */ return true; if ( y[rot[0]][rot[1]][rot[2]] != y[cart[0]][cart[1]][cart[2]]) return false; return true; } /* isrotat */ /** Compute the maximum value in the slots of all neighbours * @param piv The upper limit of slots already filled by value. * @return The maximum value in these slots */ int maxNeigh(int piv) { /* locate this in the d coordinate system */ final int[] cart = piv2x(piv) ; /* because we are dealint with partitions of n, this here is an absolute maximum.. * to be decremented in the loop. */ int mNei = n+1 ; /* loop over the neighbours in the i-th direction */ for(int i=0 ; i < cart.length ;i++) { /* neighbour: index one less in Cartesian coords */ int[] neigh = cart.clone() ; neigh[i]-- ; if (neigh[i] < 0 ) continue ; /* check whether the neighbour has appeared in the sequ. earlier sets */ final int pivnei = x2piv(neigh) ; if ( pivnei < piv) mNei = Math.min(mNei, y[neigh[0]][neigh[1]][neigh[2]] ); } return mNei ; } /* maxNeigh */ /** Recursive count of rotatable partitions. * @param piv The number of y-values already set in the y[][][] blocks. * @param nresid The sum of the parts not yet distributed. * @return The rotatable partitions that are created by distributing nresid over the n^3-piv remaining parts. */ int count(int piv,int nresid) { int ct =0 ; if ( piv == n*n*n) { if( nresid != 0 ) return 0 ; /* check rotatable and return 1 if it is. If rotatable is not checked, A000293 results. */ return isrot() ? 1 : 0; } /* restrict part v such that is monotonous with respect to neighbours * in all d directions. */ for (short v=0 ; v <= Math.min(nresid,maxNeigh(piv)) ; v++) { /* locate this in the d coordinate system */ final int[] cart = piv2x(piv) ; y[cart[0]][cart[1]][cart[2]] = v ; if ( isrotat(piv) ) /* put v into the slot and recur to next slot */ ct += count(piv+1,nresid-v) ; } return ct ; } /* count */ /* Count rotatable partitions * @return q'(d,inf,n) of Wright J. Lond Math Soc. (1968) p 501, oeis.org/A002722 */ public int count() { return count(0,n) ; } /* javac -cp . Rpart3.java java -Xmx6000m -Xss6000m -cp . Rpart3 5 15 28 16 36 17 47 18 56 19 69 20 94 21 114 22 138 23 177 24 218 25 262 26 333 27 410 28 496 29 615 30 755 31 906 */ public static void main(String[] args) { int n=1 ; if (args.length > 0) n = (new Integer(args[0])).intValue() ; while (true) { Rpart3 r = new Rpart3(n) ; int ct = r.count() ; System.out.println(n+ " " + ct) ; n++ ; } } /* main */ } /* Rpart3 */