0,3

Inverse of sequence A006068 considered as a permutation of the nonnegative integers, i.e. A006068(A003188(n)) = n = A003188(A006068(n)). - Howard A. Landman (howard(AT)polyamory.org), Sep 25 2001

M. W. Bunder et al., On binary reflected Gray codes and functions, Discr. Math., 308 (2008), 1690-1700.

M. Gardner, Mathematical Games, Sci. Amer. Vol. 227 (No. 2, Feb. 1972), p. 107.

M. Gardner, Knotted Doughnuts and Other Mathematical Entertainments. Freeman, NY, 1986, p. 15.

J. A. Oteo and J. Ros, A Fractal Set from the Binary Reflected Gray Code, J. Phys. A: Math Gen. 38 (2005) 8935-8949.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

N. J. A. Sloane, Table of n, a(n) for n = 0..1000

Joerg Arndt, Fxtbook

R. Stephan, Some divide-and-conquer sequences ...

R. Stephan, Table of generating functions

Index entries for sequences that are permutations of the natural numbers

a(n) = 2*a([n/2])+A021913(n-1) - Henry Bottomley (se16(AT)btinternet.com), Apr 05 2001

a(n) = n XOR floor(n/2), where XOR is the binary exclusive OR operator. - Paul D. Hanna (pauldhanna(AT)juno.com), Jun 04 2002

G.f.: 1/(1-x) * sum(k>=0, 2^k*x^2^k/(1+x^2^(k+1))). - Ralf Stephan, May 06 2003

a(0)=0, a(2n) = 2a(n) + [n odd], a(2n+1) = 2a(n) + [n even]. - Ralf Stephan (ralf(AT)ark.in-berlin.de), Oct 20 2003

a(n) = sum(k=1, n, 2^A007814(k) * (-1)^((k/2^A007814(k)-1)/2)). - Ralf Stephan (ralf(AT)ark.in-berlin.de), Oct 29 2003

a(0) = 0, a(n+1) = a(n) XOR 2^A007814(n) - Jaume Simon Gispert (jaume(AT)nuem.com), Sep 11 2004

Inverse of sequence A006068. - Philippe DELEHAM, Apr 29 2005

with(combinat); graycode(6); # to produce first 64 terms

printf(cat(` %.6d`$64), op(map(convert, graycode(6), binary))); lprint(); # to produce binary strings

(PARI) a(n)=sum(k=1, n, (-1)^((k/2^valuation(k, 2)-1)/2)*2^valuation(k, 2))

a(2*A003714(n)) = 3*A003714(n) for all n. - Antti Karttunen, Apr 26 1999

Same sequence in binary: A014550, bisection: A048724. Cf. A038554, A048641, A048642.

Sequence in context: A083362 A153142 A154447 this_sequence A154435 A006042 A100280

Adjacent sequences: A003185 A003186 A003187 this_sequence A003189 A003190 A003191

nonn,nice,easy

N. J. A. Sloane (njas(AT)research.att.com).

More terms from Larry Reeves (Larryr(AT)acm.org), Sep 05 2000

0,3

Starting with a(1)=0 mirror all initial 2^k segments and increase by one.

a(n) gives the net rotation (measured in right angles) after taking n steps along a dragon curve. - Christopher Hendrie (hendrie(AT)acm.org), Sep 11 2002

This sequence generates A082410: (0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1...) and A014577; identical to the latter except starting 1, 1, 0...; by writing a "1" if a(n+1) > a(n); if not, write "0". E.g. A014577(2) = 0, since a(3) < a(2), or 1 < 2. - Gary W. Adamson (qntmpkt(AT)yahoo.com), Sep 20 2003

Starting with 1 = partial sums of A034947: (1, 1, -1, 1, 1, -1, -1, 1, 1, 1,...). - Gary W. Adamson (qntmpkt(AT)yahoo.com), Jul 23 2008

The composer Per Norgard's name is also written in the OEIS as Per Noergaard.

J.-P. Allouche and J. Shallit, The ring of k-regular sequences, II, Theoret. Computer Sci., 307 (2003), 3-29.

Flajolet and Ramshaw, A note on Gray code..., SIAM J. Comput. 9 (1980), 142-158.

Jeffrey Shallit, The mathematics of Per Noergaard's rhythmic infinity system, Fib. Q., 43 (2005), 262-268.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 0..10000

Joerg Arndt, Fxtbook

J.-P. Allouche, J. Shallit, The Ring of k-regular Sequences, II

