A359506 a(n) is the least integer m such that there exists a strictly increasing integer sequence n = b_1 < b_2 < ... < b_t = m with the property that b_1 XOR b_2 XOR ... XOR b_t = 0.

0, 3, 5, 6, 7, 10, 9, 12, 11, 14, 13, 20, 15, 18, 17, 24, 19, 22, 21, 28, 23, 26, 25, 40, 27, 30, 29, 36, 31, 34, 33, 48, 35, 38, 37, 44, 39, 42, 41, 56, 43, 46, 45, 52, 47, 50, 49, 80, 51, 54, 53, 60, 55, 58, 57, 72, 59, 62, 61, 68, 63, 66, 65, 96, 67

Offset

0,2

Comments

XOR is the bitwise XOR function, A003987.

This sequence is a bijection from the nonnegative integers to A057716, the nonpowers of 2.

Let's call the sequences mentioned in the definition as "zero-XOR sequences", and their last terms as "enders". a(n) is then the least possible ender for any zero-XOR sequence starting with n. - Antti Karttunen, Nov 25 2024

Links

Antti Karttunen, Table of n, a(n) for n = 0..65537 (first 1000 terms from Peter Kagey)

Peter Kagey, Proof of bijection onto A057716 Note: there is a typo in this first revision of the proof. In the definition of f (which is now A378212) "Let f(n) be the least nonnegative integer k such that ...", the "least" should actually be "greatest", Antti Karttunen, Dec 01 2024, as communicated by Peter Kagey

Formula

For n > 1, a(n) >= n + 3. a(4n) = 4n + 3 for n > 0. Conjecture: a(n) <= 5(n+1)/3. - Charles R Greathouse IV, Jan 12 2023

For all n >= 0, A378212(a(n)) = n. - Antti Karttunen, Nov 25 2024

Example

For n = 19, a(19) = 28 with the sequence 19 XOR 20 XOR 27 XOR 28 = 0.
A table illustrating the first eleven terms:
   n |a(n)| sequence
  ---+----+-------------------
   0 |  0 |  0
   1 |  3 |  1 XOR  2 XOR  3
   2 |  5 |  2 XOR  3 XOR  4 XOR  5
   3 |  6 |  3 XOR  5 XOR  6
   4 |  7 |  4 XOR  5 XOR  6 XOR  7
   5 | 10 |  5 XOR  6 XOR  9 XOR 10
   6 |  9 |  6 XOR  7 XOR  8 XOR  9
   7 | 12 |  7 XOR 11 XOR 12
   8 | 11 |  8 XOR  9 XOR 10 XOR 11
   9 | 14 |  9 XOR 10 XOR 13 XOR 14
  10 | 13 | 10 XOR 11 XOR 12 XOR 13

Maple

f:= proc(n) local k, S;
    S:= {n};
    for k from n+1 do
      S:= S union map(Bits:-Xor, S, k);
      if member(0, S) then return k fi;
    od;
end proc:
f(0):= 0:
map(f, [$0..100]); # Robert Israel, Jan 12 2023

Mathematica

f[n_] := Module[{k, S}, S = {n}; For[k = n+1, True, k++, S = S  ~Union~ BitXor[S, k]; If[MemberQ[S, 0], Return[k]]]];
f[0] = 0;
f /@ Range[0, 100] (* Jean-François Alcover, Jan 22 2023, after Robert Israel *)

Prog

(PARI) a(n)= if (n==0, return (0), my (x=[n], y); for (m=n+1, oo, if (vecmin(y=[bitxor(v, m) | v<-x])==0, return (m), x=setunion(x, Set(y)))))  \\ Rémy Sigrist, Jan 12 2023

Crossrefs

Cf. A003987, A057716, A359507, A359508, A378212 (a left inverse).

Cf. A006255, A275288, A277278, A277494, A300516, A329732 (variants of the theme).

Sequence in context: A242883 A163621 A124194 * A379346 A055597 A053048

Adjacent sequences: A359503 A359504 A359505 * A359507 A359508 A359509

Keyword

nonn

Author

Peter Kagey, Jan 03 2023

Status

approved