A350784 -id:A350784 - cp's OEIS frontend

A236602 Number of canonical Gray cycles of length 2n.

1, 1, 1, 6, 4, 22, 96, 1344, 672, 3448, 12114, 158424, 406312, 4579440, 37826256, 906545760, 362618304, 1784113248, 5576251408, 68998853808, 154939065862

Offset: 1

Stanislav Sykora, Feb 01 2014

By a canonical Gray cycle (CGC) of length 2n is intended a monocyclic permutation of the integers {0,1,2,...,2n-1} such that (i) it starts with "0", (ii) the binary expansions of any two adjacent terms of the cycle differ by exactly one bit, and (iii) the last term is larger than the second. Note: there are no CGC's of odd length.
For n>1, a(n) is also the number of all distinct Hamiltonian circuits in a simple graph with 2n vertices, labeled 0,1,2,...,(2n-1), in which two vertices are connected by an edge only if the binary expansions of their labels differ by exactly one bit.
The sequence is a superset of A066037.

			a(5) = 4 since there are only these 4 CGC's of length 10:
{0 2 3 7 6 4 5 1 9 8}
{0 2 6 4 5 7 3 1 9 8}
{0 4 5 7 6 2 3 1 9 8}
{0 4 6 2 3 7 5 1 9 8}

Stanislav Sykora, On Canonical Gray Cycles, Stan's Library, Vol.V, January 2014, DOI: 10.3247/SL5Math14.001.

Cf. A066037 (subset), A236603, A350784.

A236602[n_] := Count[Map[lpf, Map[j0f, Permutations[Range[2 n - 1]]]], 0]/2;
j0f[x_] := Join[{0}, x, {0}];
btf[x_] := Module[{i},
   Table[DigitCount[BitXor[x[[i]], x[[i + 1]]], 2, 1], {i,
     Length[x] - 1}]];
