A217032 Minimum number of steps to reach n! starting from 1 and using the operations of multiplication, addition, or subtraction.

0, 1, 3, 4, 6, 6, 7, 8, 8, 9, 9, 10, 11, 11, 12, 12, 12, 13, 13

Offset

1,3

Comments

A straight-line program is a sequence that starts at 1 and has each entry obtained from two preceding entries by addition, multiplication, or subtraction. This sequence lists the smallest number of steps needed to reach n!. A 10-step solution for 12 is {1, 2, 4, 6, 24, 30, 720, 900, 924, 518400, 12!}, found by Stan Wagon; John Guilford found all such, and proved that 10 is minimal for 12! - edited by Stan Wagon, Nov 07 2012

This sequence describes the difficulty of computing the factorial in Valiant's model. If it is of polynomial growth -- that is, there exists some c such that a(n) < (log n)^c for all n -- then the factorial is said to be easy to compute, and consequently "the Hilbert Nullstellensatz is intractable, and consequently the algebraic version of 'NP != P' is true" (Shub & Smale). - Charles R Greathouse IV, Sep 24 2012

During Al Zimmermann's contest (see link), Ed Mertensotto generated all sequences of 12 steps and found no better solutions. Hence a(13)-a(17) are optimal. Solutions of 13 steps were found for a(18) and a(19) during the contest. Hence, they are optimal too. - Dmitry Kamenetsky, Apr 22 2013

Links

Table of n, a(n) for n=1..19.

Peter Borwein and Joe Hobart, The extraordinary power of division in straight line programs, American Mathematical Monthly 119:7 (2012), pp. 584-592.

P. Koiran, Valiant's model and the cost of computing integers, Comput. Complex. 13 (2004), pp. 131-146. [DOI]

Ed Mertensotto, post about enumerating all sequences of 12 steps [broken link]

Ed Mertensotto, Tomas G. Rokicki, Gil Dogon, Search, digest of 25 messages in AlZimmermannsProgrammingContests Yahoo group, Mar 19 - Apr 23, 2013.

Michael Shub and Steve Smale, On the intractability of Hilbert's Nullstellensatz and an algebraic version of "NP = P", Duke Mathematical Journal 81:1 (1995), pp. 47-54. [DOI]

Stan Wagon, Macalester Problem of the Week 1153

Al Zimmermann, Al Zimmermann's Programming Contests: Factorials

Index to sequences related to the complexity of n

Formula

a(n) = A173419(n!) >= A217031(n). - Charles R Greathouse IV, Sep 24 2012

Example

The entry for 9! is 8 because of the straight-line program {1, 2, 3, 9, 8, 72, 70, 7!, 9!}; subtraction is essential to getting 9! in 8 steps. The entry for 10! is 9 because of the straight-line program {1, 2, 3, 5, 7, 12, 144, 6!, 7!, 10!}, which does not use subtraction.

Crossrefs

Cf. A216999, A217031, A173419, A003065, A141414.

Sequence in context: A033957 A031131 A105321 * A300305 A160095 A135319

Adjacent sequences: A217029 A217030 A217031 * A217033 A217034 A217035

Keyword

nonn,more,hard,nice

Author

Stan Wagon, Sep 24 2012

Extensions

a(12) from Charles R Greathouse IV, Oct 04 2012

a(13)-a(19) from Ed Mertensotto, Mar 20 2013

Status

approved