|
|
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
|
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 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
|
|
|
KEYWORD
|
nonn,more,hard,nice
|
|
AUTHOR
|
|
|
EXTENSIONS
|
a(13)-a(19) from Ed Mertensotto, Mar 20 2013
|
|
STATUS
|
approved
|
|
|
|