login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A217031
Minimum value of A173419(k*n!) over nonzero k.
3
0, 1, 3, 4, 5, 6, 6, 7, 7, 7, 9, 9, 9, 9, 10, 10, 10, 11, 11, 11, 12, 12, 12
OFFSET
1,3
COMMENTS
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.
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.
The sequence is nondecreasing by definition.
LINKS
FORMULA
log n << a(n) < 2n log_2 n.
a(n) <= A217032(n).
EXAMPLE
These examples use the minimal value for k, see A217490.
a(1) = 0 since A173419(1!) = 0.
a(2) = 1 since A173419(2!) = 1.
a(3) = 3 since A173419(3!) = 3.
a(4) = 4 since A173419(4!) = 4.
a(5) = 5 since A173419(2*5!) = 5.
a(6) = 6 since A173419(6!) = 6.
a(7) = 6 since A173419(13*7!) = 6.
a(8) = 7 since A173419(26*8!) = 7.
a(9) = 7 since A173419(11830*9!) = 7.
a(10) = 7 since A173419(1183*10!) = 7.
a(11) = 9 since A173419(11!) = 9.
a(12) = 9 since A173419(561*12!) = 9.
The 9 steps computation:
1, 2, 4, 8, 64, 65, 4160, 4158, 17297280, 299195895398400 = (3432 * 14!)
proves that a(13) = a(14) <= 9.
The 12 steps computation:
1, 2, 4, 16, 18, 324, 323, 104652, 10952041104, 10952041100, 119947204299897374400, 14387331819361319182380790372013775360000, 206995316880406686700094970538841597542096346999032300472917857600543129600000000
proves that a(23) <= 12, since the last number is:
23! * 8006931102170352452004696490160949546032818169320135140000
CROSSREFS
KEYWORD
nonn,hard,more,nice
AUTHOR
EXTENSIONS
a(13)-a(16) from Charles R Greathouse IV, Oct 04 2012
a(13) and a(14) corrected by Gil Dogon, Apr 26 2013
Extended until a(23) doing full enumeration of all 12 step computations, from Gil Dogon, May 02 2013
STATUS
approved