// C++ code to compute sequence A263453 in the OEIS, by Eric M. Schmidt. // I hereby waive all rights to this code, in accordance with the CC0 // waiver: // http://creativecommons.org/publicdomain/zero/1.0/ #include #include #include #include #include // For mpz_class // Select integer type for sequence values. Should be able to hold // the partition numbers up to where you are computing the sequence. using LargeInt = mpz_class; // A table of Grundy numbers for Kayles template struct KaylesTable { KaylesTable() : values() { std::array excluded; for (int i = 1; i < tableSize; ++i) { std::fill_n(excluded.begin(), i+1, false); for (int j = 0; j <= (i-1)/2; ++j) { int const k = (i-1) - j; excluded[values[j] ^ values[k]] = true; } for (int j = 0; j <= i/2 - 1; ++j) { int const k = (i-2) - j; excluded[values[j] ^ values[k]] = true; } int const nextvalue = std::find(excluded.begin(), excluded.end(), false) - excluded.begin(); values[i] = nextvalue; } } std::array values; }; // Returns the Grundy number of Kayles with n pins in a row. int kayles(int n) { constexpr int period = 12; constexpr int numperiods = 7; constexpr int tableSize = period * numperiods; static KaylesTable const table; if (n < tableSize) return table.values[n]; return table.values[(tableSize - period) + (n % period)]; } // Compute a(n) for 0 <= n < bound. std::vector A263453(int bound) { constexpr int gnBound = 16; std::vector> gnCounts(bound); // After iteration d, gnCounts[n][gn] holds the number of n-pin // arrangements with no more than d pins in any group, // with Grundy number gn. gnCounts[0][0] = 1; for (int d = 1; d < bound; ++d) { int const kayles_d = kayles(d); for (int n = bound-1; n >= 0; --n) { for (int j = 1; j*d <= n; ++j) { // We consider removing j groups of size d from // a group of i pins. int const removedgn = (j%2 ? kayles_d : 0); int const k = n - j*d; for (int gn = 0; gn < gnBound; ++gn) gnCounts[n][gn] += gnCounts[k][gn ^ removedgn]; } } } // Fetch the values for Grundy number 0 std::vector result(bound); std::transform(gnCounts.begin(), gnCounts.end(), result.begin(), [](auto const & gNumbers) { return gNumbers[0]; } ); return result; } int main() { constexpr int maxIndex = 10000; std::vector const table(A263453(maxIndex+1)); for (int n = 0; n <= maxIndex; ++n) std::cout << n << ' ' << table[n] << '\n'; }