A173419 -id:A173419 - cp's OEIS frontend

A140361 Number of additions, subtractions, or multiplications necessary to reach n starting from 1 and 2.

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

Offset: 0

Leonid Broukhis, Jul 21 2008

nonn

Koiran calls this function tau(n). - Leonid Broukhis, Aug 04 2008

In the model used here a computation of length h of an integer n is a sequence of integers (n_{-1}=1, n_0=2, n_1, ..., n_h=n) such that for each i >= 1 there exist j,k < i and o in {+,-,*} with n_i = n_j o n_k. a(0)=a(1)=a(2)=0 and for n >= 3, a(n) is equal to the length of a shortest computation of n. - Alois P. Heinz, Sep 20 2012

			a(7) = 3 because we have 7 = (1+2)+(2*2), or 7 = 2*(2+2)-1 and there is no shorter way; the sequences are (1,2,3,4,7) or (1,2,4,8,7), respectively.

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

Cf. A173419.

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, 2}}:
S:= proc(n) S(n):= map(x->x[], F(n)) minus S(n-1) end: S(0):= {0, 1, 2}:
a:= proc(n) local k; for k from 0 while not(n in S(k)) do od; k end:
seq(a(n), n=0..100);  # Alois P. Heinz, Sep 24 2012

a(n) = A173419(n) - 1 for n > 1. Hence log_2(log_2(n)) <= a(n) <= 2*log_2(n) - 1. - Charles R Greathouse IV, Sep 20 2012

Corrected, from 6 to 5, a(59) = ((2+2)*2)*8-1-4 and a(94) = (((2+2)+2)+4)*10-6, by Leonid Broukhis, Aug 04 2008

a(24) and a(96) corrected by Charles R Greathouse IV, Sep 20 2012

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

A229662 The number of subsets of 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

2, 5, 20, 149, 1852, 34354, 873386, 28671789, 1166062774, 56973937168, 3266313635225, 215667757729237

Offset: 1

Gil Dogon, Sep 27 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 reduced if there is no repetition in the sequence. Two SLPs are considered equivalent if their sequence defines the same set of integers. This OEIS sequence gives the number of reduced SLPs with n steps.

			a(1) = 2 and the SLPs are (1,2) (1,0)
a(2) = 5 and the SLPs are (1,2,3) (1,2,4) (1,2,-1) (1,0,-1) (1,0,2)

Cf. A229673, A214872, A216999, A173419, A141414.

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

A229673 The number of subsets of nonzero 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, 3, 15, 126, 1667, 31966, 828678, 27535826, 1128945382, 55473589278, 3193471420236, 211517309562652

Offset: 1

Gil Dogon, Sep 27 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 reduced if there is no repetition in the sequence. Two SLPs are considered equivalent if their sequences define the same subset(only difference is sequence order).  This sequence gives the number of SLPs with n steps in which 0 does not appear.
This 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 such as A216999 or A229686. This is because 0 is never needed in the shortest SLP calculation of any other integer.
Michael Collier generated independently the values up to 1128945382.

			a(1) = 1 and the SLP is (1,2).
a(2) = 3 and the SLPs are (1,2,3), (1,2,4), and (1,2,-1).

Cf. A229662, A216999, A173419, A214872, A229686.

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

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

A140361 Number of additions, subtractions, or multiplications necessary to reach n starting from 1 and 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

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

A229662 The number of subsets of 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

Crossrefs

Formula

A229673 The number of subsets of nonzero 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

Crossrefs

Formula

A219906 Number of different straight line programs of length n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Extensions