|
%I M0103 #85 Aug 02 2023 14:36:06
%S 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,
%T 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,
%U 2,3,3,3,2,3,3,4,3,4,3,3,2,3,3,4,3
%N Optimal cost function between two processors at distance n.
%C 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
%C 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
%C Starting from 0, the smallest number of steps to reach n, where each step involves moving a power of 2 in either direction. - _Dmitry Kamenetsky_, Jul 04 2023
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Reinhard Zumkeller, <a href="/A007302/b007302.txt">Table of n, a(n) for n = 0..10000</a>
%H J.-P. Allouche and J. Shallit, <a href="http://www.math.jussieu.fr/~allouche/kreg2.ps">The Ring of k-regular Sequences, II</a>, Theoret. Computer Sci., 307 (2003), 3-29.
%H Alma D'Aniello, Aldo de Luca, and Alessandro De Luca, <a href="http://arxiv.org/abs/1602.03231">On Christoffel and standard words and their derivatives</a>, arXiv:1602.03231 [cs.DM], 2016 (mentions this sequence).
%H C. Heuberger and H. Prodinger, <a href="http://dx.doi.org/10.1007/s006070170021">On minimal expansions in redundant number systems: Algorithms and quantitative analysis</a>, Computing 66(2001), 377-393.
%H S. Kropf and S. Wagner, <a href="https://arxiv.org/abs/1605.03654">q-Quasiadditive functions</a>, arXiv:1605.03654 [math.CO], 2016. See section "The nonadjacent form and its Hamming weight".
%H G. Manku and J. Sawada, <a href="http://www.cis.uoguelph.ca/~sawada/papers/esa-loopless.pdf">A loopless Gray code for minimal signed-binary representations</a>, 13th Annual European Symposium on Algorithms (ESA), LNCS 3669 (2005), 438-447.
%H A. Parreau, M. Rigo, E. Rowland, and E. Vandomme, <a href="http://arxiv.org/abs/1405.3532">A new approach to the 2-regularity of the l-abelian complexity of 2-automatic sequences</a>, arXiv preprint arXiv:1405.3532 [cs.FL], 2014.
%H Yaniv Sadeh, Ori Rottenstreich, and Haim Kaplan, <a href="https://arxiv.org/abs/2212.13256">Codes for Load Balancing in TCAMs: Size Analysis</a>, arXiv:2212.13256 [cs.NI], 2022.
%H J. Sawada, <a href="http://dx.doi.org/10.1137/050641405">A simple Gray code to list all minimal signed binary representations</a>, SIAM Journal on Discrete Mathematics, Vol. 21 No. 1 (2007), 16-25.
%H Hugo Volger, <a href="http://dx.doi.org/10.1016/0020-0190(85)90085-7">Some results on addition/subtraction chains</a>, Information Processing Letters, vol. 20, p. 155-160 (1985).
%H A. Weitzman, <a href="ftp://ftp.inria.fr/INRIA/Projects/algo/web/seminars/sem92-93/weitzman.ps">Transformation of parallel programs guided by micro-analysis</a>, pp. 155-159 of Algorithms Seminars 1992-1993, ed. B. Salvy, Report #2130, INRIA, Rocquencourt, Dec. 1993.
%H <a href="/index/Com#complexity">Index to sequences related to the complexity of n</a>
%F 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 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
%F a(n) = hammingweight( XOR(n, 3*n) ). - _Ramasamy Chandramouli_, Aug 20 2010
%F A007302(n) = A000120(n) - sum (A213629(n,A136412(k))). - _Reinhard Zumkeller_, Jun 17 2012
%F a(0) = 0; a(2n) = a(n); a(4n-1) = a(n) + 1; a(4n+1) = a(n) + 1. - _Nathan Fox_, Mar 12 2013
%t 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_ *)
%o (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)
%o a(n)=sum(r=0,log(3*n)\log(2)-1,!!ep(r,n))
%o for(n=1,100,print1(a(n)", "))
%o /* corrected by _Charles R Greathouse IV_, Jun 16 2012 */
%o (PARI) a(n)=hammingweight(bitxor(n,3*n)) \\ _Charles R Greathouse IV_, Jan 03 2017
%o (Haskell)
%o import Data.Bits (xor)
%o a007302 n = a000120 $ xor n (3 * n) :: Integer
%o -- _Reinhard Zumkeller_, Jun 17 2012
%Y Cf. A005578, A057526.
%Y Subtracting 1 gives A280737.
%Y Cf. A007583 (indices of record highs).
%K nonn,easy,nice
%O 0,4
%A _Simon Plouffe_
|
