|
%I #28 Sep 13 2015 09:43:45
%S 0,1,3,4,5,6,6,7,7,7,9,9,9,9,10,10,10,11,11,11,12,12,12
%N Minimum value of A173419(k*n!) over nonzero k.
%C This sequence relates to the difficulty of computing the factorial in an arithmetic model where adding, subtracting, and multiplying can be done with unit cost.
%C If this sequence 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 ultimately easy to compute, and consequently "the Hilbert Nullstellensatz is intractable, and consequently the algebraic version of 'NP != P' is true" (Shub & Smale). If A217032, the corresponding sequence with k = 1, is of polynomial growth it is instead called easy to compute and the same conclusion follows.
%C The sequence is nondecreasing by definition.
%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.
%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.
%H <a href="/index/Com#complexity">Index to sequences related to the complexity of n</a>
%F log n << a(n) < 2n log_2 n.
%F a(n) <= A217032(n).
%e These examples use the minimal value for k, see A217490.
%e a(1) = 0 since A173419(1!) = 0.
%e a(2) = 1 since A173419(2!) = 1.
%e a(3) = 3 since A173419(3!) = 3.
%e a(4) = 4 since A173419(4!) = 4.
%e a(5) = 5 since A173419(2*5!) = 5.
%e a(6) = 6 since A173419(6!) = 6.
%e a(7) = 6 since A173419(13*7!) = 6.
%e a(8) = 7 since A173419(26*8!) = 7.
%e a(9) = 7 since A173419(11830*9!) = 7.
%e a(10) = 7 since A173419(1183*10!) = 7.
%e a(11) = 9 since A173419(11!) = 9.
%e a(12) = 9 since A173419(561*12!) = 9.
%e The 9 steps computation:
%e 1, 2, 4, 8, 64, 65, 4160, 4158, 17297280, 299195895398400 = (3432 * 14!)
%e proves that a(13) = a(14) <= 9.
%e The 12 steps computation:
%e 1, 2, 4, 16, 18, 324, 323, 104652, 10952041104, 10952041100, 119947204299897374400, 14387331819361319182380790372013775360000, 206995316880406686700094970538841597542096346999032300472917857600543129600000000
%e proves that a(23) <= 12, since the last number is:
%e 23! * 8006931102170352452004696490160949546032818169320135140000
%Y Cf. A217032, A173419, A140361, A217490.
%K nonn,hard,more,nice
%O 1,3
%A _Charles R Greathouse IV_, Sep 24 2012
%E a(13)-a(16) from _Charles R Greathouse IV_, Oct 04 2012
%E a(13) and a(14) corrected by _Gil Dogon_, Apr 26 2013
%E Extended until a(23) doing full enumeration of all 12 step computations, from _Gil Dogon_, May 02 2013
| 