P. Flajolet et al., Mellin Transforms And Asymptotics: Digital Sums, Theoret. Computer Sci. 23 (1994), 291-314.

R. Stephan, Some divide-and-conquer sequences ...

R. Stephan, Table of generating functions

Index entries for "core" sequences

a(2^k + i) = a(2^k - i + 1) + 1 for k >= 0 and 0 < i <= 2^k. - Reinhard Zumkeller (reinhard.zumkeller(AT)gmail.com), Aug 14 2001

a(2n+1) = 2a(n)-a(2n)+1, a(4n) = a(2n), a(4n+2) = 1+a(2n+1).

a(j+1) = a(j) + (-1)^A014707[j] - Christopher Hendrie (hendrie(AT)acm.org), Sep 11 2002

G.f.: 1/(1-x) * sum(k>=0, x^2^k/(1+x^2^(k+1))). - Ralf Stephan, May 2 2003

Delete the 0, make subsets of 2^n terms; and reverse the terms in each subset to generate A088696. - Gary W. Adamson (qntmpkt(AT)yahoo.com), Oct 19 2003

a(0)=0, a(2n) = a(n) + [n odd], a(2n+1) = a(n) + [n even]. - Ralf Stephan (ralf(AT)ark.in-berlin.de), Oct 20 2003

a(n) = sum(k=1, n, (-1)^((k/2^A007814(k)-1)/2)) = sum(k=1, n, (-1)^A025480(k-1)). - Ralf Stephan (ralf(AT)ark.in-berlin.de), Oct 29 2003

A005811 := proc(n) local i, b, ans; ans := 1; b := convert(n, base, 2); for i from 2 to nops(b) do if b[ i-1 ]<>b[ i ] then ans := ans+1 fi od; RETURN(ans); end; [ seq(A005811(i), i=1..50) ];

Table[ Length[ Length/@Split[ IntegerDigits[ n, 2 ] ] ], {n, 1, 255} ]

(PARI) a(n)=sum(k=1, n, (-1)^((k/2^valuation(k, 2)-1)/2))

Cf. A056539, A014707, A014577, A082410.

A000975 gives records. - Oliver Kosut (vern(AT)mit.edu), May 06 2002

a(n) = A037834(n)+1.

a(n) = A069010(n) + A033264(n) (from Ralf Stephan)

Cf. A034947.

Sequence in context: A088696 A004738 A043554 this_sequence A008342 A002850 A111944

Adjacent sequences: A005808 A005809 A005810 this_sequence A005812 A005813 A005814

easy,nonn,core,nice

N. J. A. Sloane (njas(AT)research.att.com), Jeffrey Shallit, Simon Plouffe

Additional description from Wouter Meeussen (wouter.meeussen(AT)pandora.be)

1,1

More precisely, this is the number of ways of making a list of the 2^n nodes of the n-cube, with a distinguished starting position and a direction, such that each node is adjacent to the previous one and the last node is adjacent to the first.

M. Gardner, Knotted Doughnuts and Other Mathematical Entertainments. Freeman, NY, 1986, p. 24.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.

a(n)=A003042(n)*2^n. - Max Alekseyev, Jun 15 2006

a(1) = 2: we have 1,2 or 2,1.

a(2) = 8: label the nodes 1, 2, ..., 4. Then the 8 possibilities are 1,2,3,4; 1,4,3,2; 2,3,4,1; 2,1,4,3; etc.

Cf. A003042, A006070, A091299.

Sequence in context: A001417 A156926 A001697 this_sequence A052457 A119654 A008926

Adjacent sequences: A006066 A006067 A006068 this_sequence A006070 A006071 A006072

nonn,more

N. J. A. Sloane (njas(AT)research.att.com).

a(5) corrected by Jonathan Cross (jcross(AT)wcox.com), Oct 10 2001

Definition corrected by Max Alekseyev, Jun 15 2006

1,3

This is the number of ways of making a list of the 2^n nodes of the n-cube, with a distinguished starting position and a direction, such that each node is adjacent to the previous one and the last node is adjacent to the first; and then dividing the total by 2^(n+1) because the starting node and the direction do not really matter.

The number is a multiple of n!/2 since any directed cycle starting from 0^n induces a permutation on the n bits, namely the order in which they first get set to 1.

R. J. Douglas, Bounds on the number of Hamiltonian circuits in the n-cube, Discrete Mathematics, 17 (1977), 143-146.

Harary, Hayes and Wu, A survey of the theory of hypercube graphs, Computers and Mathematics with Applications, 15(4), 1988, 7-289.

