|
| |
|
|
A007302
|
|
Optimal cost function between two processors at distance n.
(Formerly M0103)
|
|
3
| |
|
|
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, 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, 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
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 0,4
|
|
|
COMMENTS
| 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
a(n) is also the number of ones in the binary representation of the number given by the function XOR(n, 3n) where n is expressed in base 2. [From Ramasamy Chandramouli (thedavinci(AT)gmail.com), Aug 20 2010]
|
|
|
REFERENCES
| 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.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
Hugo Volger, "Some results on addition/subtraction chains," Information Processing Letters, vol. 20, p. 155-160 (1985).
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.
|
|
|
LINKS
| J.-P. Allouche and J. Shallit, The Ring of k-regular Sequences, II
|
|
|
FORMULA
| 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
|
|
|
PROG
| 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", ")))
|
|
|
CROSSREFS
| Cf. A005578, A057526.
Sequence in context: A043530 A164995 A055718 * A099910 A043555 A118821
Adjacent sequences: A007299 A007300 A007301 * A007303 A007304 A007305
|
|
|
KEYWORD
| nonn,easy,nice
|
|
|
AUTHOR
| Simon Plouffe (simon.plouffe(AT)gmail.com)
|
| |
|
|
