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,2

Comments

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

All powers of 2 appear.

Links

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

Formula

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

Example

  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

Prog

(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

Crossrefs

Cf. A002048, A246360.

Sequence in context: A190190 A063465 A287346 * A035001 A260386 A092268

Adjacent sequences: A344838 A344839 A344840 * A344842 A344843 A344844

Keyword

nonn,base

Author

Rémy Sigrist, May 29 2021

Status

approved