The length-restricted antipalindrome sum conjecture

An antipalindrome is a natural number whose canonical base-22 expansion is an antipalindromic word, meaning that the word equals the complement of its reversal. An even integer has an even least significant bit. For an odd integer length n9n\geq 9, consider even integers whose canonical base-22 expansions have length nn.

The length-restricted antipalindrome sum conjecture. Every even integer of length nn, for nn odd and n9n\geq 9, is the sum of at most 1010 antipalindromes of length n3n-3.

The conjecture is intended to be proved using nondeterministic pushdown automata, but the authors' computations were incomplete because their program ran out of space. They hoped to establish it as a theorem in a future version; its truth would imply that every even natural number is the sum of at most 1313 antipalindromes.

Sources & referencesView supporting material

Primary source

Aayush Rajasekaran, Jeffrey Shallit and Tim Smith, “Sums of Palindromes: an Approach via Automata”, arXiv:1706.10206 (2017).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.