#include <cstring> #include <iostream> #include <unordered_set> #include <utility> constexpr int maxn = 64; unsigned long long mask[maxn]; // A087207 mask of prime factors bool visited[maxn]; int S[maxn]; struct pair_hash { inline std::size_t operator()(const std::pair<int, unsigned long long> & v) const { return v.second; } }; struct layer { int maxv = 0; std::unordered_set<std::pair<int, unsigned long long>, pair_hash> blocks[1+maxn][1+maxn]; void add(int i, int j, int v, unsigned long long m) { if (maxv < v) { maxv = v; } blocks[i][j].insert(std::make_pair(v, m)); } size_t size() const { size_t s = 0; for (int i = 1; i <= maxn; i++) { for (int j = 1; j <= maxn; j++) { s += blocks[i][j].size(); } } return s; } }; layer bottom; // n: maximum k // s: current term S[k] // m: mask of prime factors that are mandatory in S[k+1] // f: mask of prime factors that are forbidden in S[k+1] // k: current index void explore_blocks(int n, int s, unsigned long long m, unsigned long long f, int k) { S[k] = s; if (m==0) { // this is a new block. // a block is characterized by: // - its endpoints, // - its values. unsigned long long mask_of_values = 0; for (int i = 1; i <= k; i++) { mask_of_values |= 1LL << (S[i]-1); } bottom.add(S[1], S[k], k, mask_of_values); } else { visited[s] = true; for (int z = 1; z <= n; z++) { if (!visited[z] && (mask[z] & m)==m && (mask[z] & f)==0) { explore_blocks(n, z, mask[z]-m, m, k+1); } } visited[s] = false; } } void explore_blocks(int n) { for (int s = 1; s <= n; s++) { explore_blocks(n, s, mask[s], 0, 1); } } int maxv; void grow(const layer& middle) { layer *xtop = new layer; layer &top = *xtop; for (int i = 1; i <= maxn; i++) { for (int j = 1; j <= maxn; j++) { if (bottom.blocks[i][j].size()) { for (int k = 1; k <= maxn; k++) { if ((mask[j] & mask[k])==0) { for (int l = 1; l <= maxn; l++) { for (const auto & b : bottom.blocks[i][j]) { for (const auto & m : middle.blocks[k][l]) { if ((b.second & m.second)==0) { top.add(i, l, b.first + m.first, b.second + m.second); } } } } } } } } } if (top.maxv) { if (maxv < top.maxv) { maxv = top.maxv; } grow(top); } delete xtop; } int a(int n) { maxv = bottom.maxv; grow(bottom); return maxv; } int main() { std::memset(mask, 0, sizeof(mask)); std::memset(visited, 0, sizeof(visited)); unsigned long long b = 1; int v = 0; // last value for (int n = 1; n<maxn; n++) { bool is_prime = false; if (n > 1 && !mask[n]) { is_prime = true; if (!b) { std::cerr << "# bug" << std::endl; return 1; } for (int m = n; m < maxn; m += n) { mask[m] += b; } b *= 2; } if (!is_prime) { explore_blocks(n); v = a(n); } std::cout << n << ' ' << v << std::endl; } return 0; }