login
This site is supported by donations to The OEIS Foundation.

 

Logo

"Email this user" was broken Aug 14 to 9am Aug 16. If you sent someone a message in this period, please send it again.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 (list; graph; refs; listen; history; text; internal format)
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

Table of n, a(n) for n=1..23.

P. Koiran, Valiant's model and the cost of computing integers, Comput. Complex. 13 (2004), pp. 131-146.

Michael Shub and Steve Smale, On the intractability of Hilbert's Nullstellensatz and an algebraic version of "NP = P", Duke Mathematical Journal 81:1 (1995), pp. 47-54.

Index to sequences related to the complexity of n

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

Cf. A217032, A173419, A140361, A217490.

Sequence in context: A162552 A133575 A230113 * A104136 A198466 A212642

Adjacent sequences:  A217028 A217029 A217030 * A217032 A217033 A217034

KEYWORD

nonn,hard,more,nice

AUTHOR

Charles R Greathouse IV, Sep 24 2012

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified August 17 23:58 EDT 2017. Contains 290682 sequences.