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

Author

Leonid Broukhis, Jul 21 2008

Keywords

• nonn

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

Examples

			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.
		

Links

• 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

Crossrefs

Cf. A173419.

Programs

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

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

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