cp's OEIS Frontend

A217031 Minimum value of A173419(k*n!) over nonzero k.

%I A217031 #30 Aug 06 2024 07:21:13
%S A217031 0,1,3,4,5,6,6,7,7,7,9,9,9,9,10,10,10,11,11,11,12,12,12
%N A217031 Minimum value of A173419(k*n!) over nonzero k.
%C A217031 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 A217031 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 A217031 The sequence is nondecreasing by definition.
%H A217031 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 A217031 Michael Shub and Steve Smale, <a href="https://citeseerx.ist.psu.edu/pdf/a16554b6837219fab950b3628e6d5bc485565311">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 A217031 <a href="/index/Com#complexity">Index to sequences related to the complexity of n</a>
%F A217031 log n << a(n) < 2n log_2 n.
%F A217031 a(n) <= A217032(n).
%e A217031 These examples use the minimal value for k, see A217490.
%e A217031 a(1) = 0 since A173419(1!) = 0.
%e A217031 a(2) = 1 since A173419(2!) = 1.
%e A217031 a(3) = 3 since A173419(3!) = 3.
%e A217031 a(4) = 4 since A173419(4!) = 4.
%e A217031 a(5) = 5 since A173419(2*5!) = 5.
%e A217031 a(6) = 6 since A173419(6!) = 6.
%e A217031 a(7) = 6 since A173419(13*7!) = 6.
%e A217031 a(8) = 7 since A173419(26*8!) = 7.
%e A217031 a(9) = 7 since A173419(11830*9!) = 7.
%e A217031 a(10) = 7 since A173419(1183*10!) = 7.
%e A217031 a(11) = 9 since A173419(11!) = 9.
%e A217031 a(12) = 9 since A173419(561*12!) = 9.
%e A217031 The 9 steps computation:
%e A217031 1, 2, 4, 8, 64, 65, 4160, 4158, 17297280, 299195895398400 = (3432 * 14!)
%e A217031 proves that a(13) = a(14) <= 9.
%e A217031 The 12 steps computation:
%e A217031 1, 2, 4, 16, 18, 324, 323, 104652, 10952041104, 10952041100, 119947204299897374400, 14387331819361319182380790372013775360000, 206995316880406686700094970538841597542096346999032300472917857600543129600000000
%e A217031 proves that a(23) <= 12, since the last number is:
%e A217031 23! * 8006931102170352452004696490160949546032818169320135140000
%Y A217031 Cf. A217032, A173419, A140361, A217490.
%K A217031 nonn,hard,more,nice
%O A217031 1,3
%A A217031 _Charles R Greathouse IV_, Sep 24 2012
%E A217031 a(13)-a(16) from _Charles R Greathouse IV_, Oct 04 2012
%E A217031 a(13) and a(14) corrected by _Gil Dogon_, Apr 26 2013
%E A217031 Extended until a(23) doing full enumeration of all 12 step computations, from _Gil Dogon_, May 02 2013