// OEIS A306746 - C++ program by Bert Dobbelaere // // "A Goldbug number is an even number 2m for which there exists some subset of the // prime non-divisors (PNDs) of 2m, 2 < p1 < p2 < p3 < ... < pk < m, such that // (2m-p1)*(2m-p2)*(2m-p3)*...*(2m-pk) has only p1,p2,p3,...,pk as factors. A Goldbug // number is called order k if the maximal subset satisfying the property is of size k." // About the algorithm: // We find the maximal subset of primes by iterative elimination of elements that imply // factors in the product above that are not allowed. // First, all odd numbers < 2m_max (M2MAX constant) are factored, factors and primes are // stored in tables. The algorithm initially marks all odd primes < m as "allowed", all // other integers < 2m as "disallowed", then removes the factors of 2m from the allowed set. // Each "elimination round", any "allowed" prime p will become "disallowed" if (2m-p) // contains at least one disallowed factor. The elimination process is repeated as long as // at least one prime was removed from the list. If the resulting list is nonempty, 2m is a // Goldbug number and the length of the "allowed list" is its order. // Implementation notes: // Program contains some large statically allocated arrays. // Potential memory improvements: // - storing only odd values would halve the memory requirements. // - factorisation of numbers below m is only accessed during initialisation // Storing the factors in a rectangular array rather than using a pointer table eliminates // an indirection level. The primes in the candidate set are represented in two ways: once // in an master array of booleans (optimal for random access), and two times as simple arrays of // "allowed" primes at a given time (optimized for sequential access). #include #include #include #define M2MAX 30000000 // "Maximum value for 2m" #define MAXFACTORS 8 // Support (MAXFACTORS-1) distinct odd prime factors: value 8 is OK for 2m < 1.115e8. #define MAXPRIMES (M2MAX/5) // Overestimate of the number of primes below M2MAX (provided default ok for large M2MAX) #define LAST 0xFFFFFFFFu // Last factor marker typedef unsigned u32; // Arrays filled during initialisation: u32 factors[M2MAX][MAXFACTORS]; // odd prime factors of numbers 0) // Maximal set is nonempty { // We found a Goldbug number of order srccnt. printf("%u is a Goldbug number of order %u.\nMaximal set: [",m2,allowedcount); for(u32 k=0;k<(srccnt-1);k++) printf("%u, ",src[k]); printf("%u]\n\n",src[srccnt-1]); } } int main() { initfactors(); for(u32 m2=2;m2<=M2MAX;m2+=2) { if(m2%100000==0) printf(" ....(%u)\n",m2); solve(m2); } printf("Done searching Goldbug numbers <= %u.\n",M2MAX); return 0; }