Small gaps in the Ulam sequence

The Ulam sequence, described by Stanisław Ulam in the 1960s, starts 1, 2 and then iteratively adds the smallest integer that can be uniquely written as the sum of two distinct earlier terms: this gives 1,2,3,4,6,8,11,⋯ Already in 1972 the great French poet Raymond Queneau wrote that it “gives an impression of great irregularity”. This irregularity appears to have a lot of structure and has inspired a great deal of work; nonetheless, very little is actually known. We improve the best upper bound on its growth and show that some small gaps have to exist: for some c>0 and all n∈ℕ, min 1≤k≤n a k+1 a k ≤1+clogn n.