A336033 a(n) is the number of k such that 1 <= k < n and a(k) XOR ... XOR a(n-1) = 0 (where XOR denotes the bitwise XOR operator).

0, 1, 0, 1, 2, 0, 1, 0, 1, 2, 3, 2, 2, 3, 4, 0, 1, 0, 1, 2, 0, 1, 0, 1, 2, 3, 2, 2, 3, 4, 5, 3, 3, 4, 3, 3, 4, 5, 6, 4, 4, 5, 4, 4, 5, 6, 7, 5, 5, 6, 5, 5, 6, 7, 8, 0, 1, 0, 1, 2, 0, 1, 0, 1, 2, 3, 2, 2, 3, 4, 0, 1, 0, 1, 2, 0, 1, 0, 1, 2, 3, 2, 2, 3, 4, 5, 3

Offset: 1

Author

Rémy Sigrist, Jul 07 2020

Keywords

• nonn
• base

Comments

This sequence has fractal features; each time the sequence hits a new power of 2, say a(m) = 2^k for the first time, then a(m + i) = a(i) for i = 1..m and a(2*m + 1) = 1 + a(m).

These are (a strong conjecture) the "y" values from A340488. - Rémy Sigrist, Jan 11 2021

Examples

			The first terms, alongside the corresponding k's, are:
  n   a(n)  k's
  --  ----  -------
   1     0  {}
   2     1  {1}
   3     0  {}
   4     1  {3}
   5     2  {1, 2}
   6     0  {}
   7     1  {6}
   8     0  {}
   9     1  {8}
  10     2  {6, 7}
  11     3  {1, 2, 5}
  12     2  {8, 9}
		

Links

• Rémy Sigrist, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A336190, A340488.

Programs

PARI

for (n=1, #a=vector(87), x=0; forstep (k=n-1, 1, -1, if (0==x=bitxor(x, a[k]), a[n]=1+a[k]; break)); print1 (a[n] ", "))