Paperlane

no. 15 · Monday 16 November 2026

The Ulam sequence grows subexponentially

Noah Kravitz

math.CO

Abstract

We prove that the $n$-th element of the Ulam sequence, a somewhat mysterious recursively-defined sequence of positive integers, has size $e^{O(\sqrt{n})}$; previous upper bounds were exponential in $n$. Our argument uses an additive-combinatorial lemma, possibly of independent interest, about covering finite difference sets with multiplicatively short intervals. The proofs are due to ChatGPT.

fields
Combinatorics, Number Theory
pdf ↗ page arXiv:2611.17584 ↗