cp's OEIS Frontend

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.

%I A359506 #41 Dec 01 2024 10:04:58
%S A359506 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,
%T A359506 30,29,36,31,34,33,48,35,38,37,44,39,42,41,56,43,46,45,52,47,50,49,80,
%U A359506 51,54,53,60,55,58,57,72,59,62,61,68,63,66,65,96,67
%N 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.
%C A359506 XOR is the bitwise XOR function, A003987.
%C A359506 This sequence is a bijection from the nonnegative integers to A057716, the nonpowers of 2.
%C A359506 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
%H A359506 Antti Karttunen, <a href="/A359506/b359506.txt">Table of n, a(n) for n = 0..65537</a> (first 1000 terms from Peter Kagey)
%H A359506 Peter Kagey, <a href="/A359506/a359506.pdf">Proof of bijection onto A057716</a> 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_
%F A359506 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
%F A359506 For all n >= 0, A378212(a(n)) = n. - _Antti Karttunen_, Nov 25 2024
%e A359506 For n = 19, a(19) = 28 with the sequence 19 XOR 20 XOR 27 XOR 28 = 0.
%e A359506 A table illustrating the first eleven terms:
%e A359506    n |a(n)| sequence
%e A359506   ---+----+-------------------
%e A359506    0 |  0 |  0
%e A359506    1 |  3 |  1 XOR  2 XOR  3
%e A359506    2 |  5 |  2 XOR  3 XOR  4 XOR  5
%e A359506    3 |  6 |  3 XOR  5 XOR  6
%e A359506    4 |  7 |  4 XOR  5 XOR  6 XOR  7
%e A359506    5 | 10 |  5 XOR  6 XOR  9 XOR 10
%e A359506    6 |  9 |  6 XOR  7 XOR  8 XOR  9
%e A359506    7 | 12 |  7 XOR 11 XOR 12
%e A359506    8 | 11 |  8 XOR  9 XOR 10 XOR 11
%e A359506    9 | 14 |  9 XOR 10 XOR 13 XOR 14
%e A359506   10 | 13 | 10 XOR 11 XOR 12 XOR 13
%p A359506 f:= proc(n) local k,S;
%p A359506     S:= {n};
%p A359506     for k from n+1 do
%p A359506       S:= S union map(Bits:-Xor,S,k);
%p A359506       if member(0,S) then return k fi;
%p A359506     od;
%p A359506 end proc:
%p A359506 f(0):= 0:
%p A359506 map(f, [$0..100]); # _Robert Israel_, Jan 12 2023
%t A359506 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]]]];
%t A359506 f[0] = 0;
%t A359506 f /@ Range[0, 100] (* _Jean-François Alcover_, Jan 22 2023, after _Robert Israel_ *)
%o A359506 (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
%Y A359506 Cf. A003987, A057716, A359507, A359508, A378212 (a left inverse).
%Y A359506 Cf. A006255, A275288, A277278, A277494, A300516, A329732 (variants of the theme).
%K A359506 nonn
%O A359506 0,2
%A A359506 _Peter Kagey_, Jan 03 2023