login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A140361 Number of additions, subtractions, or multiplications necessary to reach n starting from 1 and 2. 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 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,6

COMMENTS

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

LINKS

Table of n, a(n) for n=0..99.

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

FORMULA

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

EXAMPLE

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.

MAPLE

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

CROSSREFS

Cf. A173419.

Sequence in context: A136032 A135975 A334796 * A237769 A187182 A176208

Adjacent sequences:  A140358 A140359 A140360 * A140362 A140363 A140364

KEYWORD

nonn

AUTHOR

Leonid Broukhis, Jul 21 2008

EXTENSIONS

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

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 7 12:03 EDT 2022. Contains 357271 sequences. (Running on oeis4.)