Code: #include <stdio.h> /* the code is also attached as a zip file - the program is demonstrated for 3/13 as 6/55 will produce a huge listing and take too long to execute */ const unsigned int numdraws = 3; /* in the real lotto this will be 6 */ const unsigned int maxserial = 13; /* in the real lotto this will be 55 */ const unsigned int bits_per_char = 8; /* in the real lotto this will be bits_per_long = 32 */ int writecombin(FILE *fp, unsigned char c1, unsigned char c2, unsigned int maxcheck); unsigned int findsetbitcount(unsigned char c); void main() { unsigned char c1 , c2, maxval, carry, residue_bits; /* in the real lotto this will be unsigned long */ /* The program assumes that you need to compute non-repeating numbers i.e. in a draw of 6 you cant have a combination like : 1-5-12-5-19-1 (both 1 and 5 are repeated) if you can have repeating numbers the program will be have to be modified bits 0 .. 7 from c1 denote integers 1 .. 8 bits 0 .. 4 from c2 denote integers 9 .. 13 i.e. residue_bits is 5 If bits 0, 3 are set in c1 and bit 2 is set in c2 the draw is 1-4-11 If bits 0, 3 are set in c1 and NO bit is set in c2 the draw is 1-4 this is invalid since the no of draws is ONLY 2 Similarly If bits 0, 2, 6 are set in c1 and bits 1, 2, 4 are set in c2 the draw is 1-3-7-10-11-13 this is invalid since the no of draws is 6 i.e. we take only draws where the total no of bits set (in c1 and c2 combined) is 3 in the real lotto the valid combinations will be cases where the total no of bits (c1 c2 combined) is 6 in real lotto c1 & c2 will be unsigned long bits 0 .. 31 from c1 will denote integers 1 .. 32 bits 0 .. 22 from c2 will denote integers 33 .. 55 i.e. residue_bits is 23 */ FILE *fp; c1 = c2 = 0; residue_bits = maxserial % bits_per_char; /* no of bits we need from c2 - in real lotto bits_per_long */ /* we will use bit numbers 0 .. (residue_bits - 1) from c2 ( once c2 == 1 << residue_bits all the combinations involving 1 .. 13 (1 .. 55 in real lotto) */ maxval = (1 << residue_bits); fp = fopen("combin.txt", "w"); while( c2 < maxval ) { /* keep incrementing c1 in every iteration - if there is overflow ie MSB in c1 which is set before increment is cleared after increment then increment c2 for each iteration check the total no of bits set in c1 & c2 combined - if it equals the no of draws note as valid combination since we are using 0 .. (residue_bits - 1) from c2 the process stops when bit no <residue_bits> is set in c2 - this will happen only in the iteration after all the possible bits are set in c1 (1111 1111) & c2 (0001 1111) */ carry = c1; c1++; if( carry > c1 ) /* True ONLY when MSB in c1 is SET BEFORE increment and CLEARED AFTER increment */ c2++; if( findsetbitcount(c1) + findsetbitcount(c2) == numdraws ) { /* if total bits set == no of draws note this as a valid combination */ writecombin(fp, c1, c2, maxserial); } } fclose(fp); } unsigned int findsetbitcount(unsigned char val) { /* return the no of bits set in val */ unsigned int i, setbits; for( i = 0, setbits = 0; i < bits_per_char; i++ ) if( val & (1 << i) ) setbits++; return setbits; } int writecombin(FILE *fp, unsigned char c1, unsigned char c2, unsigned int maxcheck) { unsigned char c; unsigned int i, bitcount, serialno; for( i = 0, bitcount = 0; i < maxcheck; i++ ) { c = (i >= bits_per_char ? c2 : c1); if( c & (1 << (i % bits_per_char)) ) { if( bitcount ) fprintf(fp, "-"); fprintf(fp, "%u", i + 1); bitcount++; } } fprintf(fp, "\n"); return bitcount; }