The 2-cube has a single cycle consisting of all 4 edges.

Equals A006069/2^(n+1) and A003042/2.

Cf. A006070, A091299, A003043, A091302.

Sequence in context: A013738 A076781 A055306 this_sequence A107252 A131453 A160226

Adjacent sequences: A066034 A066035 A066036 this_sequence A066038 A066039 A066040

nonn,nice

John Tromp (tromp(AT)cwi.nl), Dec 12 2001

0,3

The top left 8x8 corner of the array is

+0 +1 +5 +4 20 21 17 16

+2 +3 +7 +6 22 23 19 18

10 11 15 14 30 31 27 26

+8 +9 13 12 28 29 25 24

40 41 45 44 60 61 57 56

42 43 47 46 62 63 59 58

34 35 39 38 54 55 51 50

32 33 37 36 52 53 49 48

By taking the top left 2x2 corner, 2x4 rectangle ((0,1,5,4),(2,3,7,6)) or 4x4 corner one obtains Karnaugh map templates for 2, 3 or 4 variables respectively (although not the standard ones usually given in the textbooks).

A. Karttunen, Table of n, a(n) for n = 0..2079

Wikipedia, Karnaugh map

Index entries for sequences that are permutations of the natural numbers

a(x,y) = A000695(A003188(x)) + 2*A000695(A003188(y))

(Scheme:) (define (A163233bi x y) (+ (A000695 (A003188 x)) (* 2 (A000695 (A003188 y)))))

(define (A163233 n) (A163233bi (A025581 n) (A002262 n)))

Inverse: A163234. a(n) = A057300(A163235(n)). Transpose: A163235. Row sums: A163242. Cf. A054238, A147995.

Sequence in context: A044043 A133128 A057337 this_sequence A096666 A064664 A078386

Adjacent sequences: A163230 A163231 A163232 this_sequence A163234 A163235 A163236

nonn,tabl

Antti Karttunen (His-Firstname.His-Surname(AT)gmail.com), Jul 29 2009

0,2

The top left 8x8 corner of this array

+0 +2 10 +8 40 42 34 32

+1 +3 11 +9 41 43 35 33

+5 +7 15 13 45 47 39 37

+4 +6 14 12 44 46 38 36

20 22 30 28 60 62 54 52

21 23 31 29 61 63 55 53

17 19 27 25 57 59 51 49

16 18 26 24 56 58 50 48

corresponds with Adamson's "H-bond codon-anticodon magic square" (see page 287 in Pickover's book):

CCC CCU CUU CUC UUC UUU UCU UCC

CCA CCG CUG CUA UUA UUG UCG UCA

CAA CAG CGG CGA UGA UGG UAG UAA

CAC CAU CGU CGC UGC UGU UAU UAC

AAC AAU AGU AGC GGC GGU GAU GAC

AAA AAG AGG AGA GGA GGG GAG GAA

ACA ACG AUG AUA GUA GUG GCG GCA

ACC ACU AUU AUC GUC GUU GCU GCC

when the base-triplets are interpreted as quaternary (base-4) numbers, with the following rules: C = 0, A = 1, U = 2, G = 3.

Clifford A. Pickover, The Zen of Magic Squares, Circles, and Stars: An Exhibition of Surprising Structures across Dimensions, Princeton University Press, 2002, pp. 285-289.

A. Karttunen, Table of n, a(n) for n = 0..2079

Index entries for sequences that are permutations of the natural numbers

(Scheme:) (define (A163235 n) (A163233bi (A002262 n) (A025581 n)))

Inverse: A163236. a(n) = A057300(A163233(n)). Transpose: A163233. Row sums: A163242. Cf. A054238, A147995.

Sequence in context: A144274 A144275 A011268 this_sequence A142963 A099755 A110682

Adjacent sequences: A163232 A163233 A163234 this_sequence A163236 A163237 A163238

nonn,tabl

Antti Karttunen (His-Firstname.His-Surname(AT)gmail.com), Jul 29 2009

1,2

Finding a(6) is problem 43 in the Knuth reference. a(6) was estimated to be about 7*10^22 by Silverman, et al.

M. Gardner, Knotted Doughnuts and Other Mathematical Entertainments. Freeman, NY, 1986, p. 24.

D. E. Knuth, The Art of Computer Programming, vol. 4A, Combinatorial Algorithms, (to appear), section 7.2.1.1.

