/** Rortatable partitions. * @author R. J. Mathar * @since 2016-05-28 */ class Rpart4 { /** Dimension. E.g. d=3 means solid partitions. */ static final int d = 4 ; /** the number to be partitioned */ int n ; /** n^d */ int npowd ; /** the solid partition with indices the cartesian coords 0..n-1. */ short[][][][] y; /** ctor. * @param n The number to be partitioned */ Rpart4(int n) { y = new short[n][n][n][n] ; this.n = n ; npowd = (int)(Math.pow(n,d)+0.5) ; } /** 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+x4*n^3 */ int[] cart = new int[d] ; for(int i=0 ; i < d ; i++) { cart[i] = piv % n; piv /= n ; } return cart ; } /* piv2x */ /** 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 ; } /* x2piv */ /** Check if the y are a rotatable partition * @return true if they are */ boolean isrot() { /* check all n^d positions */ for(int piv=0 ; piv < npowd; 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]][rot[3]] != y[cart[0]][cart[1]][cart[2]][cart[3]]) 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]][rot[3]] != y[cart[0]][cart[1]][cart[2]][cart[3]]) 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]][neigh[3]] ); } 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^d-piv remaining parts. */ int count(int piv,int nresid) { int ct =0 ; if ( piv == npowd) { 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]][cart[3]] = 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/A002723 */ public int count() { return count(0,n) ; } /* javac -cp . Rpart4.java java -Xmx6000m -Xss6000m -cp . Rpart4 5 5 2 6 2 7 3 8 3 9 5 10 6 11 8 12 9 13 11 14 14 15 19 16 22 17 28 18 34 19 44 20 52 21 63 22 78 23 99 24 119 */ public static void main(String[] args) { int n=1 ; if (args.length > 0) n = (new Integer(args[0])).intValue() ; while (true) { Rpart4 r = new Rpart4(n) ; int ct = r.count() ; System.out.println(n+ " " + ct) ; n++ ; } } /* main */ } /* Rpart4 */