Lower bounds on the lengths of double-base representations

Abstract:

A double-base representation of an integer $n$ is an expression $n = n_1 + \cdots + n_r$, where the $n_i$ are (positive or negative) integers that are divisible by no primes other than $2$ or $3$; the length of the representation is the number $r$ of terms. It is known that there is a constant $a >0$ such that every integer $n$ has a double-base representation of length at most $a\log n / \log \log n$. We show that there is a constant $c>0$ such that there are infinitely many integers $n$ whose shortest double-base representations have length greater than $c\log n / (\log \log n \log \log \log n)$.

Our methods allow us to find the smallest positive integers with no double-base representations of several lengths. In particular, we show that $103$ is the smallest positive integer with no double-base representation of length $2$, that $4985$ is the smallest positive integer with no double-base representation of length $3$, that $641687$ is the smallest positive integer with no double-base representation of length $4$, and that $326552783$ is the smallest positive integer with no double-base representation of length $5$.