A217032 -id:A217032 - cp's OEIS frontend

A173419 Length of shortest computation yielding n using addition, subtraction and multiplication (starting from 1).

0, 1, 2, 2, 3, 3, 4, 3, 3, 4, 4, 4, 5, 4, 4, 3, 4, 4, 5, 4, 5, 5, 5, 4, 4, 5, 4, 5, 5, 5, 5, 4, 5, 5, 5, 4, 5, 5, 5, 5, 6, 5, 6, 6, 5, 6, 6, 5, 5, 5, 6, 6, 6, 5, 6, 5, 6, 6, 6, 5, 6, 5, 5, 4, 5, 5, 6, 5, 6, 6, 6, 5, 6, 6, 5, 6, 6, 5, 5, 5, 4, 5, 5, 5, 6, 6, 6, 6, 6, 5, 6, 6, 6, 6, 6, 5, 6, 6, 5, 5, 6, 6, 6, 6, 6, 6, 6, 5

Offset: 1

Charles R Greathouse IV, Feb 17 2010, Apr 22 2010

Let x_0 = 1 and x_m = n, with each x_k = x_i + x_j, x_k = x_i * x_j, or x_k = x_i - x_j for some 0 <= i,j < k. a(n) is the least such m.
Shub & Smale ask if there is a c such that a(n!) <= (log n)^c for all n.
If for any sequence of nonzero integers (m_i) there is no constant c such that a(n! * m_n) <= (log n)^c, then "the Hilbert Nullstellensatz is intractable, and consequently the algebraic version of 'NP != P' is true" (Shub & Smale).
Conjecture: if n is prime then a(n) >= a(n-1). The conjecture is true for n < 1800. - Dmitry Kamenetsky, Dec 26 2019

			For n = 9, one sequence is (1, 1 + 1 = 2, 1 + 2 = 3, 3 * 3 = 9). Since no shorter sequence is possible, a(9) = 3.
For n = 96, one sequence is (1, 1 + 1 = 2, 2 + 2 = 4, 2 + 4 = 6, 4*4 = 16, 6*16 = 96); no shorter is possible so a(96) = 5.

R. K. Guy, Unsolved Problems Number Theory, Sect. F26.

Alois P. Heinz, Table of n, a(n) for n = 1..1800
Peter Borwein and Joe Hobart, The extraordinary power of division in straight line programs, American Mathematical Monthly 119:7 (2012), pp. 584-592.
F. Cucker, M. Shub, and S. Smale, Separation of Complexity classes in Koiran's weak model, Theoretical Computer Science 133:1 (1994), pp. 3-14.
W. DeMelo and B. F. Svaiter, The cost of computing integers, Proc. Amer. Math. Soc. 124 (1996), pp. 1377-1378.
P. Koiran, Valiant's model and the cost of computing integers, Comput. Complex. 13 (2004), pp. 131-146.
Carlos Gustavo T. de A. Moreira, On asymptotic estimates for arithmetic cost functions, Proceedings of the American Mathematical Society 125:2 (1997), pp. 347-353.
Richard J. Mathar, Extended list of chain examples
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.
Al Zimmermann's Programming Contests, Factorials
Index to sequences related to the complexity of n

Records are essentially A141414.

Cf. A003313 (shortest chain using just addition), A005245 (number of 1s using just addition and multiplication), A217032(n):=A173419(n!).

g:= f->seq(f union {t}, t={seq(seq({i+j, i-j, i*j}[], j=f), i=f)} minus f):
F:= proc(n) F(n):= map(g, F(n-1)) end: F(0):= {{1}}:
S:= proc(n) S(n):= map(x->x[], F(n)) end:
a:= proc(n) local k; for k from 0 while not(n in S(k)) do od; k end:
seq(a(n), n=1..110);  # Alois P. Heinz, Sep 24 2012

a(n) <= 2 log_2(n).
a(n) >= log_2(log_2(n)) + 1.
a(n) >= log_2(n)/log_2(log_2(n)) for almost all n, as proved by Moreira (improving DeMelo & Svaiter).
a(n) <= A005245(n) <= A003313(n) <= A014701(n) <= 2*A000523(n). - Charles R Greathouse IV, Feb 07 2022

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

Original entry on oeis.org

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

A214872 The number of subsets of positive integers of cardinality n, produced as the steps in a computation starting with 1 and using the operations of multiplication, addition, or subtraction.

Original entry on oeis.org

1, 2, 8, 59, 663, 10609, 225219, 6057298, 199290037, 7805646133, 356263294786, 18626811747385

Offset: 1

Gil Dogon, May 03 2013

