A359506 -id:A359506 - cp's OEIS frontend

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.

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.

A359508 a(n) = log_2(A359507(n) - 1).

Original entry on oeis.org

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, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 6, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2

Offset: 1

Peter Kagey, Jan 03 2023

nonn

Conjecture: A359507(n) is always of the form 2^m + 1.

If log_2(A359507(n) - 1) is not an integer, then define a(n) = -1.

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

Cf. A000523, A359506, A359507, A378218.

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);
A359508(n) = (#digits(A359507(n)-1, 2)-1); \\ Antti Karttunen, Nov 22 2024

a(n) = A000523(A359507(n)-1).
Conjecture:
a(4k)   = 1 for k > 0,
a(4k+1) = 2 for k > 0,
a(4k+2) = 1 for k > 0,
a(4k+3) = a(k) + 2 for k > 0.
Apparently, a(n) = abs(A378218(1+n)). [This holds at least up to n=65537] - Antti Karttunen, Nov 22 2024
a(n) = A007814((n - 3*b(n + 1) + 2) mod b(n + 1) + b(n + 2) - 1) + 1, where b(n) = 2^A000523(A002264(n)) for n >= 4. - Alan Michael Gómez Calderón, Feb 25 2025

More terms from Antti Karttunen, Nov 22 2024

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

A378212 a(n) is the greatest nonnegative integer k such that there exists a strictly increasing integer sequence k = b_1 < b_2 < ... < b_t = n with the property that b_1 XOR b_2 XOR ... XOR b_t = 0, or 0 if there are no such k (when n is a power of 2).

Original entry on oeis.org

0, 0, 0, 1, 0, 2, 3, 4, 0, 6, 5, 8, 7, 10, 9, 12, 0, 14, 13, 16, 11, 18, 17, 20, 15, 22, 21, 24, 19, 26, 25, 28, 0, 30, 29, 32, 27, 34, 33, 36, 23, 38, 37, 40, 35, 42, 41, 44, 31, 46, 45, 48, 43, 50, 49, 52, 39, 54, 53, 56, 51, 58, 57, 60, 0, 62, 61, 64, 59, 66, 65, 68, 55, 70, 69, 72, 67, 74, 73, 76, 47, 78, 77

Offset: 0

Peter Kagey and Antti Karttunen, Nov 25 2024

nonn

Let's call the sequences mentioned in the definition as "zero-XOR sequences", and their first terms as "starters". a(n) is then the greatest possible starter for any zero-XOR sequence ending with n. a(2^k)'s are set to 0's, because there are no zero-XOR sequences ending with any power of two. That such a sequence exists for any n that is not a power of 2 can be seen from the n-th row of A348296. [This from Peter's PDF-proof at A359506]

With 0's removed this is a permutation of natural numbers.

			A table illustrating the first fifteen terms:
   n |a(n)| sequence
  ---+----+-------------------------------------------------------------
   0 |  0 |  0
   1 |  0 |  As 1 = 2^0, there are no zero-XOR sequences ending with it
   2 |  0 |  (ditto, 2 = 2^1)
   3 |  1 |  1 XOR  2 XOR  3
   4 |  0 |  4 = 2^2
   5 |  2 |  2 XOR  3 XOR  4 XOR  5
   6 |  3 |  3 XOR  5 XOR  6
   7 |  4 |  4 XOR  5 XOR  6 XOR  7
   8 |  0 |  8 = 2^3
   9 |  6 |  6 XOR  7 XOR  8 XOR  9
  10 |  5 |  5 XOR  6 XOR  9 XOR 10
  11 |  8 |  8 XOR  9 XOR 10 XOR 11
  12 |  7 |  7 XOR 11 XOR 12
  13 | 10 | 10 XOR 11 XOR 12 XOR 13
  14 |  9 |  9 XOR 10 XOR 13 XOR 14
  ---+----+-------------------------------------------------------------
Note that there are often other solutions for a zero-XOR sequence ending with n, as for example the terms taken from the n-th row of A348296, followed by n, like for example [2, 8, 10] for 10, [1, 2, 8, 11] for 11, or [2, 4, 8, 14] for 14, but in those cases the starting term is not the greatest possible starter for a sequence ending with n that satisfies the condition.

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

Left inverse of A359506.

Cf. A131577 (positions of 0's), A348296.

up_to = 65537;
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.
A378212list(up_to_n) = { my(v=vector(up_to_n), k); for(n=1, up_to_n, k=A359506(n); if(k <= up_to_n, if(0==v[k], v[k]=n, print("Not injective! A359506(",v[k],")=A359506("n")="k); return(1/0)))); (v); };
v378212 = A378212list(up_to);
A378212(n) = if(!n,n,v378212[n]);

For all n >= 0, a(A359506(n)) = n.

cp's OEIS Frontend

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

A359508 a(n) = log_2(A359507(n) - 1).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

Extensions

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

A378212 a(n) is the greatest nonnegative integer k such that there exists a strictly increasing integer sequence k = b_1 < b_2 < ... < b_t = n with the property that b_1 XOR b_2 XOR ... XOR b_t = 0, or 0 if there are no such k (when n is a power of 2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula