Problem of the Week 1153Computing FactorialsA straight line program (SLP) is a sequence of integers (positive or negative) starting with 1 such that each one comes from two (not necessarily distinct) previous entries by either adding, subtracting (in either order), or multiplying. If an SLP ending in x has K+1 entries then it is called a K-step program for x. For example, a 4-step SLP for 4! is (1, 2, 4, 6, 24) and a 6-step program for 5! is (1, 2, 3, 4, 12, 10, 120).
A famous conjecture of S. Smale concerns the shortest SLP that ends with n!. An 8-step SLP for 6! = 720 can be obtained from the definition of factorial: Want more of a challenge? Work on larger factorials. I know the shortest programs for 6!, 7!, 8!, 9!, 10!, 11!, and 12!. Bigger challenge: Find a 17-step program for 20!. I have one, but have no idea whether 17 is minimal. Also, I can say that the number of numbers obtainable in k steps is {1,3,6,13,38,153,867,6930,75986}. Is it possible to get one more entry in this sequence? Not sure. There are 75986 numbers obtainable in 8 steps. The Smale conjecture is that it is not possible to compute n! by an SLP in (log n)^c steps for some constant c independent of n. The problem is related to #4 on Smale's list of 18 problems for the 21st century. Source: P. Borwein & J. Hobart, The extraordinary power of division in straight line programs, American Mathematical Monthly, 119 (Sept. 2012 ) 584-592. For more information on this problem, see the results of Al Zimmerman's contest or the update on OEIS. The true optimum for n! is now known up to 19!. © Copyright 2012 Stan Wagon. Reproduced with permission.
|