Silverman, Jerry; Vickers, Virgil E.; and Sampson, John L., Statistical estimates of the n-bit Gray codes by restricted random generation of permutations of 1 to 2^n, IEEE Trans. Inform. Theory 29 (1983), no. 6, 894-901.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Eric Weisstein's World of Mathematics, Hamiltonian Circuit

a(n) = 2 * A066037(n).

Equals A006069 divided by 2^n. Cf. A006070, A091299, A003043.

Cf. A091302.

Sequence in context: A090904 A125295 A050649 this_sequence A000887 A118542 A007155

Adjacent sequences: A003039 A003040 A003041 this_sequence A003043 A003044 A003045

nonn,nice

N. J. A. Sloane (njas(AT)research.att.com).

1,1

More precisely, this is the number of ways of making a list of the 2^n nodes of the n-cube, with a distinguished starting position and a direction, such that each node is adjacent to the previous one. The final node may or may not be adjacent to the first.

M. Gardner, Knotted Doughnuts and Other Mathematical Entertainments. Freeman, NY, 1986, p. 24.

Eric Weisstein's World of Mathematics, Hamiltonian Path

a(1) = 2: we have 1,2 or 2,1. a(2) = 8: label the nodes 1, 2, ..., 4. Then the 8 possibilities are 1,2,3,4; 1,3,4,2; 2,3,4,1; 2,1,4,3; etc.

# A Python function that calculates A091299[n] from Janez Brank. (Replace leading dots by spaces!)

.def CountGray(n):

.. def Recurse(unused, lastVal, nextSet):

.... count = 0

.... for changedBit in range(0, min(nextSet + 1, n)):

...... newVal = lastVal ^ (1 << changedBit)

...... mask = 1 << newVal

...... if unused & mask:

........ if unused == mask: count += 1

........ else: count += Recurse(unused & ~mask, newVal,

............................... max(nextSet, changedBit + 1))

.... return count

.. count = Recurse((1 << (1 << n)) - 2, 0, 0)

.. for i in range(1, n + 1): count *= 2 * i

.. return max(1, count)

Equals A006069 + A006070. Divide by 2^n to get A003043. Cf. A003042, A066037, A091302.

Sequence in context: A009817 A124105 A079613 this_sequence A007314 A102099 A012298

Adjacent sequences: A091296 A091297 A091298 this_sequence A091300 A091301 A091302

nonn,more

N. J. A. Sloane (njas(AT)research.att.com), Feb 20 2004

a(5) from Janez Brank (janez.brank(AT)ijs.si), Mar 02 2005

1,8

1 X 1 {{1}}, 2 X 2 {{1, 1}, {1, 0}}, 3 X 3 {{1,1, 1}, {1, 0, 0}, {1, 0, 0}}, 4 X 4 {{1, 1, 1, 1}, {1, 0, 0, 1}, {1, 0,0, 0}, {1, 1, 0, 0}}, 5 X 5 {{1, 1, 1, 1, 1}, {1, 0, 0, 1, 1}, {1, 0, 0, 0, 0}, {1, 1, 0, 0, 0}, {1, 1, 0, 0, 0}}, 6 X 6 {{1, 1, 1, 1, 1, 1}, {1, 0, 0, 1, 1, 0}, {1, 0, 0, 0, 0, 0}, {1,1, 0, 0, 0, 0}, {1, 1, 0, 0, 0, 0}, {1, 0, 0, 0, 0, 0}}

Roger Bagula and Gary Adamson, Pascal's Triangle in Gray Code: its Hadamard and IFS

Binary Matrix: b(i,j) matrix multiplication of two: a[i,j]=b[i,k).b[j,k] a[i,j]-> p[n,x] p(n,x)->t(n,m] Polynomials: 1, 1 - x, -1 - x + x^2, 2 x + x^2 - x^3, 1 - x - 4 x^2 - x^3 + x^4, -2 x + 2 x^2 + 6 x^3 +x^4 - x^5, 4 x^2 - 2 x^3 - 7 x^4 - x^5 +x^6, 2 x - x^2 - 9 x^3 + 3 x^4 + 9 x^5 + x^6 - x^7

{1},

{1, -1},

{-1, -1, 1},

{0, 2, 1, -1},

{1, -1, -4, -1, 1},

{0, -2, 2,6, 1, -1},

{0, 0, 4, -2, -7, -1, 1},

{0, 2, -1, -9, 3, 9,1, -1},

{1, 1, -13, 8, 20, -8, -13, -1, 1},

{0, -2, -2, 24, -15, -31, 13,17, 1, -1},

