cp's OEIS Frontend

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

%I A378212 #17 Nov 30 2024 12:57:10
%S A378212 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,
%T A378212 19,26,25,28,0,30,29,32,27,34,33,36,23,38,37,40,35,42,41,44,31,46,45,
%U A378212 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
%N 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).
%C A378212 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]
%C A378212 With 0's removed this is a permutation of natural numbers.
%H A378212 Antti Karttunen, <a href="/A378212/b378212.txt">Table of n, a(n) for n = 0..65537</a>
%F A378212 For all n >= 0, a(A359506(n)) = n.
%e A378212 A table illustrating the first fifteen terms:
%e A378212    n |a(n)| sequence
%e A378212   ---+----+-------------------------------------------------------------
%e A378212    0 |  0 |  0
%e A378212    1 |  0 |  As 1 = 2^0, there are no zero-XOR sequences ending with it
%e A378212    2 |  0 |  (ditto, 2 = 2^1)
%e A378212    3 |  1 |  1 XOR  2 XOR  3
%e A378212    4 |  0 |  4 = 2^2
%e A378212    5 |  2 |  2 XOR  3 XOR  4 XOR  5
%e A378212    6 |  3 |  3 XOR  5 XOR  6
%e A378212    7 |  4 |  4 XOR  5 XOR  6 XOR  7
%e A378212    8 |  0 |  8 = 2^3
%e A378212    9 |  6 |  6 XOR  7 XOR  8 XOR  9
%e A378212   10 |  5 |  5 XOR  6 XOR  9 XOR 10
%e A378212   11 |  8 |  8 XOR  9 XOR 10 XOR 11
%e A378212   12 |  7 |  7 XOR 11 XOR 12
%e A378212   13 | 10 | 10 XOR 11 XOR 12 XOR 13
%e A378212   14 |  9 |  9 XOR 10 XOR 13 XOR 14
%e A378212   ---+----+-------------------------------------------------------------
%e A378212 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.
%o A378212 (PARI)
%o A378212 up_to = 65537;
%o A378212 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.
%o A378212 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); };
%o A378212 v378212 = A378212list(up_to);
%o A378212 A378212(n) = if(!n,n,v378212[n]);
%Y A378212 Left inverse of A359506.
%Y A378212 Cf. A131577 (positions of 0's), A348296.
%K A378212 nonn
%O A378212 0,6
%A A378212 _Peter Kagey_ and _Antti Karttunen_, Nov 25 2024