The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A007302 Optimal cost function between two processors at distance n. (Formerly M0103) 12
 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; text; 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, Jun 30 2003 Volger (1985) proves that a(n) <= ceiling(log_2(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. - Ramasamy Chandramouli, Aug 20 2010 A007302(n) = A000120(n) - sum (A213629(n,A136412(k))). - Reinhard Zumkeller, Jun 17 2012 REFERENCES N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence). LINKS Reinhard Zumkeller, Table of n, a(n) for n = 0..10000 J.-P. Allouche and J. Shallit, The Ring of k-regular Sequences, II, Theoret. Computer Sci., 307 (2003), 3-29. Alma D'Aniello, Aldo de Luca, Alessandro De Luca, On Christoffel and standard words and their derivatives, arXiv:1602.03231 [cs.DM], 2016 (mentions this sequence). C. Heuberger and H. Prodinger, On minimal expansions in redundant number systems: Algorithms and quantitative analysis, Computing 66(2001), 377-393. S. Kropf, S. Wagner, q-Quasiadditive functions, arXiv:1605.03654 [math.CO], 2016. See section "The nonadjacent form and its Hamming weight". G. Manku and J. Sawada, A loopless Gray code for minimal signed-binary representations, 13th Annual European Symposium on Algorithms (ESA), LNCS 3669 (2005), 438-447. A. Parreau, M. Rigo, E. Rowland, E. Vandomme, A new approach to the 2-regularity of the l-abelian complexity of 2-automatic sequences, arXiv preprint arXiv:1405.3532 [cs.FL], 2014. J. Sawada, A simple Gray code to list all minimal signed binary representations, SIAM Journal on Discrete Mathematics, Vol. 21 No. 1 (2007), 16-25. 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. 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). 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 a(0) = 0; a(2n) = a(n); a(4n-1) = a(n) + 1; a(4n+1) = a(n) + 1. - Nathan Fox, Mar 12 2013 MATHEMATICA a[n_] := Count[ BitXor[ b1 = IntegerDigits[n, 2]; b3 = IntegerDigits[3*n, 2]; PadLeft[b1, Length[b3]], b3], 1]; Table[a[n], {n, 0, 100}] (* Jean-François Alcover, May 20 2014, after Ramasamy Chandramouli *) PROG (PARI) ep(r, n)=local(t=n/2^(r+2)); floor(t+5/6)-floor(t+4/6)-floor(t+2/6)+floor(t+1/6) a(n)=sum(r=0, log(3*n)\log(2)-1, !!ep(r, n)) for(n=1, 100, print1(a(n)", ")) /* corrected by Charles R Greathouse IV, Jun 16 2012 */ (PARI) a(n)=hammingweight(bitxor(n, 3*n)) \\ Charles R Greathouse IV, Jan 03 2017 (Haskell) import Data.Bits (xor) a007302 n = a000120 \$ xor n (3 * n) :: Integer -- Reinhard Zumkeller, Jun 17 2012 CROSSREFS Cf. A005578, A057526. Subtracting 1 gives A280737. Sequence in context: A164995 A294108 A055718 * A303401 A327491 A099910 Adjacent sequences:  A007299 A007300 A007301 * A007303 A007304 A007305 KEYWORD nonn,easy,nice AUTHOR STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified April 20 07:46 EDT 2021. Contains 343125 sequences. (Running on oeis4.)