

A217032


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


7



0, 1, 3, 4, 6, 6, 7, 8, 8, 9, 9, 10, 11, 11, 12, 12, 12, 13, 13
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,3


COMMENTS

A straightline 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 10step 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

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


FORMULA



EXAMPLE

The entry for 9! is 8 because of the straightline 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 straightline program {1, 2, 3, 5, 7, 12, 144, 6!, 7!, 10!}, which does not use subtraction.


CROSSREFS



KEYWORD

nonn,more,hard,nice


AUTHOR



EXTENSIONS

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


STATUS

approved



