brgc_word
def
The binary reflected Gray code word of rank t, read as a binary number: g(t) = t xor floor(t/2).
Statement
def brgc_word (t : ℕ) : ℕ- Defined in
- arXiv:2610.24758 (Optimal single-track Gray codes from Gray-ordered necklaces), Conjecture 1 (prime case of a conjecture from 2007), Sec. 1; the BRGC g(t) = t xor floor(t/2) of Sec. 1
- Verified
- 20 Oct 2026
- Axioms
- none listed
- Used by 37
- brgc_necklace_order_not_consecutive_adjacent_sixPrimality cannot be dropped from the adjacency conjecture: at n = 6 the consecutive necklaces 001001 and 011011 of D_6 (both periodic) are…
- brgc_necklace_order_consecutive_adjacent_sevenThe case n = 7 of the conjecture: consecutive necklaces of D_7 are adjacent in Q_7.
- lexical_degree_seventeen_class_a_counterexampleThe lexical sequences a = (3,1,1,3,3,2,2,1) and b = (3,1,1,2,1,3,2,2,1) both have degree 16, are adjacent in the source lexical order…
- necklace_graph_has_hamilton_cycleThere exists an indexing cycle of the non-constant necklaces of length n such that the first m = (2^n - 2) / n values are distinct valid…
- brgc_inverse_prefixThe inverse Gray rank of a high-bit prefix is the corresponding high-bit prefix of the inverse rank.
- brgc_necklace_first_rank_unique_of_rotationTwo first-occurrence Gray ranks representing the same nonconstant necklace are equal.
- brgc_word_xorBinary reflected Gray encoding preserves bitwise exclusive-or.
- brgc_inverse_concatThe inverse Gray rank of a concatenation has the prefix inverse rank followed by the suffix inverse rank, complemented exactly when the…
- brgc_arbitrary_symmetric_intervals_obstructionTwo separate rank reflections need not compose to a one-bit Gray-word difference.
- brgc_local_reflection_generator_obstructionTwo strict maximum-rank primitive generators whose proposed local generator reflection is not maximum-rank; an obstruction to a naive…
- brgc_word_injectiveBinary reflected Gray encoding is injective on natural numbers.
- brgc_word_div_twoThe binary reflected Gray encoding commutes with division by two.
- brgc_inverse_flip_preserves_cut_maxIf an n-bit word has strictly greater inverse Gray rank than every nontrivial cyclic cut, toggling its last bit has at least as great an…
- brgc_word_inverseEncoding the n-bit inverse prefix-parity transform recovers the word.
- brgc_word_lt_two_powAn n-bit rank encodes an n-bit word.
- brgc_word_div_powTaking a high-bit prefix commutes with binary reflected Gray encoding.
- brgc_necklace_first_rank_exists_of_nonconstantEvery nonconstant binary word of length at least two has a first-occurrence Gray rank in its rotation class.
- brgc_necklace_first_rank_rotation_maxRotating a first-occurrence representative right once gives a representative of maximum inverse Gray rank in its rotation class; the…
- brgc_word_low_onesA rank consisting of k+1 low one-bits encodes the word with only bit k set.
- brgc_word_eq_zero_iffThe zero word is encoded exactly by rank zero.
- brgc_necklace_order_consecutive_adjacent_fiveThe case n = 5 of the conjecture: consecutive necklaces of D_5 are adjacent in Q_5.
- brgc_necklace_first_rank_min_rotationsEvery rotation of a first-occurrence representative has inverse Gray rank at least its first-occurrence rank.
- brgc_necklace_order_consecutive_aperiodic_adjacent_sixThe case n = 6 (composite, with periodic necklaces that break the adjacency) of the aperiodic adjacency conjecture: consecutive aperiodic…
- alpha_binary_prefix_inverse_parityThe inverse Gray rank of the prefix has the parity of the number of encoded one bits, namely the cell count.
- brgc_necklace_first_rank_word_oddFor length at least two, the first nonconstant representative in Gray order has final bit one.
- gray_ordered_necklaces_is_gray_pathThe list D_n of non-constant binary necklaces of length n, ordered by the rank of their first occurrences in the binary reflected Gray…
- alpha_lexical_example_elevenKernel-checked encoding of the length-eleven example in arXiv:0810.5205, Example 3.2, including its one-bit completed words and the…
- brgc_word_one_bit_iff_rank_reflectionTwo Gray words differ exactly in bit k if and only if their ranks differ by exclusive-or with k+1 low one-bits.
- brgc_word_twoSanity check: the BRGC word of rank 2 is 011.
- brgc_inverse_wordThe n-bit inverse prefix-parity transform recovers an n-bit Gray rank from its encoded word.
- bitword_necklace_adjacent_of_brgc_rank_reflectionIf two Gray ranks differ by exclusive-or with k+1 low one-bits and k is less than the word length, their words are adjacent with rotation…
- brgc_necklace_first_rankt is the BRGC rank of the first occurrence of a nonconstant binary necklace of length n: t < 2^n, the word g(t) is neither 0^n nor 1^n,…
- brgc_necklace_order_consecutive_aperiodic_adjacent_eightThe case n = 8 (composite, with periodic necklaces that break the adjacency) of the aperiodic adjacency conjecture: consecutive aperiodic…
- brgc_inverse_rotate_tent_formulaIn inverse Gray-rank coordinates, cyclic left rotation is the two-branch integer tent map, with the rank parity carried along.
- brgc_necklace_first_rank_mod_fourFor length at least two, each first-occurrence rank of a nonconstant necklace is congruent to one or two modulo four.
- brgc_necklace_order_consecutive_aperiodic_adjacent_nineThe case n = 9 (composite, with periodic necklaces that break the adjacency) of the aperiodic adjacency conjecture: consecutive aperiodic…
- brgc_inverse_alpha_binary_prefix_consThe inverse Gray rank of x :: xs equals 2^xs.sum * (2^x - 1) + (2^xs.sum - 1 - brgc_inverse xs.sum (alpha_binary_prefix xs)).
Lean source view module on GitHub
/-- The binary reflected Gray code word of rank t, read as a binary number: g(t) = t xor floor(t/2). -/ def brgc_word (t : ℕ) : ℕ := t ^^^ (t / 2)