// Code to compute sequence A277496 in the OEIS. // By Eric Schmidt. // I hereby waive all rights to the work, in accordance with the CC0 // Public Domain Dedication: // https://creativecommons.org/publicdomain/zero/1.0/ // // This code uses Google's dense_hash_set: // // https://github.com/sparsehash/sparsehash #include #include #include #include #include constexpr int Base{7}; namespace { constexpr int numThreads{4}; // Let k = mid - first. By repeatedly calling this function, the range // [first, mid) will contain all k-permutations of [first, last). They are // enumerated in lexicographical order. Returns false to indicate that we // wrapped around to the lexicographically smallest permutation. template bool next_partial_permutation(BidirIter first, BidirIter last, BidirIter mid) { std::reverse(mid, last); return std::next_permutation(first, last); } using LargeInt = long long; // An integer for which equality does not depend on the sign. // The purpose is that we negate a value in the hash table to indicate that // the corresponding problem has more than one solution. struct FuzzyInt { mutable LargeInt value{0}; }; bool operator==(FuzzyInt x, FuzzyInt y) { return x.value == y.value || x.value == -y.value; } struct FuzzyIntHash { size_t operator() (FuzzyInt fi) const { return std::hash()(fi.value); } }; int factorial(int n) { int result(1); for (int i = 2; i <= n; ++i) result *= i; return result; } // The inner loop of uniquecount. For the given digit assignment, we // determine the sum word, and update the count appropriately. void examinedigitchoice ( unsigned int const & word1length, std::vector const & word2, int const & numLetters, std::vector const & relettering, bool const & symmetricSummands, google::dense_hash_set & found, LargeInt & count, std::vector const & lettertodigit, std::vector & digittoletter, std::vector & digitsofsum ) { int const unusedSlot{Base}; // Skip cases where a word begins with zero if (lettertodigit[word1length - 1] == 0 || lettertodigit[word2.back()] == 0) return; // Compute inverse correspondence of lettertodigit std::fill(digittoletter.begin(), digittoletter.end(), unusedSlot); for (int i = 0; i < numLetters; ++i) digittoletter[lettertodigit[i]] = i; // Find digits of the sum int carry = 0; unsigned int sumidx = 0; for (; sumidx < word1length; ++sumidx) { int const word1digit(lettertodigit[sumidx]); int const word2digit(sumidx < word2.size() ? lettertodigit[word2[sumidx]] : 0); int const sum(word1digit + word2digit + carry); digitsofsum[sumidx] = sum % Base; carry = sum / Base; } if (carry) digitsofsum[sumidx++] = 1; // Compute numerical "hash" value for the word corresponding to the sum. LargeInt power{1}; LargeInt hashval{0}; int lettersUsed{numLetters}; bool relettergreater{false}; for (unsigned int i = 0; i < sumidx; ++i) { int const digit(digitsofsum[i]); int letter(digittoletter[digit]); if (letter == unusedSlot) { letter = lettersUsed++; digittoletter[digit] = letter; } // If symmetricSummands is set, compute the word we would get if we // swapped the summands and relettered. If it is lexicographically // less, then we discard this instance as a duplicate. else if (symmetricSummands && !relettergreater && letter < numLetters) { if (relettering[letter] < letter) return; if (relettering[letter] > letter) relettergreater = true; } hashval += letter * power; power *= Base; } hashval += power; // Ensure uniqueness of hashval auto const insertResult(found.insert(FuzzyInt{hashval})); // Increase count if this is a new problem. if (insertResult.second) ++count; else { if (insertResult.first->value == hashval) { // We found a problem with more than one solution, so uncount it. --count; insertResult.first->value = -hashval; } } } // Count the number of puzzles (with unique solutions) for two given summands. //The first word always has A for the ones place, and so on. LargeInt uniquecount ( unsigned int const word1length, std::vector const & word2, int const numLetters ) { int const unusedSlot{Base}; // Compute the problem we get if we reverse the two words. // If this problem is lexicographically smaller, it would be a duplicate, // so we return. // If both problems are the same, we set symmetricSummands to indicate // that we should be careful of overcounting later. std::vector relettering; bool symmetricSummands{false}; if (word1length == word2.size()) { relettering.resize(numLetters); std::fill(relettering.begin(), relettering.end(), unusedSlot); for (unsigned int i = 0; i < word1length; ++i) relettering[word2[i]] = i; int lettersAssigned = word1length; for (unsigned int i = 0; i < word1length; ++i) { int letter = relettering[i]; if (letter == unusedSlot) letter = lettersAssigned++; relettering[i] = letter; } auto const newword2begin = relettering.begin(); auto const newword2end = newword2begin + word1length; bool const newisless(std::lexicographical_compare (newword2begin, newword2end, word2.begin(), word2.end())); if (newisless) return 0; bool const newisequal(std::equal (newword2begin, newword2end, word2.begin())); if (newisequal) symmetricSummands = true; } google::dense_hash_set found(factorial(Base)); found.set_empty_key(FuzzyInt{0}); LargeInt count{0}; std::vector lettertodigit; for (int i = 0; i < Base; ++i) lettertodigit.push_back(i); std::vector digittoletter(Base); std::vector digitsofsum(Base+1); auto const dfirst = lettertodigit.begin(); auto const dlast = lettertodigit.end(); auto const dmid = dfirst + numLetters; do { examinedigitchoice(word1length, word2, numLetters, relettering, symmetricSummands, found, count, lettertodigit, digittoletter, digitsofsum); } while (next_partial_permutation(dfirst, dlast, dmid)); return count; } int fallingfactorial(int n, int k) { int result{1}; for (int j = n-k+1; j <= n; ++j) result *= j; return result; } // Count the number of possible second summands for the given lengths. int numword2(int const word1length, int const word2length) { int result{0}; for (int i = 0; i <= Base - word1length; ++i) { result += fallingfactorial(word1length, word2length - i) * fallingfactorial(word2length, i) / factorial(i); } return result; } LargeInt workItem ( std::vector letterpool, int const word1length, int const word2length, int numIters ) { int const unusedSlot{Base}; LargeInt count{0}; auto const dfirst = letterpool.begin(); auto const dlast = letterpool.end(); auto const dmid = dfirst + word2length; for (int i = 0; i < numIters; ++i) { std::vector word2; int numLetters{word1length}; for (auto iter = dfirst; iter < dmid; ++iter) { int const letter(*iter); word2.push_back (letter == unusedSlot ? numLetters++ : letter); } count += uniquecount(word1length, word2, numLetters); next_partial_permutation(dfirst, dlast, dmid); }; return count; } LargeInt A277496() { int const unusedSlot{Base}; LargeInt totalcount{0}; std::vector letterpool(Base); for (int word1length = 1; word1length <= Base; ++word1length) { for (int word2length = 1; word2length <= word1length; ++word2length) { for (int i = 0; i < word1length; ++i) letterpool[i] = i; for (int i = word1length; i < Base; ++i) letterpool[i] = unusedSlot; auto const dfirst = letterpool.begin(); auto const dlast = letterpool.end(); auto const dmid = dfirst + word2length; int const numItems(numword2(word1length, word2length)); int const chunkSize(numItems / numThreads); std::vector> values; for (int i = 0; i < numThreads-1; ++i) { values.push_back(std::async(std::launch::async, workItem, letterpool, word1length, word2length, chunkSize)); for (int j = 0; j < chunkSize; ++j) next_partial_permutation(dfirst, dlast, dmid); } int const itemsLeft(numItems - chunkSize*(numThreads-1)); totalcount += workItem (letterpool, word1length, word2length, itemsLeft); for (auto & f : values) totalcount += f.get(); } } return totalcount; } } int main() { std::cout << A277496() << '\n'; }