A359508 -id:A359508 - 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.

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

Peter Kagey, Jan 03 2023

nonn

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

			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

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_

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

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

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

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 *)

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

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

A378218 Dirichlet inverse of A345182.

Original entry on oeis.org

1, 0, -1, -1, -1, -2, -1, -2, -1, -2, -1, -3, -1, -2, -1, -3, -1, -2, -1, -3, -1, -2, -1, -4, -1, -2, -1, -3, -1, -2, -1, -4, -1, -2, -1, -3, -1, -2, -1, -4, -1, -2, -1, -3, -1, -2, -1, -5, -1, -2, -1, -3, -1, -2, -1, -4, -1, -2, -1, -3, -1, -2, -1, -5, -1, -2, -1, -3, -1, -2, -1, -4, -1, -2, -1, -3, -1, -2, -1, -5

Offset: 1

Antti Karttunen, Nov 22 2024

sign

Antti Karttunen, Table of n, a(n) for n = 1..65537

Cf. A345182, A359508.

memoA345182 = Map();
A345182(n) = if(n<=2, n%2, my(v); if(mapisdefined(memoA345182,n,&v), v, v = sumdiv(n,d,if(dA345182(d),0)); mapput(memoA345182,n,v); (v)));
memoA378218 = Map();
A378218(n) = if(1==n,1,my(v); if(mapisdefined(memoA378218,n,&v), v, v = -sumdiv(n,d,if(dA345182(n/d)*A378218(d),0)); mapput(memoA378218,n,v); (v)));

a(1) = 1, and for n > 1, a(n) = -Sum_{d|n, dA345182(n/d) * a(d).

Apparently, abs(a(n+1)) = A359508(n).

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

Original entry on oeis.org

0, 2, 3, 3, 3, 5, 3, 5, 3, 5, 3, 9, 3, 5, 3, 9, 3, 5, 3, 9, 3, 5, 3, 17, 3, 5, 3, 9, 3, 5, 3, 17, 3, 5, 3, 9, 3, 5, 3, 17, 3, 5, 3, 9, 3, 5, 3, 33, 3, 5, 3, 9, 3, 5, 3, 17, 3, 5, 3, 9, 3, 5, 3, 33, 3, 5, 3, 9, 3, 5, 3, 17, 3, 5, 3, 9, 3, 5, 3, 33, 3, 5, 3, 9, 3, 5, 3, 17, 3, 5, 3, 9, 3, 5, 3, 65, 3, 5, 3, 9, 3, 5

Offset: 0

Peter Kagey, Jan 03 2023

nonn

Conjecture: a(n) is of the form 2^k + 1 for all n > 0.

Antti Karttunen, Table of n, a(n) for n = 0..65537

Cf. A092487, A359506, A359508.

A359506(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))))); \\ From A359506.
A359507(n) = (A359506(n)-n); \\ Antti Karttunen, Nov 22 2024

a(n) = A359506(n) - n.

More terms from Antti Karttunen, Nov 22 2024

A359509 a(n) is the number of subsets {b_1, b_2, ..., b_t} of {n, n+1, ..., A359506(n)} containing n with the property that b_1 XOR b_2 XOR ... XOR b_t = 0.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 2, 1, 2, 1, 16, 1, 2, 1, 16, 1, 2, 1, 16, 1, 2, 1, 2048, 1, 2, 1, 16, 1, 2, 1, 2048, 1, 2, 1, 16, 1, 2, 1, 2048, 1, 2, 1, 16, 1, 2, 1, 67108864, 1, 2, 1, 16, 1, 2, 1, 2048, 1, 2, 1, 16, 1, 2, 1, 67108864, 1, 2, 1, 16, 1, 2, 1, 2048, 1, 2, 1

Offset: 0

Peter Kagey, Jan 03 2023

nonn

Cf. A000295, A359508.

Conjectured formula: a(n) = 2^A000295(A359508(n)) for n > 0.

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A378218 Dirichlet inverse of A345182.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

Extensions

A359509 a(n) is the number of subsets {b_1, b_2, ..., b_t} of {n, n+1, ..., A359506(n)} containing n with the property that b_1 XOR b_2 XOR ... XOR b_t = 0.

Views

Author

Keywords

Crossrefs

Formula