A007886 Number of cycles induced by iterating the Gray-coding of an n-bit number: a(n+1) = a(n) + 2^n/C_n, where C_n = least power of 2 >= n (C_n is the length of the cycle), with a(0) = 1.

1, 2, 3, 4, 6, 8, 12, 20, 36, 52, 84, 148, 276, 532, 1044, 2068, 4116, 6164, 10260, 18452, 34836, 67604, 133140, 264212, 526356, 1050644, 2099220, 4196372, 8390676, 16779284, 33556500, 67110932, 134219796, 201328660, 335546388, 603981844

Offset

0,2

Comments

Counts cycles of the prefix-XOR operator on GF(2)^n (conjugate to Gray code). The formula is a direct expansion of the recurrence a(n+1) = a(n) + 2^n/C_n. - Laurent Neau, Jan 16 2026

Links

Laurent Neau, Table of n, a(n) for n = 0..1000

J. Culberson, Mutation-Crossover Isomorphisms and the Construction of Discriminating Functions, Evolutionary Computation 2(3): 279-311, (1994).

Laurent Neau, Algebraic proof of closed-form formula, Jan 2026.

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

Formula

a(n) = 2^(n-L-1) + Sum_{k=0..L} 2^(2^k-k-1) where L = floor(log_2(n)). - Laurent Neau, Jan 16 2026

Prog

(PARI) f(n) = 2^(n-1-log(n+.5)\log(2)) \\ A054243
a(n) = if (n<=1, n+1, a(n-1) + f(n-1));
(PARI) a(n) = if(n==0, 1, my(L=logint(n, 2)); 1<<(n-L-1) + sum(k=0, L, 1<<bitneg(k, k))); \\ Kevin Ryde, Jan 24 2026

Crossrefs

Cf. A054243, A062383 (C_n).

Sequence in context: A018465 A127107 A383332 * A135108 A018515 A018253

Adjacent sequences: A007883 A007884 A007885 * A007887 A007888 A007889

Keyword

nonn,easy

Author

Joe Culberson (joe(AT)cs.ualberta.ca)

Status

approved