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
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
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, and 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 and 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, and 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.
Yaniv Sadeh, Ori Rottenstreich, and Haim Kaplan, Codes for Load Balancing in TCAMs: Size Analysis, arXiv:2212.13256 [cs.NI], 2022.
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(n) = hammingweight( XOR(n, 3*n) ). - Ramasamy Chandramouli, Aug 20 2010
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
KEYWORD
nonn,easy,nice
AUTHOR
STATUS
approved