bibkey: kurkov2023a006068
authors: N. J. A. Sloane; Paul D. Hanna; Mikhail Kurkov
year: 2023
title: "OEIS A006068, inverse Gray code, with Kurkov's recurrence"
doi: null
url: https://oeis.org/A006068
claim: "A006068 %N: a(n) is Gray-coded into n. A006068 %F: Conjecture: a(n) = a(A053645(A063946(n))) + A053644(n) for n > 0 with a(0) = 0. - _Mikhail Kurkov_, Sep 09 2023"
strata_touched:
  - D5/S1/Digit/Admissibility/KurkovGrayInverseRecurrence
license: citation-only
triage: anchor

OEIS A006068: inverse Gray code

The sequence is defined by its inverse Gray-code property. Paul D. Hanna’s June 4, 2002 formula gives an independent XOR-prefix construction:

a(n) = n XOR [n/2] XOR [n/4] XOR [n/8] … XOR [n/2^m] where m = [log(n)/log(2)] (for n>0) and [x] is integer floor of x.

Hanna’s January 18, 2012 formula states:

a(n) XOR [a(n)/2] = n.

The formal definition writes Hanna’s XOR-prefix formula recursively as a(0)=0 and a(n)=n XOR a(n/2) for positive n, using natural floor division. The first clause of the formal result uses the frozen gray definition to prove the NAME property; the remaining clauses prove the zero boundary and Kurkov’s recurrence.

Verified locator

The following verbatim locators are supplied by the orchestrator’s 2026-09-15 source check. This implementation seat made no network request.

• URL: https://oeis.org/A006068
• %N (verbatim): a(n) is Gray-coded into n.
• Conjecture %F (verbatim): Conjecture: a(n) = a(A053645(A063946(n))) + A053644(n) for n > 0 with a(0) = 0. - Mikhail Kurkov, Sep 09 2023
• %A (verbatim): N. J. A. Sloane

Referenced sequences and scope

For positive n, A053644 is the most significant bit 2^floor(log2 n), and A053645 subtracts A053644 from n. A063946 complements the second bit from the left and fixes zero and one. Its %F line is:

If 22^k <= n < 32^k then a(n) = n + 2^k; if 32^k <= n < 42^k then a(n) = n - 2^k

Both cases are proved and used locally inside the formal result. The formal msb n := 2 ^ Nat.log 2 n agrees with A053644 on positive inputs; its value at zero is 1, whereas A053644(0) is 0. The recurrence uses only positive arguments to msb. These quotations are retained for citation only; completeness of the literature search and priority are not claimed.