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

Author

Peter Kagey and Antti Karttunen, Nov 25 2024

Keywords

• nonn

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.

Examples

			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.
		

Links

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

Crossrefs

Left inverse of A359506.

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

Programs

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

Formula

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