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

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,6

Comments

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.

Links

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

Formula

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

Example

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.

Prog

(PARI)
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]);

Crossrefs

Left inverse of A359506.

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

Sequence in context: A232749 A181578 A065332 * A381094 A265515 A336564

Adjacent sequences: A378209 A378210 A378211 * A378213 A378214 A378215

Keyword

nonn

Author

Peter Kagey and Antti Karttunen, Nov 25 2024

Status

approved