lpf[x_] := Length[Select[btf[x], # != 1 &]];
Join[{1}, Table[A236602[n], {n, 2, 5}]]
(* OR, a less simple, but more efficient implementation. *)
A236602[n_, perm_, remain_] := Module[{opt, lr, i, new},
   If[remain == {},
     If[DigitCount[BitXor[First[perm], Last[perm]], 2, 1] == 1, ct++];
     Return[ct],
     opt = remain; lr = Length[remain];
     For[i = 1, i <= lr, i++,
      new = First[opt]; opt = Rest[opt];
      If[DigitCount[BitXor[Last[perm], new], 2, 1] != 1, Continue[]];
      A236602[n, Join[perm, {new}],
       Complement[Range[2 n - 1], perm, {new}]];
      ];
     Return[ct];
     ];
   ];
Join[{1}, Table[ct = 0; A236602[n, {0}, Range[2 n - 1]]/2, {n, 2, 8}] ](* Robert Price, Oct 25 2018 *)

a(2^(n-1)) = A066037(n).

a(n) = A350784(n)/2 for n >= 2. - Martin Ehrenstein, Feb 16 2022

a(17)-a(18) from Fausto A. C. Cariboni, May 13 2017
a(19)-a(20) from Martin Ehrenstein, Feb 16 2022
a(21) from Martin Ehrenstein, Feb 21 2022

A290772 Number of cyclic Gray codes of length 2n which include all-0 bit sequence and use the least possible number of bits.

Original entry on oeis.org

1, 2, 24, 12, 2640, 7536, 9408, 2688, 208445760, 1082368560, 4312566720, 12473296800, 24050669760, 27034640640, 13900259520, 1813091520

Offset: 1

Ashis Kumar Mal, Aug 10 2017

From Andrey Zabolotskiy, Aug 23 2017: (Start)
The smallest number of bits needed is ceiling(log_2(n)). For larger number of bits, more Gray codes exist. Cyclic Gray codes of odd lengths do not exist, hence only even lengths are considered.
A003042 is a subsequence: A003042(n+1) = a(2^n).
a(n) is also the number of self-avoiding directed cycles of length 2n on a cube of the least possible dimension starting from the origin.
(End)

			Let n=3, so we count codes of length 6. Then at least 3 bits are needed to have such a code. There are a(3)=24 3-bit cyclic Gray codes of length 6:
000, 001, 011, 010, 110, 100
000, 001, 011, 111, 110, 100
000, 001, 011, 111, 110, 010
000, 001, 011, 111, 101, 100
000, 001, 101, 100, 110, 010
000, 001, 101, 111, 110, 100
000, 001, 101, 111, 110, 010
000, 001, 101, 111, 011, 010
000, 010, 011, 001, 101, 100
000, 010, 011, 111, 110, 100
000, 010, 011, 111, 101, 100
000, 010, 011, 111, 101, 001
000, 010, 110, 111, 101, 100
000, 010, 110, 111, 101, 001
000, 010, 110, 111, 011, 001
000, 010, 110, 100, 101, 001
000, 100, 101, 111, 110, 010
000, 100, 101, 111, 011, 010
000, 100, 101, 111, 011, 001
000, 100, 101, 001, 011, 010
000, 100, 110, 111, 101, 001
000, 100, 110, 111, 011, 010
000, 100, 110, 111, 011, 001
000, 100, 110, 010, 011, 001

Thomas König, Fortran program for counting

Cf. A003042, A286899, A350784.

from math import log2, ceil
def cyclic_gray(nb, n, a):
    if len(a) == n:
        if bin(a[-1]).count('1') == 1:
            return 1
        return 0
    r = 0
    for i in range(nb):
        x = a[-1] ^ (1<Andrey Zabolotskiy, Aug 23 2017

a(7)-a(8) and name from Andrey Zabolotskiy, Aug 23 2017
a(9)-a(13) from Ashis Kumar Mal, Sep 02 2017
a(14)-a(16) from Thomas König, Jan 22 2022

A385185 Number of permutations of 0..n-1 which are binary Gray codes.

Original entry on oeis.org

1, 2, 2, 8, 4, 16, 24, 144, 36, 164, 192, 1168, 976, 5688, 10656, 91392, 11424, 67032, 61840, 403568, 258956, 1589080, 2520324, 22646880, 10898976, 67039504, 93326800, 819193248, 924489888, 7399407552, 16309883520, 187499658240, 11718728640

Offset: 1

Ross Drewe, Aug 03 2025

In a binary Gray code, the binary expansions of any two consecutive terms differ at a single bit position.

When n is odd, the binary weights of n and the first term in the permutation must have opposite parity, since otherwise it's not possible to step through all of 0,...,n-1.

			For n=5, the a(5) = 4 possible permutations which are Gray codes are
  1 3 2 0 4
  2 3 1 0 4
  4 0 1 3 2
  4 0 2 3 1
For n=8, a(8) = 144 includes 0 1 3 2 6 4 5 7 which is lexicographically smallest, and also includes the binary reflected Graycode 0 1 3 2 6 7 5 4.

Cf. A091299, A350784 (when beginning with 0).

function N = Gcode(L); H = hmap; N = 0; unused = uint8([0: L-1]); for i = 1:length(unused); g = unused(i); u = unused; u(i) = []; gray(g, u); end
function gray(g, u); curidx = g(end) + 1; d = H(curidx,:); if isscalar(u); if d(u+1); N = N + 1; end; else for j = 1: length(u); r = u(j); if d(r+1); nextg = [g r]; nextu = u; nextu(j) = []; gray(nextg, nextu); end; end; end; end
function map = hmap; map = false(L, L); S = uint8([0:L-1]); [X,Y] = meshgrid(S); X = X(:); Y = Y(:);
xb = de2bi(X); yb = de2bi(Y); for k = 1:L^2; v = sum(bitxor(xb(k,:), yb(k,:))); if v == 1; map(k) = true; end; end; end; end

a(2^n) = A091299(n).

a(2^n+1) = a(2^n)/2^(n-1) for n > 0. - Andrew Howroyd, Aug 04 2025

a(27)-a(33) from Andrew Howroyd, Aug 04 2025

cp's OEIS Frontend

A236602 Number of canonical Gray cycles of length 2n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A290772 Number of cyclic Gray codes of length 2n which include all-0 bit sequence and use the least possible number of bits.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Extensions

A385185 Number of permutations of 0..n-1 which are binary Gray codes.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

MATLAB

Formula

Extensions