#include #include // exit #include // memset using namespace std; enum GROUPS {PAIRS=2, TRIPLETS=3, QUADS=4}; const int PRINT_THIS_OR_HIGHER = PAIRS; // Can't reach 5 or higher (time or memory) const int MAXGROUPSIZE = QUADS; /* Parallel bit-count population algorithm and assembly most-significant-bit. Challenge and support (for full docs) https://www.sololearn.com/Discuss/622449/?ref=app https://code.sololearn.com/cZX2I8giW2zV/?ref=app INPUT: 3 to ~56000 (if wanting quads) Curious: The first two triples are doubles of each other Doubles : input = 33+ Triples : 2060+ 82 triples < 56000 Quads : 33012+ 2 quads <= 36036 */ struct quark_t { unsigned long total = 0; int members = 0; unsigned long memberList[MAXGROUPSIZE]; }; // no objects to start with quark_t* theArray; // how many bits are set? See companion code. unsigned long population(unsigned long of) { unsigned long x; // The algorithm with final substitutions of = of - ((of >> 1) & 0x55555555); x = (of & 0x33333333) + ((of >> 2) & 0x33333333); return ((x + (x >> 4) & 0x0F0F0F0F) * 0x01010101) >> 24; } // Inline assembly: BSR is FAST // Bitscan Reverse returns 0-based bit offset // Answers: What's the highest bit set? // Function returns max value for that bit // Example: 63: 6 bits = 63*6 = 378 // Then, no pair with sum > 378 can be generated. int msb, maxTotals; int getMaxValueFor(unsigned long zig) { asm("bsr %1,%0" : "=r"(msb) : "r"(zig)); maxTotals = 2 << msb; return (msb+1) * (maxTotals-1); } void freeMemory() { delete [] theArray; theArray = NULL; } int main() { char NL = '\n'; unsigned long zig; // input cin >> zig; // The total can never exceed this // I refactored not to need it, but I do need maxTotals int maxValue = getMaxValueFor(zig); int sz_qt = sizeof new quark_t[1]; // size of a quark theArray = new quark_t[maxTotals]; // array of quarks memset(theArray, 0, sz_qt * maxTotals); // zap it int uniques = 0; // First we zig while(zig > 2) { unsigned long total = population(zig)*zig; int scan = 0; while(scan < uniques) if(theArray[scan++].total == total) break; if(scan == uniques) uniques += 1; else scan -= 1; if(theArray[scan].members == MAXGROUPSIZE) { cout << theArray[scan].members; freeMemory(); cout << NL << "Houston--we have a problem. Too many members for total: " << total << " @(" << zig << ")" << endl; exit(1); // ZOMG IT'S ALL ON FIRE! } theArray[scan].total = total; theArray[scan].memberList[theArray[scan].members++] = zig--; } unsigned long zag = uniques; // zig zag while(zag --> 0) { int members = theArray[zag].members; if(members >= PRINT_THIS_OR_HIGHER) for(int i=0; i

Quarks: pair/triple/quads : parallel bitcount + assembly msb [challenge]