// 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;
}