(An official version and a preprint are available online.)
A double-base representation of an integer n is an expression n = n1 + … + nr, where the ni 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 alog 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 105 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.
We use several computer programs to obtain the results of this paper. The program SumOf5.c shows that every positive integer less than 326552783 has a double-base representation of length 5. The program Check5.c finds all representations of 326552783 modulo 4441033200890842920 as a sum of five integers of the form ±2a3b. The Magma program Check5.magma finishes the proof that 326552783 has no double-base representation of length 5. And the Magma code in DoubleBase.magma can be used to check various other results from the paper.