The straight line complexity of small factorials and primorials

Abstract

In this paper we determine the straight-line complexity of $n!$ for $n\le 22$ and give bounds for the complexities up to $n=46$. In the same way we determine the straight-line complexity of the product of the first primes up to $p=31$ and gives bounds for $p\le 43$. Our results are based on an exhaustive computer search of the short length straight-line programs.

arXiv commentV4: Published version. Reformatted to journal format. Minor typos corrected. v3: Updated acknowledgments, improved some of the lower bounds after recomputing all data with a new program, corrected two incorrect lower bounds due a damaged datafile from the original 10 year old computation. V2: Corrected typos and a mistake in table 2