|
%I #28 Dec 06 2019 21:42:47
%S 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,
%T 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,
%U 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
%N Number of additions, subtractions, or multiplications necessary to reach n starting from 1 and 2.
%C Koiran calls this function tau(n). - _Leonid Broukhis_, Aug 04 2008
%C 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
%H P. Koiran, <a href="http://perso.ens-lyon.fr/pascal.koiran/Publis/tau.springer.pdf">Valiant's model and the cost of computing integers</a>, Comput. Complex. 13 (2004), pp. 131-146.
%H <a href="/index/Com#complexity">Index to sequences related to the complexity of n</a>
%F 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
%e 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 g:= f->seq(f union {t}, t={seq(seq({i+j, i-j, i*j}[], j=f), i=f)} minus f):
%p F:= proc(n) F(n):= map(g, F(n-1)) end: F(0):= {{1, 2}}:
%p S:= proc(n) S(n):= map(x->x[], F(n)) minus S(n-1) end: S(0):= {0, 1, 2}:
%p a:= proc(n) local k; for k from 0 while not(n in S(k)) do od; k end:
%p seq(a(n), n=0..100); # _Alois P. Heinz_, Sep 24 2012
%Y Cf. A173419.
%K nonn
%O 0,6
%A _Leonid Broukhis_, Jul 21 2008
%E 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
%E a(24) and a(96) corrected by _Charles R Greathouse IV_, Sep 20 2012
|
