Enumerating Cryptarithms Using Deterministic Finite Automata

2018/07/27 by Yuki Nozaki, Nozaki, Yuki, Diptarama Hendrian +7
Computer Science · #Coding theory and cryptography #Cryptography and Data Security #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1807.11580

openalex publication_date 2018/07/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

A cryptarithm is a mathematical puzzle where given an arithmetic equation written with letters rather than numerals, a player must discover an assignment of numerals on letters that makes the equation hold true. In this paper, we propose a method to construct a DFA that accepts cryptarithms that admit (unique) solutions for each base. We implemented the method and constructed a DFA for bases k ≤ 7. Those DFAs can be used as complete catalogues of cryptarithms,whose applications include enumeration of and counting the exact numbers G_k(n) of cryptarithm instances with n digits that admit base-k solutions. Moreover, explicit formulas for G₂(n) and G₃(n) are given.

Related

• Cryptarithmically unique terms in integer sequences
• The Dead Cryptographers Society Problem
• Counting Solutions to Discrete Non-Algebraic Equations Modulo Prime Powers
• On the Representation of Finite Automata
• Autómatas celulares elementales aplicados a la encriptación de datos