// A360306 - a(n) is the smallest positive integer which can be represented as the sum of n distinct nonzero fourth powers in exactly n ways, or -1 if no such integer exists. // C++ program by Bert Dobbelaere #include #include #include #include #if 1 // Quick demo const int NMAX = 30; const uint64_t LUTSIZE = 10000000; #else // Parameters used to create b-file. Requires 64GB of RAM. const int NMAX = 80; const uint64_t LUTSIZE = 780000000; #endif uint8_t *lut[NMAX+1]; void initLUT() { std::cout << "Allocating lookup table." << std::endl; for(int i=0 ; i<=NMAX ; i++) { lut[i] = new uint8_t[LUTSIZE]; memset(lut[i], 0, LUTSIZE*sizeof(uint8_t)); } uint64_t s4=0, k4=0; lut[0][0]=1; for(uint64_t k=1;;k++) { std::cout << "Adding sums with largest term = " << k << "^4 to table" << std::endl; k4 = k*k*k*k; s4 += k4; if(k4 >= LUTSIZE) break; for(int j=NMAX-1 ; j>=0 ; j--) { uint64_t lim = (s4 >= LUTSIZE) ? LUTSIZE : s4; for(uint64_t x=lim ; x>=k4 ; x--) { int s= lut[j+1][x] + lut[j][x-k4]; lut[j+1][x]= s>255 ? 255:s; // Saturate at 255, allows single byte storage (as long as n<255, that's OK) } } } } int main() { initLUT(); for(int n=1;n<=NMAX;n++) { assert(n<255); // Must stay below saturation limit in LUT uint64_t x=0; bool found=false; while(x= " << LUTSIZE << " if it exists" << std::endl; } } for(int i=0 ; i<=NMAX ; i++) { delete[] lut[i]; } return 0; }