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
Keywords
Examples
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
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_
Crossrefs
Programs
-
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 *) -
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
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
Comments