|
%I #55 Sep 06 2023 16:14:01
%S 0,1,3,4,6,6,7,8,8,9,9,10,11,11,12,12,12,13,13
%N Minimum number of steps to reach n! starting from 1 and using the operations of multiplication, addition, or subtraction.
%C 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
%C 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
%C 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
%H Peter Borwein and Joe Hobart, <a href="http://www.jstor.org/stable/10.4169/amer.math.monthly.119.07.584">The extraordinary power of division in straight line programs</a>, American Mathematical Monthly 119:7 (2012), pp. 584-592.
%H P. Koiran, <a href="http://perso.ens-lyon.fr/pascal.koiran/Publis/tau.springer.pdf">Valiant's model and the cost of computing integers</a>, Comput. Complex. 13 (2004), pp. 131-146. <a href="http://dx.doi.org/10.1007/s00037-004-0186-2">[DOI]</a>
%H Ed Mertensotto, <a href="http://groups.yahoo.com/group/AlZimmermannsProgrammingContests/message/5479">post about enumerating all sequences of 12 steps</a> [broken link]
%H Ed Mertensotto, Tomas G. Rokicki, Gil Dogon, <a href="/A217032/a217032.txt">Search</a>, digest of 25 messages in AlZimmermannsProgrammingContests Yahoo group, Mar 19 - Apr 23, 2013.
%H Michael Shub and Steve Smale, <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.100.5035">On the intractability of Hilbert's Nullstellensatz and an algebraic version of "NP = P"</a>, Duke Mathematical Journal 81:1 (1995), pp. 47-54. <a href="http://dx.doi.org/10.1090/S0273-0979-1989-15750-9">[DOI]</a>
%H Stan Wagon, <a href="http://mathforum.org/wagon/fall12/p1153.html">Macalester Problem of the Week 1153</a>
%H Al Zimmermann, <a href="http://www.azspcs.com/Contest/Factorials">Al Zimmermann's Programming Contests: Factorials</a>
%H <a href="/index/Com#complexity">Index to sequences related to the complexity of n</a>
%F a(n) = A173419(n!) >= A217031(n). - _Charles R Greathouse IV_, Sep 24 2012
%e 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.
%Y Cf. A216999, A217031, A173419, A003065, A141414.
%K nonn,more,hard,nice
%O 1,3
%A _Stan Wagon_, Sep 24 2012
%E a(12) from _Charles R Greathouse IV_, Oct 04 2012
%E a(13)-a(19) from Ed Mertensotto, Mar 20 2013
|
