0,4

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

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

J.-P. Allouche and J. Shallit, The ring of k-regular sequences, II, Theoret. Computer Sci., 307 (2003), 3-29.

C. Heuberger and H. Prodinger, On minimal expansions in redundant number systems: Algorithms and quantitative analysis, Computing 66(2001), 377-393.

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.

Hugo Volger, "Some results on addition/subtraction chains," Information Processing Letters, vol. 20, p. 155-160 (1985).

J.-P. Allouche and J. Shallit, The Ring of k-regular Sequences, II

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

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

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", ")))

Cf. A005578, A057526.

Sequence in context: A002321 A043530 A055718 this_sequence A099910 A043555 A118821

Adjacent sequences: A007299 A007300 A007301 this_sequence A007303 A007304 A007305

nonn,easy,nice

Simon Plouffe (plouffe(AT)math.uqam.ca)