Testing Transformer Learnability on the Arithmetic Sequence of Rooted Trees

Prime factorization, the decomposition of a natural number into its constituent primes, lies at the crossroads of arithmetic, complexity theory, and computational practice. While every integer admits a unique factorization, the operational effort required to obtain it grows quickly with its magnitude. State-of-the-art algorithms achieve remarkable performance for moderately large inputs, yet their complexity escalates rapidly when confronted with truly large instances. Moreover, in this limit, the sequence of integers with known prime factorizations becomes effectively sparse, with regions where the factorizations of intermediate values are computationally inaccessible. It is therefore natural to ask whether modern machine learning methods, and more specifically Large Language Models (LLMs), can offer any advantages from this perspective.