%I A007302 M0103
%S A007302 0,1,1,2,1,2,2,2,1,2,2,3,2,3,2,2,1,2,2,3,2,3,3,3,2,3,3,3,2,
%T A007302 3,2,2,1,2,2,3,2,3,3,3,2,3,3,4,3,4,3,3,2,3,3,4,3,4,3,3,2,
%U A007302 3,3,3,2,3,2,2,1,2,2,3,2,3,3,3,2,3,3,4,3,4,3,3,2,3,3,4,3
%N A007302 Optimal cost function between two processors at distance n.
%C A007302 Also the number of nonzero digits in the symmetric signed digit expansion 
               of n with q=2 (i.e. the representation of n in the (-1,0,1)_2 number 
               system). - Ralf Stephan (ralf(AT)ark.in-berlin.de), Jun 30 2003
%C A007302 Volger (1985) proves that a(n) <= ceil(log2(3n/2) / 2) and uses a(n) 
               to derive an upper bound on the length of the minimum addition-subtraction 
               chain for n. - Steven G. Johnson (stevenj(AT)math.mit.edu), May 01 
               2007
%D A007302 J.-P. Allouche and J. Shallit, The ring of k-regular sequences, II, Theoret. 
               Computer Sci., 307 (2003), 3-29.
%D A007302 C. Heuberger and H. Prodinger, On minimal expansions in redundant number 
               systems: Algorithms and quantitative analysis, Computing 66(2001), 
               377-393.
%D A007302 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, 
               Academic Press, 1995 (includes this sequence).
%D A007302 Hugo Volger, "Some results on addition/subtraction chains," Information 
               Processing Letters, vol. 20, p. 155-160 (1985).
%D A007302 A. Weitzman, Transformation of parallel programs guided by micro-analysis, 
               pp. 155-159 of Algorithms Seminars 1992-1993, ed. B. Salvy, Report 
               #2130, INRIA, Rocquencourt, Dec. 1993.
%H A007302 J.-P. Allouche and J. Shallit, <a href="http://www.lri.fr/~allouche/kreg2.ps">
               The Ring of k-regular Sequences, II</a>
%F A007302 a(0) = 0; a(n) = 1 if n is a power of 2; a(n) = 1 + min { a(n-2^k), a(2^(k+1)-n) 
               } if 2^k < n < 2^(k+1).
%F A007302 Apparently, a(n) = 0 if n = 0, = 1 if n = 1, = a(n/2) if n > 1 and n 
               even and = min(a(n-1), a(n+1))+1 if n > 1 and n odd. - David W. Wilson, 
               Dec 28 2005
%o A007302 ep(r,n)=local(t); t=n/2^(r+2):floor(t+5/6)-floor(t+4/6)-floor(t+2/6)+floor(t+1/
               6):for(n=1,100,p=0:for(r=0,floor(log2(3*n))-1,if(ep(r,n),p=p+1)): 
               if(1,print1(p",")))
%Y A007302 Cf. A005578, A057526.
%Y A007302 Sequence in context: A043530 A164995 A055718 this_sequence A099910 A043555 
               A118821
%Y A007302 Adjacent sequences: A007299 A007300 A007301 this_sequence A007303 A007304 
               A007305
%K A007302 nonn,easy,nice
%O A007302 0,4
%A A007302 Simon Plouffe (simon.plouffe(AT)gmail.com)