A007302 Optimal cost function between two processors at distance n.

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

Author

Simon Plouffe

Keywords

• nonn
• easy
• nice

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
• Jean-Paul Allouche and Jeffrey 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).
• Clemens Heuberger and Helmut Prodinger, On minimal expansions in redundant number systems: Algorithms and quantitative analysis, Computing 66(2001), 377-393.
• Sara Kropf and Stephan Wagner, q-Quasiadditive functions, arXiv:1605.03654 [math.CO], 2016. See section "The nonadjacent form and its Hamming weight".
• Gurmeet Singh Manku and Joe Sawada, A loopless Gray code for minimal signed-binary representations, 13th Annual European Symposium on Algorithms (ESA), LNCS 3669 (2005), 438-447.
• Nathan Mihm, Optimal Addition-Subtraction Chains, Bachelor Honors Thesis, Univ. Minnesota-Twin Cities (2025). See p. 4.
• Aline Parreau, Michel Rigo, Eric Rowland, and Elise 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.
• Joe 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

Crossrefs

Cf. A005578, A057526.

Subtracting 1 gives A280737.

Cf. A007583 (indices of record highs).

Programs

Haskell

import Data.Bits (xor)
a007302 n = a000120 $ xor n (3 * n) :: Integer
-- Reinhard Zumkeller, Jun 17 2012

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 *)

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

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