A007302 Optimal cost function between two processors at distance n. (Formerly M0103)

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

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.

Index to sequences related to the complexity of n

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

A007302(n) = A000120(n) - sum (A213629(n,A136412(k))). - Reinhard Zumkeller, Jun 17 2012

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.

Cf. A007583 (indices of record highs).

Sequence in context: A164995 A294108 A055718 * A362028 A303401 A327491

Adjacent sequences: A007299 A007300 A007301 * A007303 A007304 A007305

Keyword

nonn,easy,nice

Author

Simon Plouffe

Status

approved