login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A007302 Optimal cost function between two processors at distance n.
(Formerly M0103)
10
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.

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(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 A099910 A213325

Adjacent sequences:  A007299 A007300 A007301 * A007303 A007304 A007305

KEYWORD

nonn,easy,nice

AUTHOR

Simon Plouffe

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.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 22 12:39 EDT 2019. Contains 321421 sequences. (Running on oeis4.)