A straight-line program (SLP) is a sequence that starts at 1 and has each entry obtained from two preceding entries by addition, multiplication, or subtraction. The length of the SLP is defined as that of the sequence without the first 1. An SLP is said to be positive if all numbers in the sequence are positive, and reduced if there is no repetition in the sequence. Two SLPs are considered equivalent if their sequence consists of the same numbers (only difference is sequence order).  This OEIS sequence gives the number of reduced positive SLPs with n steps.
For most purposes only positive SLPs can be considered, as for every general SLP sequence, applying absolute value to all the steps will produce a positive SLP.
This OEIS sequence can also be thought of as defining the size of the search space that needs to be traversed when trying to compute other SLP related OEIS sequences as given in the cross references below.

			a(1) = 1 and the SLP is (1,2).
a(2) = 2 and the positive SLPs are (1,2,3) (1,2,4).
a(3) = 8 and the positive SLPs are (1,2,3,4) (1,2,3,5) (1,2,3,6) (1,2,3,9) (1,2,4,5) (1,2,4,6) (1,2,4,8) (1,2,4,16).
Notice that also (1,2,4,3) is a legal positive reduced length 3 SLP sequence but it is equivalent to (1,2,3,4) hence is not enumerated.

Al Zimmermann, Al Zimmermann's Programming Contests: Factorials

Cf. A217032, A216999, A217031, A173419, A141414.

a(n) >= a(n-1) * 2 * (n-1) and a(2)=2 Hence a(n) >= 2^(n-1)*(n-1)! .

The recurrence above is true since if the maximum of an SLP sequence of length n-1 is added to all elements except itself, and multiplied with all elements except the first 1 (including itself), then 2n-2 different extensions of the original SLP sequence are produced, resulting in 2n-2 reduced SLP's of length n.

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

A217490 Let t be the length of the shortest computation yielding a positive multiple of n! using addition, subtraction and multiplication. Then a(n) is the least k > 0 such that k*n! can be computed in t steps.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 13, 26, 11830, 1183, 1, 561, 48048, 3432, 3718, 3718, 956689100690500088178176, 187, 8983799529705, 6061484504517072231744, 26002249020, 1181920410, 8006931102170352452004696490160949546032818169320135140000

Offset: 1

Charles R Greathouse IV, Oct 04 2012

Least k > 0 such that A173419(k*n!) = A217031(n).
Related to the algebraic version of the P =? NP problem, see A173419 and A217031.
a(n) = 1 if and only if A217031(n) = A217032(n).

			a(1) = 1 since A173419(1!) = 0.
a(2) = 1 since A173419(2!) = 1.
a(3) = 1 since A173419(3!) = 3.
a(4) = 1 since A173419(4!) = 4.
a(5) = 2 since A173419(2*5!) = 5.
a(6) = 1 since A173419(6!) = 6.
a(7) = 13 since A173419(13*7!) = 6.
a(8) = 26 since A173419(26*8!) = 7.
a(9) = 11830 since A173419(11830*9!) = 7.
a(10) = 1183 since A173419(1183*10!) = 7.
a(11) = 1 since A173419(11!) = 9.
a(12) = 561 since A173419(561*12!) = 9.
a(22) = 1181920410
Because of the following 12 step computation:
1, 2, 4, 16, 256, 18, 324, 104976, 104720, 10993086720, 120847955633440358400, 10992982000, 1328479401015208457964748800000
The last number is 1181920410 * 22!

Trivial bound: 1 <= a(n) <= 2^(2^(A217031(n))/n! <= 2^(2^(2n-2))/n! . Can this be improved?

Extended until a(23) doing full enumeration of all 12 step computations, from Gil Dogon, May 02 2013

A219906 Number of different straight line programs of length n.

Original entry on oeis.org

1, 3, 13, 82, 788, 12141, 302791, 11729499

Offset: 0

N. J. A. Sloane, Dec 13 2012

See Borwein and Hobart (or A216999) for definition.

Peter Borwein and Joe Hobart, The extraordinary power of division in straight line programs, American Mathematical Monthly 119:7 (2012), pp. 584-592.

Cf. A173419, A216999, A217032.

g:= f-> seq([f[], t], t={seq(seq({i+j, i-j, i*j}[], j=f), i=f)}):
F:= proc(n) F(n):= map(g, F(n-1)) end: F(0):= {[1]}:
a:= n-> nops(F(n)):
seq(a(n), n=0..5);  # Alois P. Heinz, Dec 14 2012

Typo in a(4) corrected, a(6)-a(7) from Alois P. Heinz, Dec 14 2012

cp's OEIS Frontend

A173419 Length of shortest computation yielding n using addition, subtraction and multiplication (starting from 1).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Formula

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

Views

Author

Keywords

Examples

Links

Crossrefs

Extensions

A214872 The number of subsets of positive integers of cardinality n, produced as the steps in a computation starting with 1 and using the operations of multiplication, addition, or subtraction.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A217490 Let t be the length of the shortest computation yielding a positive multiple of n! using addition, subtraction and multiplication. Then a(n) is the least k > 0 such that k*n! can be computed in t steps.

Views

Author

Keywords

Comments

Examples

Formula

Extensions

A219906 Number of different straight line programs of length n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Extensions