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

 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 A362816 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.

Last modified November 30 11:40 EST 2023. Contains 367460 sequences. (Running on oeis4.)