{0, 0, 4, 4, -40, 20, 44, -14, -19, -1, 1},

{0, 0, 0, -8, -4, 56, -24, -54, 14, 20, 1, -1}

c[i_, k_] := Floor[Mod[i/2^k, 2]]; b[i_, k_] = If[c[i, k] == 0 && c[i, k + 1] == 0, 0, If[c[i, k] == 1 && c[i, k + 1] == 1, 0, 1]]; An[d_] := Table[If[Sum[b[n, k]*b[m, k], {k, 0, d - 1}] == 0, 1, 0], {n, 0, d - 1}, {m, 0, d - 1}]: a=Join[{{1}}, Table[CoefficientList[CharacteristicPolynomial[An[d], x], x], {d, 1, 20}]]; Flatten[a] RowSum=Table[Apply[Plus, Abs[a[[n]]]], {n, 1, Length[a]}]

Cf. A121801.

Sequence in context: A118210 A061399 A161856 this_sequence A107688 A060097 A098120

Adjacent sequences: A122941 A122942 A122943 this_sequence A122945 A122946 A122947

tabl,uned,sign

Roger Bagula and Gary Adamson (rlbagulatftn(AT)yahoo.com), Oct 24 2006

0,4

Let a(0) = 0. Add "1" to each term in n-th row, then bring down to create the first half of the next row. Reverse terms of n-th row and subtract "1", then append, as the right half of row (n+1).

First few rows of the triangle =

0;

1, -1;

2, .0, -2, 0;

3, .1, -1, 1, -1, -3, -1, 1;

4, .2, .0, 2, .0, -2, .0, 2, 0, -2, -4, -2, 0, -2, 0, 2;

...

We present examples of Petoukhov matrices (Cf. A164091) using rows 2 and 3.

.

Row 3 = [2, 0, -2, 0] = A. We crease an "alternating column circulant

If by convention such matrices have an upper left term (1,1), then odd rows

cycle from term (n,n) downward using A. Even rows circulate from (n,n)

upwards (Cf. A164057). Using these rules, we obtain the exponents for

constants k in 4x4 Petoukhov matrices:

.

[2, 0, -2, 0;

.0, 2, 0, -2;

-2, 0, 2, .0;

.0,-2, 0, .2]

.

Let the Petoukhov constant k = phi, 1.6180339,... then insert k into the

matrix using the exponents shown, getting [phi^2, 1, 1/phi^2, 1;

1, phi^2, 1, 1/phi^2; 1/phi^2, 1, phi^2, 1; 1, 1/phi^2, 1, phi^2] = M.

.

Then square matrix: M^2 =

9, 6, 4, 6;

6, 9, 6, 4;

4, 6, 9, 6;

6, 4, 6, 9;

...

The terms (4, 6, 9)may be obtained from a 2x3 multiplication table,

(Cf. A036561, A164057):

.

1,..3,..9,..27,...

2,..6,.18,..54,...

4,.12,.36.........

8..24.............

16................

.

As antidiagonals of this array, we see the terms (4, 6, 9). Similarly,

for the 8x8 matrix, we apply exponents to phi in the next row using the

same circulant rule. As indicated by the next antidiagonal of the 2x3 table,

the 8x8 matrix uses the terms (8, 12, 18, 27), but with a binomial frequency

of (1, 3, 3, 1). The 8x8 matrix is likewise a square of the corresponding

matrix using the exponents [3, 1, -1, 1, -1, -3, -1, 1], then applying the

circulant rule. Let this 8x8 phi matrix = Q. Then Q^2 = the 8x8 Petoukhov

matrix (Cf. A164057):

.

27...18...12...18...12...08...12...18;

18...27...18...12...08...12...18...12;

12...18...27...18...12...18...12...08;

18...12...18...27...18...12...08...12;

12...08...12...18...27...18...12...18;

08...12...18...12...18...27...18...12;

12...18...12...08...12...18...27...18;

18...12...08...12...18...12...18...27;

.

Note the binomial distribution of (by rows and columns) one 27, three 18's

three 12's and one 8. A harmonic relationship is preserved by Knight's moves in any direction

including wrap arounds; any neighbor = (2/3) or (3/2) * another neighbor.

A164057, A036561, A164056, A164057, A147995

Sequence in context: A094098 A164960 A124137 this_sequence A025804 A042961 A029190

Adjacent sequences: A164089 A164090 A164091 this_sequence A164093 A164094 A164095

tabl,sign

Gary W. Adamson (qntmpkt(AT)yahoo.com), Aug 09 2009