A140361 -id:A140361 - cp's OEIS frontend

A141414 Least k for which A140361(n) = k.

1, 3, 5, 7, 13, 41, 113, 311, 1821, 10267, 74587, 1015453, 12550793

Offset: 0

Leonid Broukhis, Aug 04 2008

			a(1) = 3: 3 can be written as 2+1, requiring 1 operation
a(2) = 5: 5 = (2+1)+2, the lowest number requiring 2 operations
a(3) = 7: ((2+2)+1)+2, the lowest number requiring 3 operations
a(4) = 13: (2+1)*3+2+2 (Note: 3 = 2+1 reused)
a(5) = 41: (2+1)*2*6+3+2 (3 = 2+1 reused, 6 = 3*2 reused)
a(6) = 113: ((2+1)*3+3+1)*9-4
a(7) = 311: ((2+1)*3*3+1)*(9+2)+3
a(8) = 1821: (2+(2+1))*(3+(2+2)*4)*19+16
a(9) = 10267: (1+(2+(2+1))*(3*3))*(5*45-2)+9
a(10) = 74587: (2+1)*(((2*(3*3)*9-2)-3)*157+160)+160

Index to sequences related to the complexity of n

Cf. A217032.

Comment removed and three new entries added by Jeffrey Wang (jeffreyw(AT)stanford.edu), Oct 10 2009

a(11)-a(12) from Gil Dogon, Apr 25 2013

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

Original entry on oeis.org

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

Charles R Greathouse IV, Sep 24 2012

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.

			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

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

Cf. A217032, A173419, A140361, A217490.

log n << a(n) < 2n log_2 n.

a(n) <= A217032(n).

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

cp's OEIS Frontend

A141414 Least k for which A140361(n) = k.

Views

Author

Keywords

Examples

Links

Crossrefs

Extensions