A344841 a(n) is the least positive number not of the form a(k) XOR ... XOR a(m) with 1 <= k <= m < n (where XOR denotes the bitwise XOR operator).

1, 2, 4, 5, 8, 12, 14, 16, 17, 19, 20, 21, 23, 32, 33, 35, 48, 49, 51, 56, 57, 59, 64, 65, 67, 68, 69, 71, 76, 77, 79, 80, 81, 83, 84, 85, 87, 92, 93, 95, 128, 129, 131, 132, 133, 135, 140, 141, 143, 192, 193, 195, 196, 197, 199, 204, 205, 207, 224, 225, 227

Offset: 1

Author

Rémy Sigrist, May 29 2021

Keywords

• nonn
• base
• changed

Comments

This sequence has similarities with A002048; here we use XOR, there addition.

All powers of 2 appear.

Examples

			  n   a(n)  a(k) XOR ... XOR a(n) for k=1..n
  --  ----  -------------------------------------
   1     1  1
   2     2  3, 2
   3     4  7, 6, 4
   4     5  2, 3, 1, 5
   5     8  10, 11, 9, 13, 8
   6    12  6, 7, 5, 1, 4, 12
   7    14  8, 9, 11, 15, 10, 2, 14
   8    16  24, 25, 27, 31, 26, 18, 30, 16
   9    17  9, 8, 10, 14, 11, 3, 15, 1, 17
  10    19  26, 27, 25, 29, 24, 16, 28, 18, 2, 19
		

Links

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

Crossrefs

Cf. A002048, A246360.

Programs

PARI

s=2^0; for (n=1, #a=vector(61), print1 (a[n]=valuation(s+1, 2)", "); z=0; forstep (k=n, 1, -1, s=bitor(s, 2^z=bitxor(z,a[k]))))

Python

from operator import xor
from itertools import count, accumulate, islice
from collections import deque
def A344841_gen(): # generator of terms
    aset, alist = set(), deque()
    for k in count(1):
        if k in aset:
            aset.remove(k)
        else:
            yield k
            aset |= set(k^d for d in accumulate(alist,xor))
            alist.appendleft(k)
A344841_list = list(islice(A344841_gen(),60)) # Chai Wah Wu, Sep 01 2025

Formula

Apparently, a(A246360(k)) = 2^(k-1) for any k > 0.