Scanning code
// Computes Pareto-optimal 4D Moser statistics.
- include <stdio.h>
- include <stdlib.h>
- include <string.h>
- include <time.h>
- define NUM_LINES_3D 25 // 25 non-horizontal lines in [3]^3
// the bitmasks of the 25 lines in [3]^3 const long line_bitmasks[NUM_LINES_3D] = {262657l,263172l,266304l,270592l,525314l,532608l,1049601l,1050628l,1056832l,1065216l,2101256l,2105376l,4202512l,8396808l,8405024l,16781313l,16785412l,16810048l,16843008l,33562626l,33620096l,67117057l,67125252l,67174464l,67240192l};
/* stat[i] is 0,1,2,3 depending on whether i (represented base 3) is of type a,b,c,d. */
const int stat[27] = {0,1,0, 1,2,1, 0,1,0,
1,2,1, 2,3,2, 1,2,1,
0,1,0, 1,2,1, 0,1,0};
long *data[256]; // data[a][i] will be the i^th Moser sets with a-signature a
short int *datastat[256]; // datastat[a][i] will be the statistics of the i^th Moset set with a-signature a
long numstat[9][13][7][2]; /* numstat[a][b][c][d] is the number of Moser sets with statistics (a,b,c,d) */
- define NUM_PARETO 499 // number of feasible stats
int alist[NUM_PARETO], clist[NUM_PARETO], blist[NUM_PARETO], dlist[NUM_PARETO]; // ordered list of feasible stats int statlabel[9][13][7][2]; // statlabel[a][b][c][d] is the index of statistic (a,b,c,d) (if it is feasible)
- define NUM_APAIRS 391 // 391 pairs (a1,a2) to check
int a1[NUM_APAIRS], a2[NUM_APAIRS]; // the pairs (a1,a2) we will loop over int astatnum[256]; // astatnum[a] is how many 3D Moser sets there are with a-signature a
void init_numstat(void) // This was precomputed
{
int a,b,c,d,i,s[4];
/* Initialise numstat */ for (a=0; a<9; a++) for (b=0; b<13; b++) for (c=0; c<7; c++) for (d=0; d<2; d++) numstat[a][b][c][d]=0;
numstat[0][0][0][0] = 1; numstat[0][0][0][1] = 1; numstat[0][0][6][0] = 1; numstat[0][12][0][0] = 1; numstat[8][0][0][0] = 1; numstat[4][12][0][0] = 2; numstat[0][0][1][0] = 6; numstat[0][0][1][1] = 6; numstat[0][0][5][0] = 6; numstat[4][0][5][0] = 6; numstat[0][0][3][1] = 8; numstat[0][6][6][0] = 8; numstat[0][9][3][0] = 8; numstat[1][0][0][0] = 8; numstat[1][0][0][1] = 8; numstat[1][0][6][0] = 8; numstat[1][12][0][0] = 8; numstat[3][12][0][0] = 8; numstat[5][9][0][0] = 8; numstat[7][0][0][0] = 8; numstat[7][3][0][0] = 8; numstat[0][0][2][1] = 12; numstat[0][1][0][0] = 12; numstat[0][1][0][1] = 12; numstat[0][1][6][0] = 12; numstat[0][11][0][0] = 12; numstat[6][0][2][0] = 12; numstat[0][0][2][0] = 15; numstat[0][0][4][0] = 15; numstat[2][0][6][0] = 16; numstat[2][12][0][0] = 16; numstat[4][0][0][1] = 16; numstat[6][6][0][0] = 16; numstat[0][0][3][0] = 20; numstat[0][10][1][0] = 24; numstat[2][0][0][1] = 24; numstat[4][11][0][0] = 24; numstat[4][9][2][0] = 24; numstat[5][0][3][0] = 24; numstat[6][0][1][0] = 24; numstat[7][1][0][0] = 24; numstat[7][2][0][0] = 24; numstat[2][0][0][0] = 28; numstat[6][0][0][0] = 28; numstat[3][0][0][1] = 32; numstat[3][9][3][0] = 32; numstat[4][0][3][1] = 32; numstat[0][5][6][0] = 48; numstat[0][9][2][0] = 48; numstat[1][0][1][0] = 48; numstat[1][0][1][1] = 48; numstat[1][0][5][0] = 48; numstat[3][0][5][0] = 48; numstat[4][1][5][0] = 48; numstat[4][4][5][0] = 48; numstat[4][6][2][1] = 48; numstat[6][3][2][0] = 48; numstat[6][4][1][0] = 48; numstat[0][2][6][0] = 54; numstat[4][0][1][1] = 54; numstat[3][0][0][0] = 56; numstat[5][0][0][0] = 56; numstat[0][2][0][1] = 60; numstat[4][0][4][0] = 60; numstat[6][1][2][0] = 60; numstat[0][6][0][1] = 64; numstat[0][6][3][1] = 64; numstat[1][0][3][1] = 64; numstat[1][6][6][0] = 64; numstat[1][9][3][0] = 64; numstat[0][10][0][0] = 66; numstat[0][2][0][0] = 66; numstat[4][0][0][0] = 70; numstat[0][1][1][0] = 72; numstat[0][1][1][1] = 72; numstat[0][1][5][0] = 72; numstat[4][0][2][1] = 72; numstat[2][6][6][0] = 80; numstat[0][1][3][1] = 96; numstat[0][8][3][0] = 96; numstat[1][0][2][1] = 96; numstat[1][1][0][0] = 96; numstat[1][1][0][1] = 96; numstat[1][1][6][0] = 96; numstat[1][11][0][0] = 96; numstat[5][0][2][0] = 96; numstat[5][4][3][0] = 96; numstat[5][7][1][0] = 96; numstat[5][8][0][0] = 96; numstat[6][2][2][0] = 96; numstat[2][9][3][0] = 104; numstat[3][0][3][1] = 104; numstat[0][4][6][0] = 108; numstat[0][6][5][0] = 108; numstat[0][7][4][0] = 108; numstat[2][0][5][0] = 108; numstat[6][5][0][0] = 108; numstat[0][3][6][0] = 112; numstat[3][6][3][1] = 112; numstat[1][0][2][0] = 120; numstat[1][0][4][0] = 120; numstat[3][11][0][0] = 120; numstat[4][6][1][1] = 120; numstat[5][0][1][0] = 120; numstat[5][6][2][0] = 120; numstat[6][1][1][0] = 120; numstat[2][0][1][1] = 132; numstat[4][2][5][0] = 132; numstat[4][6][4][0] = 132; numstat[0][1][2][1] = 144; numstat[2][0][3][1] = 144; numstat[3][0][1][1] = 144; numstat[4][1][0][1] = 144; numstat[4][3][5][0] = 144; numstat[4][9][1][0] = 144; numstat[2][0][1][0] = 156; numstat[6][1][0][0] = 156; numstat[0][3][0][1] = 160; numstat[1][0][3][0] = 160; numstat[4][10][0][0] = 162; numstat[5][1][3][0] = 168; numstat[6][3][1][0] = 168; numstat[0][1][2][0] = 180; numstat[0][1][4][0] = 180; numstat[2][1][6][0] = 180; numstat[0][5][0][1] = 192; numstat[1][10][1][0] = 192; numstat[3][10][1][0] = 192; numstat[4][4][3][1] = 192; numstat[2][11][0][0] = 204; numstat[4][0][3][0] = 212; numstat[0][6][1][1] = 216; numstat[0][6][2][1] = 216; numstat[0][9][1][0] = 216; numstat[3][0][2][1] = 216; numstat[4][6][0][1] = 216; numstat[6][2][1][0] = 216; numstat[0][3][0][0] = 220; numstat[0][9][0][0] = 220; numstat[0][1][3][0] = 240; numstat[0][4][0][1] = 240; numstat[2][0][2][1] = 240; numstat[3][0][4][0] = 240; numstat[4][0][1][0] = 246; numstat[3][0][1][0] = 264; numstat[3][6][5][0] = 264; numstat[4][1][3][1] = 264; numstat[2][1][0][1] = 276; numstat[4][7][3][0] = 288; numstat[2][0][4][0] = 300; numstat[6][4][0][0] = 300; numstat[3][9][2][0] = 312; numstat[2][1][0][0] = 324; numstat[0][2][5][0] = 336; numstat[3][1][0][1] = 336; numstat[4][0][2][0] = 336; numstat[0][2][1][1] = 348; numstat[2][0][2][0] = 360; numstat[4][5][2][1] = 360; numstat[6][2][0][0] = 360; numstat[0][2][1][0] = 384; numstat[0][5][3][1] = 384; numstat[1][5][6][0] = 384; numstat[1][9][2][0] = 384; numstat[2][10][1][0] = 384; numstat[4][8][2][0] = 384; numstat[5][3][3][0] = 384; numstat[5][2][3][0] = 408; numstat[0][2][3][1] = 432; numstat[1][2][6][0] = 432; numstat[3][7][4][0] = 432; numstat[5][1][0][0] = 432; numstat[2][0][3][0] = 440; numstat[6][3][0][0] = 440; numstat[4][1][1][1] = 456; numstat[0][8][2][0] = 480; numstat[1][2][0][1] = 480; numstat[3][8][3][0] = 480; numstat[3][0][3][0] = 488; numstat[0][4][0][0] = 495; numstat[0][8][0][0] = 495; numstat[0][5][5][0] = 504; numstat[3][0][2][0] = 504; numstat[3][1][5][0] = 504; numstat[5][7][0][0] = 504; numstat[1][6][0][1] = 512; numstat[1][6][3][1] = 512; numstat[4][1][4][0] = 516; numstat[1][10][0][0] = 528; numstat[1][2][0][0] = 528; numstat[2][5][6][0] = 528; numstat[4][2][0][1] = 540; numstat[1][1][1][0] = 576; numstat[1][1][1][1] = 576; numstat[1][1][5][0] = 576; numstat[3][1][0][0] = 600; numstat[4][1][2][1] = 600; numstat[5][5][2][0] = 648; numstat[4][1][0][0] = 660; numstat[0][2][2][1] = 672; numstat[4][5][4][0] = 672; numstat[5][1][2][0] = 696; numstat[2][9][2][0] = 720; numstat[5][6][1][0] = 720; numstat[4][2][3][1] = 744; numstat[4][5][1][1] = 744; numstat[2][2][6][0] = 756; numstat[0][3][5][0] = 768; numstat[0][7][3][0] = 768; numstat[1][1][3][1] = 768; numstat[1][8][3][0] = 768; numstat[2][6][3][1] = 768; numstat[4][9][0][0] = 772; numstat[0][5][0][0] = 792; numstat[0][5][1][1] = 792; numstat[0][7][0][0] = 792; numstat[4][3][3][1] = 792; numstat[4][5][0][1] = 792; numstat[0][6][4][0] = 816; numstat[3][10][0][0] = 816; numstat[0][3][1][1] = 864; numstat[0][4][3][1] = 864; numstat[1][4][6][0] = 864; numstat[1][6][5][0] = 864; numstat[1][7][4][0] = 864; numstat[0][2][4][0] = 870; numstat[0][8][1][0] = 870; numstat[5][1][1][0] = 888; numstat[0][4][5][0] = 894; numstat[0][3][3][1] = 896; numstat[1][3][6][0] = 896; numstat[3][6][0][1] = 896; numstat[0][6][0][0] = 924; numstat[0][2][2][0] = 930; numstat[0][5][2][1] = 1008; numstat[3][6][2][1] = 1008; numstat[3][1][3][1] = 1056; numstat[3][5][3][1] = 1056; numstat[4][3][0][1] = 1088; numstat[1][1][2][1] = 1152; numstat[2][6][0][1] = 1152; numstat[0][4][1][1] = 1158; numstat[2][10][0][0] = 1188; numstat[0][2][3][0] = 1200; numstat[0][3][1][0] = 1200; numstat[2][1][5][0] = 1224; numstat[4][4][0][1] = 1254; numstat[1][3][0][1] = 1280; numstat[2][4][6][0] = 1296; numstat[2][6][5][0] = 1296; numstat[2][2][0][1] = 1320; numstat[2][8][3][0] = 1344; numstat[2][7][4][0] = 1404; numstat[4][8][1][0] = 1416; numstat[1][1][2][0] = 1440; numstat[1][1][4][0] = 1440; numstat[4][4][2][1] = 1440; numstat[2][3][6][0] = 1456; numstat[3][2][0][1] = 1464; numstat[5][2][0][0] = 1464; numstat[3][1][1][1] = 1488; numstat[4][2][1][1] = 1488; numstat[2][1][1][1] = 1512; numstat[5][6][0][0] = 1512; numstat[0][3][2][1] = 1536; numstat[1][5][0][1] = 1536; numstat[3][5][5][0] = 1608; numstat[2][1][3][1] = 1632; numstat[4][2][4][0] = 1662; numstat[2][2][0][0] = 1716; numstat[1][6][1][1] = 1728; numstat[1][6][2][1] = 1728; numstat[1][9][1][0] = 1728; numstat[1][3][0][0] = 1760; numstat[1][9][0][0] = 1760; numstat[0][4][2][1] = 1788; numstat[2][1][1][0] = 1800; numstat[4][4][4][0] = 1806; numstat[3][6][1][1] = 1824; numstat[4][2][2][1] = 1824; numstat[5][4][2][0] = 1824; numstat[4][1][3][0] = 1896; numstat[1][1][3][0] = 1920; numstat[1][4][0][1] = 1920; numstat[4][4][1][1] = 1920; numstat[0][7][2][0] = 1932; numstat[5][2][2][0] = 1944; numstat[3][2][5][0] = 2016; numstat[0][7][1][0] = 2064; numstat[4][6][3][0] = 2096; numstat[3][9][1][0] = 2160; numstat[0][3][4][0] = 2172; numstat[3][1][2][1] = 2208; numstat[0][5][4][0] = 2232; numstat[4][1][1][0] = 2280; numstat[5][5][1][0] = 2352; numstat[4][3][1][1] = 2376; numstat[0][4][1][0] = 2436; numstat[4][3][2][1] = 2472; numstat[4][3][4][0] = 2496; numstat[3][1][4][0] = 2520; numstat[4][8][0][0] = 2634; numstat[4][7][2][0] = 2640; numstat[5][3][2][0] = 2640; numstat[1][2][5][0] = 2688; numstat[0][6][3][0] = 2696; numstat[0][3][2][0] = 2712; numstat[5][2][1][0] = 2712; numstat[2][1][2][1] = 2736; numstat[1][2][1][1] = 2784; numstat[4][2][0][0] = 2802; numstat[3][1][1][0] = 2808; numstat[5][3][0][0] = 2856; numstat[5][5][0][0] = 2856; numstat[3][2][0][0] = 2928; numstat[0][4][4][0] = 2988; numstat[2][6][2][1] = 3024; numstat[1][2][1][0] = 3072; numstat[1][5][3][1] = 3072; numstat[3][5][0][1] = 3072; numstat[4][1][2][0] = 3072; numstat[0][6][1][0] = 3192; numstat[0][3][3][0] = 3248; numstat[3][9][0][0] = 3320; numstat[0][5][1][0] = 3360; numstat[2][3][0][1] = 3360; numstat[3][3][0][1] = 3392; numstat[2][1][4][0] = 3420; numstat[1][2][3][1] = 3456; numstat[2][6][1][1] = 3456; numstat[5][4][0][0] = 3528; numstat[3][4][5][0] = 3600; numstat[2][5][0][1] = 3648; numstat[2][9][1][0] = 3672; numstat[1][8][2][0] = 3840; numstat[3][3][5][0] = 3840; numstat[3][2][3][1] = 3888; numstat[3][8][2][0] = 3936; numstat[1][4][0][0] = 3960; numstat[1][8][0][0] = 3960; numstat[3][4][3][1] = 3960; numstat[1][5][5][0] = 4032; numstat[2][1][2][0] = 4140; numstat[3][6][4][0] = 4176; numstat[2][9][0][0] = 4180; numstat[5][4][1][0] = 4224; numstat[0][6][2][0] = 4248; numstat[3][4][0][1] = 4416; numstat[5][3][1][0] = 4440; numstat[2][4][0][1] = 4800; numstat[0][4][2][0] = 4911; numstat[0][5][3][0] = 4920; numstat[2][5][3][1] = 4992; numstat[2][1][3][0] = 5040; numstat[3][7][3][0] = 5112; numstat[3][1][3][0] = 5136; numstat[0][4][3][0] = 5172; numstat[3][1][2][0] = 5328; numstat[1][2][2][1] = 5376; numstat[2][2][5][0] = 5376; numstat[2][3][0][0] = 5500; numstat[0][5][2][0] = 5712; numstat[3][5][2][1] = 6096; numstat[3][2][1][1] = 6120; numstat[1][3][5][0] = 6144; numstat[1][7][3][0] = 6144; numstat[3][3][3][1] = 6176; numstat[1][5][0][0] = 6336; numstat[1][5][1][1] = 6336; numstat[1][7][0][0] = 6336; numstat[4][7][1][0] = 6336; numstat[4][7][0][0] = 6384; numstat[1][6][4][0] = 6528; numstat[2][5][5][0] = 6552; numstat[4][2][3][0] = 6720; numstat[4][5][3][0] = 6720; numstat[1][3][1][1] = 6912; numstat[1][4][3][1] = 6912; numstat[2][2][3][1] = 6912; numstat[1][2][4][0] = 6960; numstat[1][8][1][0] = 6960; numstat[2][2][1][1] = 6960; numstat[4][3][0][0] = 7064; numstat[1][4][5][0] = 7152; numstat[1][3][3][1] = 7168; numstat[1][6][0][0] = 7392; numstat[1][2][2][0] = 7440; numstat[2][8][2][0] = 7680; numstat[3][5][1][1] = 8016; numstat[1][5][2][1] = 8064; numstat[3][2][2][1] = 8592; numstat[3][3][0][0] = 8600; numstat[3][8][0][0] = 9000; numstat[4][2][1][0] = 9132; numstat[2][2][1][0] = 9216; numstat[1][4][1][1] = 9264; numstat[1][2][3][0] = 9600; numstat[1][3][1][0] = 9600; numstat[4][6][2][0] = 9804; numstat[2][8][0][0] = 9900; numstat[3][2][4][0] = 10464; numstat[3][8][1][0] = 10776; numstat[4][6][0][0] = 11004; numstat[2][6][4][0] = 11424; numstat[2][3][5][0] = 11520; numstat[2][7][3][0] = 11520; numstat[4][2][2][0] = 11652; numstat[4][4][0][0] = 11742; numstat[2][4][0][0] = 11880; numstat[4][4][3][0] = 12000; numstat[2][2][2][1] = 12096; numstat[2][4][3][1] = 12096; numstat[4][3][3][0] = 12120; numstat[1][3][2][1] = 12288; numstat[2][4][5][0] = 12516; numstat[3][3][1][1] = 12768; numstat[3][2][1][0] = 13152; numstat[2][3][3][1] = 13440; numstat[2][5][1][1] = 13464; numstat[4][5][0][0] = 13512; numstat[3][4][1][1] = 14208; numstat[1][4][2][1] = 14304; numstat[3][4][2][1] = 14352; numstat[3][5][4][0] = 14688; numstat[2][5][2][1] = 15120; numstat[1][7][2][0] = 15456; numstat[2][2][4][0] = 15660; numstat[2][8][1][0] = 15660; numstat[3][3][2][1] = 15888; numstat[2][3][1][1] = 16416; numstat[1][7][1][0] = 16512; numstat[4][6][1][0] = 16536; numstat[2][7][0][0] = 16632; numstat[3][4][0][0] = 16920; numstat[3][7][0][0] = 17136; numstat[1][3][4][0] = 17376; numstat[1][5][4][0] = 17856; numstat[2][5][0][0] = 18216; numstat[1][4][1][0] = 19488; numstat[3][7][2][0] = 19896; numstat[2][6][0][0] = 20328; numstat[2][2][2][0] = 20460; numstat[4][3][1][0] = 20760; numstat[2][4][1][1] = 20844; numstat[1][6][3][0] = 21568; numstat[4][5][2][0] = 21576; numstat[1][3][2][0] = 21696; numstat[3][3][4][0] = 21936; numstat[3][2][3][0] = 22176; numstat[3][6][3][0] = 22904; numstat[3][5][0][0] = 23472; numstat[3][6][0][0] = 23520; numstat[1][4][4][0] = 23904; numstat[4][3][2][0] = 23904; numstat[3][2][2][0] = 23952; numstat[2][2][3][0] = 24000; numstat[3][4][4][0] = 24672; numstat[1][6][1][0] = 25536; numstat[1][3][3][0] = 25984; numstat[2][3][2][1] = 26112; numstat[1][5][1][0] = 26880; numstat[4][5][1][0] = 27360; numstat[2][3][1][0] = 27600; numstat[2][4][2][1] = 28608; numstat[4][4][2][0] = 29040; numstat[4][4][1][0] = 29550; numstat[3][7][1][0] = 31272; numstat[2][7][2][0] = 32844; numstat[2][5][4][0] = 33480; numstat[1][6][2][0] = 33984; numstat[3][3][1][0] = 35736; numstat[2][3][4][0] = 36924; numstat[2][7][1][0] = 39216; numstat[1][4][2][0] = 39288; numstat[1][5][3][0] = 39360; numstat[1][4][3][0] = 41376; numstat[2][6][3][0] = 43136; numstat[1][5][2][0] = 45696; numstat[2][4][4][0] = 47808; numstat[3][3][3][0] = 50912; numstat[3][5][3][0] = 52272; numstat[2][4][1][0] = 53592; numstat[3][6][2][0] = 54216; numstat[2][3][2][0] = 56952; numstat[3][6][1][0] = 58368; numstat[3][3][2][0] = 59952; numstat[2][3][3][0] = 61712; numstat[3][4][1][0] = 62400; numstat[2][6][1][0] = 63840; numstat[3][4][3][0] = 67416; numstat[2][5][1][0] = 70560; numstat[3][5][1][0] = 73176; numstat[2][6][2][0] = 76464; numstat[2][5][3][0] = 83640; numstat[3][5][2][0] = 88944; numstat[3][4][2][0] = 91824; numstat[2][4][3][0] = 93096; numstat[2][4][2][0] = 98220; numstat[2][5][2][0] = 108528;
// compute statlabel;
int count=0;
for (a=0; a<9; a++) for (b=0; b<13; b++) for (c=0; c<7; c++) for (d=0; d<2; d++) if (numstat[a][b][c][d]) { alist[count] = a; blist[count] = b; clist[count] = c; dlist[count] = d; statlabel[a][b][c][d] = count; count++; } else statlabel[a][b][c][d] = -1;
i=0;
a1[i] = 0; a2[i] = 0; i++; a1[i] = 0; a2[i] = 15; i++; a1[i] = 0; a2[i] = 23; i++; a1[i] = 0; a2[i] = 27; i++; a1[i] = 0; a2[i] = 30; i++; a1[i] = 0; a2[i] = 31; i++; a1[i] = 0; a2[i] = 60; i++; a1[i] = 0; a2[i] = 61; i++; a1[i] = 0; a2[i] = 63; i++; a1[i] = 0; a2[i] = 105; i++; a1[i] = 0; a2[i] = 107; i++; a1[i] = 0; a2[i] = 111; i++; a1[i] = 0; a2[i] = 126; i++; a1[i] = 0; a2[i] = 127; i++; a1[i] = 0; a2[i] = 255; i++; a1[i] = 1; a2[i] = 22; i++; a1[i] = 1; a2[i] = 23; i++; a1[i] = 2; a2[i] = 21; i++; a1[i] = 2; a2[i] = 22; i++; a1[i] = 2; a2[i] = 23; i++; a1[i] = 1; a2[i] = 30; i++; a1[i] = 1; a2[i] = 31; i++; a1[i] = 1; a2[i] = 44; i++; a1[i] = 2; a2[i] = 29; i++; a1[i] = 1; a2[i] = 47; i++; a1[i] = 1; a2[i] = 60; i++; a1[i] = 1; a2[i] = 61; i++; a1[i] = 1; a2[i] = 62; i++; a1[i] = 1; a2[i] = 63; i++; a1[i] = 1; a2[i] = 104; i++; a1[i] = 1; a2[i] = 105; i++; a1[i] = 1; a2[i] = 106; i++; a1[i] = 1; a2[i] = 107; i++; a1[i] = 1; a2[i] = 110; i++; a1[i] = 1; a2[i] = 111; i++; a1[i] = 1; a2[i] = 126; i++; a1[i] = 1; a2[i] = 127; i++; a1[i] = 8; a2[i] = 19; i++; a1[i] = 1; a2[i] = 134; i++; a1[i] = 8; a2[i] = 23; i++; a1[i] = 1; a2[i] = 137; i++; a1[i] = 1; a2[i] = 139; i++; a1[i] = 1; a2[i] = 143; i++; a1[i] = 1; a2[i] = 150; i++; a1[i] = 1; a2[i] = 151; i++; a1[i] = 1; a2[i] = 152; i++; a1[i] = 1; a2[i] = 153; i++; a1[i] = 1; a2[i] = 154; i++; a1[i] = 1; a2[i] = 155; i++; a1[i] = 1; a2[i] = 158; i++; a1[i] = 1; a2[i] = 159; i++; a1[i] = 1; a2[i] = 168; i++; a1[i] = 1; a2[i] = 169; i++; a1[i] = 1; a2[i] = 170; i++; a1[i] = 1; a2[i] = 171; i++; a1[i] = 1; a2[i] = 172; i++; a1[i] = 1; a2[i] = 173; i++; a1[i] = 1; a2[i] = 174; i++; a1[i] = 1; a2[i] = 175; i++; a1[i] = 1; a2[i] = 188; i++; a1[i] = 1; a2[i] = 189; i++; a1[i] = 1; a2[i] = 190; i++; a1[i] = 1; a2[i] = 191; i++; a1[i] = 1; a2[i] = 232; i++; a1[i] = 1; a2[i] = 233; i++; a1[i] = 1; a2[i] = 234; i++; a1[i] = 1; a2[i] = 235; i++; a1[i] = 1; a2[i] = 238; i++; a1[i] = 1; a2[i] = 239; i++; a1[i] = 1; a2[i] = 254; i++; a1[i] = 1; a2[i] = 255; i++; a1[i] = 22; a2[i] = 22; i++; a1[i] = 3; a2[i] = 61; i++; a1[i] = 3; a2[i] = 63; i++; a1[i] = 3; a2[i] = 86; i++; a1[i] = 3; a2[i] = 87; i++; a1[i] = 6; a2[i] = 52; i++; a1[i] = 6; a2[i] = 53; i++; a1[i] = 5; a2[i] = 58; i++; a1[i] = 6; a2[i] = 55; i++; a1[i] = 3; a2[i] = 94; i++; a1[i] = 3; a2[i] = 95; i++; a1[i] = 3; a2[i] = 104; i++; a1[i] = 3; a2[i] = 105; i++; a1[i] = 6; a2[i] = 58; i++; a1[i] = 3; a2[i] = 107; i++; a1[i] = 3; a2[i] = 108; i++; a1[i] = 3; a2[i] = 109; i++; a1[i] = 6; a2[i] = 62; i++; a1[i] = 3; a2[i] = 111; i++; a1[i] = 3; a2[i] = 124; i++; a1[i] = 3; a2[i] = 125; i++; a1[i] = 3; a2[i] = 126; i++; a1[i] = 3; a2[i] = 127; i++; a1[i] = 3; a2[i] = 192; i++; a1[i] = 12; a2[i] = 49; i++; a1[i] = 12; a2[i] = 51; i++; a1[i] = 3; a2[i] = 197; i++; a1[i] = 3; a2[i] = 198; i++; a1[i] = 12; a2[i] = 55; i++; a1[i] = 3; a2[i] = 207; i++; a1[i] = 3; a2[i] = 212; i++; a1[i] = 3; a2[i] = 213; i++; a1[i] = 3; a2[i] = 214; i++; a1[i] = 3; a2[i] = 215; i++; a1[i] = 3; a2[i] = 216; i++; a1[i] = 3; a2[i] = 217; i++; a1[i] = 3; a2[i] = 219; i++; a1[i] = 3; a2[i] = 220; i++; a1[i] = 3; a2[i] = 221; i++; a1[i] = 3; a2[i] = 222; i++; a1[i] = 3; a2[i] = 223; i++; a1[i] = 3; a2[i] = 252; i++; a1[i] = 3; a2[i] = 253; i++; a1[i] = 3; a2[i] = 255; i++; a1[i] = 6; a2[i] = 96; i++; a1[i] = 6; a2[i] = 97; i++; a1[i] = 20; a2[i] = 42; i++; a1[i] = 20; a2[i] = 43; i++; a1[i] = 21; a2[i] = 42; i++; a1[i] = 6; a2[i] = 103; i++; a1[i] = 6; a2[i] = 105; i++; a1[i] = 6; a2[i] = 107; i++; a1[i] = 6; a2[i] = 111; i++; a1[i] = 6; a2[i] = 114; i++; a1[i] = 6; a2[i] = 115; i++; a1[i] = 6; a2[i] = 118; i++; a1[i] = 6; a2[i] = 119; i++; a1[i] = 6; a2[i] = 120; i++; a1[i] = 6; a2[i] = 121; i++; a1[i] = 6; a2[i] = 122; i++; a1[i] = 6; a2[i] = 123; i++; a1[i] = 6; a2[i] = 126; i++; a1[i] = 6; a2[i] = 127; i++; a1[i] = 6; a2[i] = 144; i++; a1[i] = 9; a2[i] = 97; i++; a1[i] = 6; a2[i] = 147; i++; a1[i] = 6; a2[i] = 150; i++; a1[i] = 6; a2[i] = 151; i++; a1[i] = 6; a2[i] = 159; i++; a1[i] = 6; a2[i] = 176; i++; a1[i] = 6; a2[i] = 177; i++; a1[i] = 6; a2[i] = 178; i++; a1[i] = 6; a2[i] = 179; i++; a1[i] = 6; a2[i] = 180; i++; a1[i] = 6; a2[i] = 181; i++; a1[i] = 6; a2[i] = 182; i++; a1[i] = 6; a2[i] = 183; i++; a1[i] = 6; a2[i] = 185; i++; a1[i] = 6; a2[i] = 187; i++; a1[i] = 6; a2[i] = 189; i++; a1[i] = 6; a2[i] = 191; i++; a1[i] = 6; a2[i] = 240; i++; a1[i] = 6; a2[i] = 241; i++; a1[i] = 6; a2[i] = 242; i++; a1[i] = 6; a2[i] = 243; i++; a1[i] = 6; a2[i] = 246; i++; a1[i] = 6; a2[i] = 247; i++; a1[i] = 6; a2[i] = 249; i++; a1[i] = 6; a2[i] = 251; i++; a1[i] = 6; a2[i] = 255; i++; a1[i] = 7; a2[i] = 118; i++; a1[i] = 7; a2[i] = 119; i++; a1[i] = 7; a2[i] = 120; i++; a1[i] = 7; a2[i] = 121; i++; a1[i] = 7; a2[i] = 122; i++; a1[i] = 7; a2[i] = 123; i++; a1[i] = 7; a2[i] = 126; i++; a1[i] = 7; a2[i] = 127; i++; a1[i] = 7; a2[i] = 176; i++; a1[i] = 11; a2[i] = 113; i++; a1[i] = 24; a2[i] = 63; i++; a1[i] = 11; a2[i] = 116; i++; a1[i] = 11; a2[i] = 117; i++; a1[i] = 7; a2[i] = 182; i++; a1[i] = 7; a2[i] = 183; i++; a1[i] = 7; a2[i] = 188; i++; a1[i] = 7; a2[i] = 189; i++; a1[i] = 7; a2[i] = 191; i++; a1[i] = 7; a2[i] = 224; i++; a1[i] = 14; a2[i] = 113; i++; a1[i] = 7; a2[i] = 226; i++; a1[i] = 14; a2[i] = 115; i++; a1[i] = 7; a2[i] = 230; i++; a1[i] = 7; a2[i] = 231; i++; a1[i] = 7; a2[i] = 233; i++; a1[i] = 7; a2[i] = 235; i++; a1[i] = 7; a2[i] = 239; i++; a1[i] = 7; a2[i] = 240; i++; a1[i] = 7; a2[i] = 241; i++; a1[i] = 7; a2[i] = 242; i++; a1[i] = 7; a2[i] = 243; i++; a1[i] = 7; a2[i] = 246; i++; a1[i] = 7; a2[i] = 247; i++; a1[i] = 7; a2[i] = 248; i++; a1[i] = 7; a2[i] = 249; i++; a1[i] = 7; a2[i] = 250; i++; a1[i] = 7; a2[i] = 251; i++; a1[i] = 7; a2[i] = 254; i++; a1[i] = 7; a2[i] = 255; i++; a1[i] = 15; a2[i] = 240; i++; a1[i] = 15; a2[i] = 241; i++; a1[i] = 15; a2[i] = 243; i++; a1[i] = 15; a2[i] = 246; i++; a1[i] = 15; a2[i] = 247; i++; a1[i] = 15; a2[i] = 255; i++; a1[i] = 22; a2[i] = 104; i++; a1[i] = 22; a2[i] = 105; i++; a1[i] = 23; a2[i] = 104; i++; a1[i] = 22; a2[i] = 107; i++; a1[i] = 23; a2[i] = 106; i++; a1[i] = 22; a2[i] = 111; i++; a1[i] = 22; a2[i] = 126; i++; a1[i] = 22; a2[i] = 127; i++; a1[i] = 22; a2[i] = 129; i++; a1[i] = 24; a2[i] = 99; i++; a1[i] = 22; a2[i] = 134; i++; a1[i] = 24; a2[i] = 103; i++; a1[i] = 24; a2[i] = 105; i++; a1[i] = 24; a2[i] = 107; i++; a1[i] = 24; a2[i] = 110; i++; a1[i] = 24; a2[i] = 111; i++; a1[i] = 22; a2[i] = 150; i++; a1[i] = 22; a2[i] = 151; i++; a1[i] = 22; a2[i] = 152; i++; a1[i] = 25; a2[i] = 105; i++; a1[i] = 22; a2[i] = 154; i++; a1[i] = 25; a2[i] = 107; i++; a1[i] = 22; a2[i] = 158; i++; a1[i] = 22; a2[i] = 159; i++; a1[i] = 22; a2[i] = 169; i++; a1[i] = 22; a2[i] = 171; i++; a1[i] = 22; a2[i] = 172; i++; a1[i] = 26; a2[i] = 109; i++; a1[i] = 22; a2[i] = 174; i++; a1[i] = 26; a2[i] = 111; i++; a1[i] = 22; a2[i] = 188; i++; a1[i] = 22; a2[i] = 189; i++; a1[i] = 22; a2[i] = 190; i++; a1[i] = 22; a2[i] = 191; i++; a1[i] = 22; a2[i] = 233; i++; a1[i] = 22; a2[i] = 234; i++; a1[i] = 22; a2[i] = 235; i++; a1[i] = 22; a2[i] = 238; i++; a1[i] = 22; a2[i] = 239; i++; a1[i] = 22; a2[i] = 254; i++; a1[i] = 22; a2[i] = 255; i++; a1[i] = 23; a2[i] = 126; i++; a1[i] = 23; a2[i] = 127; i++; a1[i] = 23; a2[i] = 129; i++; a1[i] = 24; a2[i] = 115; i++; a1[i] = 24; a2[i] = 119; i++; a1[i] = 24; a2[i] = 121; i++; a1[i] = 24; a2[i] = 123; i++; a1[i] = 24; a2[i] = 126; i++; a1[i] = 24; a2[i] = 127; i++; a1[i] = 23; a2[i] = 150; i++; a1[i] = 23; a2[i] = 151; i++; a1[i] = 23; a2[i] = 152; i++; a1[i] = 25; a2[i] = 121; i++; a1[i] = 23; a2[i] = 154; i++; a1[i] = 25; a2[i] = 123; i++; a1[i] = 23; a2[i] = 158; i++; a1[i] = 23; a2[i] = 159; i++; a1[i] = 26; a2[i] = 121; i++; a1[i] = 26; a2[i] = 123; i++; a1[i] = 23; a2[i] = 172; i++; a1[i] = 26; a2[i] = 125; i++; a1[i] = 26; a2[i] = 126; i++; a1[i] = 26; a2[i] = 127; i++; a1[i] = 23; a2[i] = 188; i++; a1[i] = 23; a2[i] = 189; i++; a1[i] = 23; a2[i] = 190; i++; a1[i] = 23; a2[i] = 191; i++; a1[i] = 23; a2[i] = 232; i++; a1[i] = 23; a2[i] = 233; i++; a1[i] = 23; a2[i] = 234; i++; a1[i] = 23; a2[i] = 235; i++; a1[i] = 23; a2[i] = 238; i++; a1[i] = 23; a2[i] = 239; i++; a1[i] = 23; a2[i] = 254; i++; a1[i] = 23; a2[i] = 255; i++; a1[i] = 24; a2[i] = 231; i++; a1[i] = 24; a2[i] = 239; i++; a1[i] = 24; a2[i] = 255; i++; a1[i] = 25; a2[i] = 225; i++; a1[i] = 25; a2[i] = 227; i++; a1[i] = 25; a2[i] = 230; i++; a1[i] = 25; a2[i] = 231; i++; a1[i] = 25; a2[i] = 233; i++; a1[i] = 25; a2[i] = 234; i++; a1[i] = 25; a2[i] = 235; i++; a1[i] = 25; a2[i] = 238; i++; a1[i] = 25; a2[i] = 239; i++; a1[i] = 25; a2[i] = 241; i++; a1[i] = 25; a2[i] = 243; i++; a1[i] = 25; a2[i] = 246; i++; a1[i] = 25; a2[i] = 247; i++; a1[i] = 25; a2[i] = 248; i++; a1[i] = 25; a2[i] = 249; i++; a1[i] = 47; a2[i] = 92; i++; a1[i] = 25; a2[i] = 251; i++; a1[i] = 25; a2[i] = 254; i++; a1[i] = 25; a2[i] = 255; i++; a1[i] = 27; a2[i] = 214; i++; a1[i] = 27; a2[i] = 215; i++; a1[i] = 27; a2[i] = 216; i++; a1[i] = 46; a2[i] = 117; i++; a1[i] = 27; a2[i] = 219; i++; a1[i] = 27; a2[i] = 222; i++; a1[i] = 27; a2[i] = 223; i++; a1[i] = 27; a2[i] = 228; i++; a1[i] = 45; a2[i] = 121; i++; a1[i] = 27; a2[i] = 231; i++; a1[i] = 27; a2[i] = 236; i++; a1[i] = 27; a2[i] = 237; i++; a1[i] = 30; a2[i] = 190; i++; a1[i] = 27; a2[i] = 239; i++; a1[i] = 27; a2[i] = 252; i++; a1[i] = 27; a2[i] = 253; i++; a1[i] = 27; a2[i] = 255; i++; a1[i] = 30; a2[i] = 225; i++; a1[i] = 61; a2[i] = 105; i++; a1[i] = 30; a2[i] = 230; i++; a1[i] = 30; a2[i] = 231; i++; a1[i] = 30; a2[i] = 233; i++; a1[i] = 30; a2[i] = 235; i++; a1[i] = 30; a2[i] = 238; i++; a1[i] = 30; a2[i] = 239; i++; a1[i] = 30; a2[i] = 241; i++; a1[i] = 61; a2[i] = 109; i++; a1[i] = 30; a2[i] = 246; i++; a1[i] = 30; a2[i] = 247; i++; a1[i] = 30; a2[i] = 249; i++; a1[i] = 31; a2[i] = 234; i++; a1[i] = 30; a2[i] = 251; i++; a1[i] = 30; a2[i] = 254; i++; a1[i] = 30; a2[i] = 255; i++; a1[i] = 31; a2[i] = 241; i++; a1[i] = 31; a2[i] = 242; i++; a1[i] = 61; a2[i] = 125; i++; a1[i] = 31; a2[i] = 246; i++; a1[i] = 31; a2[i] = 247; i++; a1[i] = 31; a2[i] = 248; i++; a1[i] = 31; a2[i] = 249; i++; a1[i] = 62; a2[i] = 126; i++; a1[i] = 31; a2[i] = 251; i++; a1[i] = 31; a2[i] = 254; i++; a1[i] = 31; a2[i] = 255; i++; a1[i] = 105; a2[i] = 105; i++; a1[i] = 105; a2[i] = 107; i++; a1[i] = 107; a2[i] = 107; i++; a1[i] = 105; a2[i] = 111; i++; a1[i] = 107; a2[i] = 109; i++; a1[i] = 107; a2[i] = 111; i++; a1[i] = 111; a2[i] = 111; i++; a1[i] = 105; a2[i] = 126; i++; a1[i] = 105; a2[i] = 127; i++; a1[i] = 62; a2[i] = 214; i++; a1[i] = 107; a2[i] = 125; i++; a1[i] = 107; a2[i] = 126; i++; a1[i] = 107; a2[i] = 127; i++; a1[i] = 61; a2[i] = 237; i++; a1[i] = 111; a2[i] = 123; i++; a1[i] = 61; a2[i] = 253; i++; a1[i] = 111; a2[i] = 126; i++; a1[i] = 111; a2[i] = 127; i++; a1[i] = 126; a2[i] = 126; i++; a1[i] = 126; a2[i] = 127; i++; a1[i] = 127; a2[i] = 127; i++; a1[i] = 105; a2[i] = 150; i++; a1[i] = 105; a2[i] = 151; i++; a1[i] = 107; a2[i] = 151; i++; a1[i] = 107; a2[i] = 159; i++; a1[i] = 111; a2[i] = 159; i++; a1[i] = 107; a2[i] = 189; i++; a1[i] = 107; a2[i] = 191; i++; a1[i] = 107; a2[i] = 214; i++; a1[i] = 107; a2[i] = 215; i++; a1[i] = 107; a2[i] = 223; i++; a1[i] = 107; a2[i] = 253; i++; a1[i] = 107; a2[i] = 255; i++; a1[i] = 111; a2[i] = 246; i++; a1[i] = 111; a2[i] = 247; i++; a1[i] = 111; a2[i] = 249; i++; a1[i] = 111; a2[i] = 251; i++; a1[i] = 111; a2[i] = 255; i++; a1[i] = 126; a2[i] = 255; i++; a1[i] = 127; a2[i] = 254; i++; a1[i] = 127; a2[i] = 255; i++; a1[i] = 255; a2[i] = 255; i++;
astatnum[0]=82173l;
astatnum[1]=82173l; astatnum[2]=82173l; astatnum[3]=51060l; astatnum[4]=82173l; astatnum[5]=51060l; astatnum[6]=51052l; astatnum[7]=16836l; astatnum[8]=82173l; astatnum[9]=51052l; astatnum[10]=51060l; astatnum[11]=16836l; astatnum[12]=51060l; astatnum[13]=16836l; astatnum[14]=16836l; astatnum[15]=5750l; astatnum[16]=82173l; astatnum[17]=51060l; astatnum[18]=51052l; astatnum[19]=16836l; astatnum[20]=51052l; astatnum[21]=16836l; astatnum[22]=20472l; astatnum[23]=3071l; astatnum[24]=69868l; astatnum[25]=25777l; astatnum[26]=25777l; astatnum[27]=4021l; astatnum[28]=25777l; astatnum[29]=4021l; astatnum[30]=5000l; astatnum[31]=625l; astatnum[32]=82173l; astatnum[33]=51052l; astatnum[34]=51060l; astatnum[35]=16836l; astatnum[36]=69868l; astatnum[37]=25777l; astatnum[38]=25777l; astatnum[39]=4021l; astatnum[40]=51052l; astatnum[41]=20472l; astatnum[42]=16836l; astatnum[43]=3071ll; astatnum[44]=25777l; astatnum[45]=5000l; astatnum[46]=4021l; astatnum[47]=625l; astatnum[48]=51060l; astatnum[49]=16836l; astatnum[50]=16836l; astatnum[51]=5750l; astatnum[52]=25777l; astatnum[53]=4021l; astatnum[54]=5000l; astatnum[55]=625l; astatnum[56]=25777l; astatnum[57]=5000l; astatnum[58]=4021l; astatnum[59]=625l; astatnum[60]=9604l; astatnum[61]=784l; astatnum[62]=784l; astatnum[63]=98l; astatnum[64]=82173l; astatnum[65]=51052l; astatnum[66]=69868l; astatnum[67]=25777l; astatnum[68]=51060l; astatnum[69]=16836l; astatnum[70]=25777l; astatnum[71]=4021l; astatnum[72]=51052l; astatnum[73]=20472l; astatnum[74]=25777l; astatnum[75]=5000l; astatnum[76]=16836l; astatnum[77]=3071l; astatnum[78]=4021l; astatnum[79]=625l; astatnum[80]=51060l; astatnum[81]=16836l; astatnum[82]=25777l; astatnum[83]=4021l; astatnum[84]=16836l; astatnum[85]=5750l; astatnum[86]=5000l; astatnum[87]=625l; astatnum[88]=25777l; astatnum[89]=5000l; astatnum[90]=9604l; astatnum[91]=784l; astatnum[92]=4021l; astatnum[93]=625l; astatnum[94]=784l; astatnum[95]=98l; astatnum[96]=51052l; astatnum[97]=20472l; astatnum[98]=25777l; astatnum[99]=5000l; astatnum[100]=25777l; astatnum[101]=5000l; astatnum[102]=9604l; astatnum[103]=784l; astatnum[104]=20472l; astatnum[105]=4825l; astatnum[106]=5000l; astatnum[107]=512l; astatnum[108]=5000l; astatnum[109]=512l; astatnum[110]=784l; astatnum[111]=64l; astatnum[112]=16836l; astatnum[113]=3071l; astatnum[114]=4021l; astatnum[115]=625l; astatnum[116]=4021l; astatnum[117]=625l; astatnum[118]=784l; astatnum[119]=98l; astatnum[120]=5000l; astatnum[121]=512l; astatnum[122]=784l; astatnum[123]=64l; astatnum[124]=784l; astatnum[125]=64l; astatnum[126]=64l; astatnum[127]=8l; astatnum[128]=82173l; astatnum[129]=69868l; astatnum[130]=51052l; astatnum[131]=25777l; astatnum[132]=51052l; astatnum[133]=25777l; astatnum[134]=20472l; astatnum[135]=5000l; astatnum[136]=51060l; astatnum[137]=25777l; astatnum[138]=16836l; astatnum[139]=4021l; astatnum[140]=16836l; astatnum[141]=4021l; astatnum[142]=3071l; astatnum[143]=625l; astatnum[144]=51052l; astatnum[145]=25777l; astatnum[146]=20472l; astatnum[147]=5000l; astatnum[148]=20472l; astatnum[149]=5000l; astatnum[150]=4825l; astatnum[151]=512l; astatnum[152]=25777l; astatnum[153]=9604l; astatnum[154]=5000l; astatnum[155]=784l; astatnum[156]=5000l; astatnum[157]=784l; astatnum[158]=512l; astatnum[159]=64l; astatnum[160]=51060l; astatnum[161]=25777l; astatnum[162]=16836l; astatnum[163]=4021l; astatnum[164]=25777l; astatnum[165]=9604l; astatnum[166]=5000l; astatnum[167]=784l; astatnum[168]=16836l; astatnum[169]=5000l; astatnum[170]=5750l; astatnum[171]=625l; astatnum[172]=4021l; astatnum[173]=784l; astatnum[174]=625l; astatnum[175]=98l; astatnum[176]=16836l; astatnum[177]=4021l; astatnum[178]=3071l; astatnum[179]=625l; astatnum[180]=5000l; astatnum[181]=784l; astatnum[182]=512l; astatnum[183]=64l; astatnum[184]=4021l; astatnum[185]=784l; astatnum[186]=625l; astatnum[187]=98l; astatnum[188]=784l; astatnum[189]=64l; astatnum[190]=64l; astatnum[191]=8l; astatnum[192]=51060l; astatnum[193]=25777l; astatnum[194]=25777l; astatnum[195]=9604l; astatnum[196]=16836l; astatnum[197]=4021l; astatnum[198]=5000l; astatnum[199]=784l; astatnum[200]=16836l; astatnum[201]=5000l; astatnum[202]=4021l; astatnum[203]=784l; astatnum[204]=5750l; astatnum[205]=625l; astatnum[206]=625l; astatnum[207]=98l; astatnum[208]=16836l; astatnum[209]=4021l; astatnum[210]=5000l; astatnum[211]=784l; astatnum[212]=3071l; astatnum[213]=625l; astatnum[214]=512l; astatnum[215]=64l; astatnum[216]=4021l; astatnum[217]=784l; astatnum[218]=784l; astatnum[219]=64l; astatnum[220]=625l; astatnum[221]=98l; astatnum[222]=64l; astatnum[223]=8l; astatnum[224]=16836l; astatnum[225]=5000l; astatnum[226]=4021l; astatnum[227]=784ll; astatnum[228]=4021l; astatnum[229]=784l; astatnum[230]=784l; astatnum[231]=64l; astatnum[232]=3071l; astatnum[233]=512l; astatnum[234]=625l; astatnum[235]=64l; astatnum[236]=625l; astatnum[237]=64l; astatnum[238]=98l; astatnum[239]=8l; astatnum[240]=5750l; astatnum[241]=625l; astatnum[242]=625l; astatnum[243]=98l; astatnum[244]=625l; astatnum[245]=98l; astatnum[246]=64l; astatnum[247]=8l; astatnum[248]=625l; astatnum[249]=64l; astatnum[250]=98l; astatnum[251]=8l; astatnum[252]=98l; astatnum[253]=8l; astatnum[254]=8l; astatnum[255]=1l; }
int perms[48][27]; // The 48 symmetries of the cube
long pow2[27]; // The 27 powers of 2
void buildperms(void) {
int i,j,k,p,x,y,z,u,v,w; int n=0; long power=1;
for (i=0; i<27; i++) { pow2[i] = power; power *= 2; }
for (x=0;x<2;x++)
for (y=0;y<2;y++) for (z=0;z<2;z++) for (p=0;p<6;p++) { ; for (i=0;i<3;i++) for (j=0;j<3;j++) for (k=0;k<3;k++) { switch (p) { case 0: u=i; v=j; w=k; break; case 1: u=i; v=k; w=j; break; case 2: u=j; v=i; w=k; break; case 3: u=j; v=k; w=i; break; case 4: u=k; v=j; w=i; break; case 5: u=k; v=i; w=j; break; } if (x) u = 2-u; if (y) v = 2-v; if (z) w = 2-w; perms[n][i+3*j+9*k] = u+3*v+9*w; } n++; } }
long perm(long set, int i) // permutes set by permutation i
{
long in,out;
int j;
in = set; out = 0; for (j=0; j < 27; j++) { if (in & 1) out |= pow2[perms[i][j]]; in >>= 1; }
return out; }
int index(long set) // gives the permutation index of set of minimal size
{
long best = set, tmp; int i,j=0;
for (i=0; i < 48; i++) { tmp = perm(set, i); if (tmp < best) { best = tmp; j = i; } } return j;
}
const int bc[12] = { 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25 }; // the b points in [3]^3 const int ac[14] = { 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26 }; // the ac points in [3]^3 const int ap[8] = {0, 2, 6, 8, 18, 20, 24, 26}; // the a points in [3]^3
void init_data(void) {
int i,j,k,a; short int sig;
// allocate space
init_numstat(); // load pareto counts
for (a=0; a<256;a++)
{
data[a] = malloc(astatnum[a] * sizeof(long));
datastat[a] = malloc(astatnum[a] * sizeof(short));
}
/* enumerate the 230 line-free sets in [3]^2 by brute force */
int moser_2d[512];
int lincount=0;
for (i=0; i < 512; i++)
{
moser_2d[i] = 0;
if ((i & 7) == 7) continue; if ((i & 56) == 56) continue; if ((i & 73) == 73) continue; if ((i & 84) == 84) continue; if ((i & 146) == 146) continue; if ((i & 273) == 273) continue; if ((i & 292) == 292) continue; if ((i & 448) == 448) continue; moser_2d[i] = 1; lincount++; }
printf("Number of 2D Moser sets: %d\n", lincount);
/* Now enumerate all line-free sets in [3]^3 by brute force. */ long set, tmpset;
long slice1, slice2, slice3; int s[4]; long temp_numstat[256]; long num_linefree=0;
/* Initialise temp_numstat */ for (a=0; a<256; a++) temp_numstat[a]=0;
printf("Computing 3D Moser sets...\n");
for (slice1 = 0; slice1 < 512; slice1++) if (moser_2d[slice1]) for (slice2 = 0; slice2 < 512; slice2++) if (moser_2d[slice2]) for (slice3 = 0; slice3 < 512; slice3++) if (moser_2d[slice3]) { set = slice1 | (slice2 << 9) | (slice3 << 18);
if ((set & line_bitmasks[0]) == line_bitmasks[0]) continue; if ((set & line_bitmasks[1]) == line_bitmasks[1]) continue; if ((set & line_bitmasks[2]) == line_bitmasks[2]) continue; if ((set & line_bitmasks[3]) == line_bitmasks[3]) continue; if ((set & line_bitmasks[4]) == line_bitmasks[4]) continue; if ((set & line_bitmasks[5]) == line_bitmasks[5]) continue; if ((set & line_bitmasks[6]) == line_bitmasks[6]) continue; if ((set & line_bitmasks[7]) == line_bitmasks[7]) continue; if ((set & line_bitmasks[8]) == line_bitmasks[8]) continue; if ((set & line_bitmasks[9]) == line_bitmasks[9]) continue; if ((set & line_bitmasks[10]) == line_bitmasks[10]) continue; if ((set & line_bitmasks[11]) == line_bitmasks[11]) continue; if ((set & line_bitmasks[12]) == line_bitmasks[12]) continue; if ((set & line_bitmasks[13]) == line_bitmasks[13]) continue; if ((set & line_bitmasks[14]) == line_bitmasks[14]) continue; if ((set & line_bitmasks[15]) == line_bitmasks[15]) continue; if ((set & line_bitmasks[16]) == line_bitmasks[16]) continue; if ((set & line_bitmasks[17]) == line_bitmasks[17]) continue; if ((set & line_bitmasks[18]) == line_bitmasks[18]) continue; if ((set & line_bitmasks[19]) == line_bitmasks[19]) continue; if ((set & line_bitmasks[20]) == line_bitmasks[20]) continue; if ((set & line_bitmasks[21]) == line_bitmasks[21]) continue; if ((set & line_bitmasks[22]) == line_bitmasks[22]) continue; if ((set & line_bitmasks[23]) == line_bitmasks[23]) continue; if ((set & line_bitmasks[24]) == line_bitmasks[24]) continue;
/* now compute the a signature */ a=0; for (j=0; j < 8; j++) { if (set & pow2[ap[j]]) a |= (int) pow2[j]; }
/* now compute the a,b,c,d stats */ s[0]=s[1]=s[2]=s[3]=0; tmpset = set; for (j=0; j < 27; j++) { if (tmpset & 1l) s[stat[j]]++; tmpset /= 2; } sig = s[0] + s[1]*17 + s[2]*17*25 + s[3]*17*25*13;
data[a][temp_numstat[a]] = set;
datastat[a][temp_numstat[a]] = sig;
temp_numstat[a]++; num_linefree++; if (num_linefree % 10000 == 0) printf("*"); }
printf("\nNumber of 3D Moser sets: %ld\n", num_linefree); // checksum for (a=0; a<256; a++) if (astatnum[a] != temp_numstat[a]) printf("Inconsistency at %d! %ld != %ld\n", a,astatnum[a],temp_numstat[a]); }
- define NUM_CRUSH 144
const int expand[NUM_CRUSH] = {0, 1, 3, 6, 7, 15, 19, 20, 21, 22, 23, 28, 29, 31, 54, 55, 56, 57, 58, 59, 62, 63, 96, 97, 99, 101, 102, 103, 111, 112, 113, 115, 116, 117, 118, 119, 124, 125, 127, 240, 241, 243, 246, 247, 255, 270, 271, 284, 285, 286, 287, 318, 319, 324, 325, 327, 332, 333, 334, 335, 343, 348, 349, 350, 351, 360, 361, 362, 363, 364, 365, 366, 367, 377, 379, 380, 381, 382, 383, 449, 451, 454, 455, 457, 459, 462, 463, 468, 469, 470, 471, 473, 475, 476, 477, 478, 479, 497, 498, 499, 502, 503, 504, 505, 506, 507, 510, 511, 876, 877, 879, 895, 911, 924, 925, 927, 938, 939, 942, 943, 958, 959, 995, 998, 999, 1005, 1007, 1011, 1013, 1014, 1015, 1020, 1021, 1023, 1782, 1783, 1785, 1787, 1791, 2013, 2015, 2046, 2047, 4095}; // minimal b-labels
int crush[4096]; // maps the label of a b-word to the label of its minimal permutation int crushperm[4096]; // maps the label of a b-word to the permutation used to minimise it
void buildhash(void)
{
int i,j,k,count=0; long l,m;
printf("Building hash...");
for (i = 0; i<4096;i++)
{ j=i; l=0; for (k=0;k<12;k++) { if (j & 1) l |= pow2[bc[k]]; j >>=1; } // l is now the b-word associated to i crushperm[i] = index(l); // printf("%o (%lo) crushed by %d ", i, l, crushperm[i]); m = perm(l, crushperm[i]); // printf("and permuted to %o ", m);
j=0; for (k=0;k<12;k++) if (m & pow2[bc[k]]) j |= pow2[k]; // j is now the label of the reduction of l
// printf(" (i.e. %d)", j); for (k=0; k<NUM_CRUSH; k++) if (expand[k] == j) crush[i] = k;
if (i == expand[crush[i]]) { // printf("%d ", i); count++; }
} printf("done, with %d a-signatures.\n", count); // printf("Total mins: %d\n", count); }
- define MAX_PARETO 27 // at most 27 pareto-optimals per forbidden set
short int table[144][16384][MAX_PARETO];
void read_lookup(void)
{
FILE *input = fopen("newlookup.dat", "rb");
printf("Loading lookup table...\n"); int i, j, k; for (i=0; i<144; i++) { printf("."); for (j=0; j<16384; j++) fread(table[i][j],sizeof(short int),MAX_PARETO,input); } printf("\nTable loaded!\n");
}
- define NUMOUTER 16575 // total number of stats for the Level 1/Level 3 pair
char feasible[NUMOUTER][NUM_PARETO][2]; // feasible[a][b][c] means that there is a Level 1/Level 3 pair with total statistic a whose Level 2
// forbidden set (minus 222) permits the statistic b; if c=1, then the forbidden set contains 222
int test( long forbidden, int numouter ) // see what statistics are compatible with a forbidden set. Note that the 222 bit is ignored.
{
int i,j,k,l,a,b,x,y,z,w;
long forb, recon;
int hascenter = ((forbidden & pow2[13]) > 0); // 1 if forb contains 2222
// printf("Testing %lo (= %ld in decimal)\n", forbidden, forbidden); // printf("(%lo)", forbidden);
a=0; for (k=0;k<12;k++)
if (forbidden & pow2[bc[k]]) a |= pow2[k];
forb = perm(forbidden, crushperm[a]); a = crush[a];
// printf("Permuted version: %lo (= %ld in decimal), using permutation %d\n", forb, forb, crushperm[a]);
b=0;
for (k=0;k<14;k++)
if (forb & pow2[ac[k]]) b |= pow2[k];
// printf("Hashes: %o %o \n", a, b );
recon = 0;
for (k=0;k<12;k++)
if (expand[a] & pow2[k]) recon |= pow2[bc[k]];
for (k=0;k<14;k++)
if (b & pow2[k]) recon |= pow2[ac[k]];
// printf("Reconstituted permutation: %lo (= %ld in decimal)\n", recon, recon);
int count=0; for (i=0;i<MAX_PARETO;i++)
{ j = table[a][b][i]; if (j==-1) break; feasible[numouter][j][hascenter] = 1; // printf("<%d %d %d> ", numouter, j, hascenter); count++; }
return count; }
- define NUM_4D_LINES 125 // the nonhorizontal bitmasks
long masks[3][NUM_4D_LINES]; // the three bitmasks for each of the lines
void create_4d_lines(void)
{
int i,j,k; int count;
printf("Building 4d lines...");
count=0; for (i=0;i<27;i++) for (j=0;j<27;j++) for (k=0;k<27;k++) if (i+k == 2*j) if ((i/3)+(k/3) == 2*(j/3)) if ((i/9)+(k/9) == 2*(j/9)) { masks[0][count] = pow2[i]; masks[1][count] = pow2[j]; masks[2][count] = pow2[k]; count++; } printf("done, with %d lines.\n", count);
}
double done=0;
double total;
void testpair(int stage, int x, int y) // scans all Level 1/Level 3 pairs with a-signatures x, y respectively
{
int i,j,k; int numouter; long level1, level2, level3;
printf("%lf percent done\n", done * 100 / total ); printf("Testing stage %d (%d,%d) - %lu pairs\n", stage, x, y, astatnum[x] * astatnum[y]); done += astatnum[x] * astatnum[y];
for (i=0; i<astatnum[x]; i++)
for (j=0; j<astatnum[y]; j++)
{
numouter = datastat[x][i] + datastat[y][j]; // the total stats of the level 1/ level 3 pair
level1 = data[x][i];
level3 = data[y][j]; // compute the level 1 / level 3 pairs
level2 = 0;
for (k=0; k<NUM_4D_LINES; k++)
if ((level1 & masks[0][k]) && (level3 & masks[2][k])) level2 |= masks[1][k];
// printf("\n[%lo %lo %lo] \n", level1, level3, level2);
test(level2,numouter); // level2 is the forbidden set
}
}
char paretos[17][33][25][9][2]; // paretos[a][b][c][d][e] = 1 if (a,b,c,d,e) is found to be feasible
FILE * output;
void analyse(void) // dump the feasible table
{
int i,j,k; int a,b,c,d,e; int b0,c0,d0;
for (i=0; i<NUMOUTER; i++) { a = i%17; b0 = (i/17)%25; c0 = (i/(17*25))%13; d0 = (i/(17*25*13)); // the outer layers (Level 1, Level 3) contribute to a,b,c,d statistics for (j=0; j<NUM_PARETO;j++) for (k=0; k<2; k++) if (feasible[i][j][k]) { b=b0 + alist[j]; // The middle layer (Level 2) contribute to b,c,d,e statistics c=c0 + blist[j]; d=d0 + clist[j]; if (k==0) e = dlist[j]; else e=0; if (paretos[a][b][c][d][e] == 0) { printf("Feasible: (%d %d %d %d %d)\n", a, b, c, d, e); fprintf(output, "%d %d %d %d %d\n", a, b, c, d, e); paretos[a][b][c][d][e] = 1; } } }
}
void main(int argc, char* argv[])
{
int i,j,k,l,m; long forb, forb_base;
if (argc < 3)
{ printf("Need two arguments: '%s x y', where 0 <= x <= y <= 390.\n", argv[0]); printf("Or '%s x y count', if one only wants a pair count.\n", argv[0]); return; }
int x = atoi(argv[1]); int y = atoi(argv[2]);
if ( (x<0) || (x>y) || (y>390) )
{ printf("Need 0 <= x <= y <= 390, sorry!\n"); return; }
char str[100];
buildperms(); buildhash(); create_4d_lines(); init_numstat();
printf("Scanning the pairs from class #%d to class #%d.\n", x, y);
total=0;
for (i=x; i<=y; i++)
total += (double) astatnum[a1[i]] * (double) astatnum[a2[i]];
printf("Number of pairs in this scan: %lf (=%lf percent of total)\n", total, total*100 / 62009590818l);
if (argc > 3) return;
strcpy(str, "output_");
strcat(str, argv[1]);
strcat(str, "_");
strcat(str, argv[2]);
strcat(str, ".txt");
output = fopen(str,"w");
printf("All pairs found will be output to %s.\n", str);
init_data(); read_lookup();
for (i=0; i<17; i++)
for (j=0; j<33; j++) for (k=0; k<25; k++) for (l=0; l<9; l++) for (m=0; m<2; m++)
paretos[i][j][k][l][m] = 0; // initialise the table of feasible 4D statistics
for (i=0; i<NUMOUTER; i++)
for (j=0; j<NUM_PARETO; j++) for (k=0; k<2; k++) feasible[i][j][k]=0; // initialise the compressed table of feasible 4D statistics
for (i=x; i<=y; i++)
{ testpair(i,a1[i], a2[i]); // scan stage i analyse(); // convert the compressed table to uncompressed, dump any new statistics obtained }
fclose(output);
}
