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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A290772 Number of cyclic Gray codes of length 2n which include all-0 bit sequence and use the least possible number of bits. 0
1, 2, 24, 12, 2640, 7536, 9408, 2688, 208445760, 1082368560, 4312566720, 12473296800, 24050669760 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

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)

LINKS

Table of n, a(n) for n=1..13.

EXAMPLE

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

PROG

(Python)

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

        if x not in a:

            r += cyclic_gray(nb, n, a+[x])

    return r

print([cyclic_gray(ceil(log2(n))+1, n*2, [0]) for n in range(1, 9)])

# Andrey Zabolotskiy, Aug 23 2017

CROSSREFS

Cf. A003042, A286899.

Sequence in context: A075267 A002743 A220773 * A055535 A072217 A229429

Adjacent sequences:  A290769 A290770 A290771 * A290773 A290774 A290775

KEYWORD

nonn,hard,more

AUTHOR

Ashis Kumar Mal, Aug 10 2017

EXTENSIONS

a(7)-a(8) and name from Andrey Zabolotskiy, Aug 23 2017

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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 19 15:49 EDT 2018. Contains 316365 sequences. (Running on oeis4.)