The OEIS is supported by the many generous donors to the OEIS Foundation.

 Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 60th year, we have over 367,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”). Other ways to Give
 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified December 9 06:02 EST 2023. Contains 367685 sequences. (Running on oeis4.)