cp's OEIS Frontend

A346298 a(n) is the smallest nonnegative number not in a(0..n-1) such that the sequence a(0..n) forms the starting row of an XOR-triangle with only distinct values in each row.

%I A346298 #111 Sep 02 2023 02:25:52
%S A346298 0,1,2,4,3,7,5,8,16,6,10,17,13,24,18,32,22,9,40,21,28,11,35,45,64,20,
%T A346298 31,68,23,36,65,14,128,33,26,56,61,75,19,129,77,102,92,46,121,147,190,
%U A346298 58,119,67,200,78,139,38,25,96,256,49,76,138,34,66,265,207,184,268
%N A346298 a(n) is the smallest nonnegative number not in a(0..n-1) such that the sequence a(0..n) forms the starting row of an XOR-triangle with only distinct values in each row.
%C A346298 This sequence is conjectured to be a permutation of the nonnegative integers.
%C A346298 The second row of the XOR-triangle ((a(0) XOR a(1)), (a(1) XOR a(2)), ...) is a permutation of the positive integers. Further rows miss additional numbers. The first diagonal of this triangle, 0, 1, 2, 7, 3, 5, ..., (A345237) is not a permutation, because it contains multiple equal values.
%C A346298 If we enumerate the imaginary units of a Cayley-Dickson algebra of order m by the positive integers 1 .. 2^m-1, XOR of any pair of these numbers represents the multiplication table of this algebra if signs are ignored. This explains why a(2^n) and A345237(2^n) are equal.
%C A346298 The antidiagonals starting at a(0..2) are {0}, {1, 1}, {2, 3, 2}. Let D(n) be the antidiagonal starting at a(n). Then XOR-sum(D(2^n-1)) = 0 and XOR-sum(D((2*m + 1)*2^(n+1)-1)) = XOR-sum(D((2*m + 1)*2^(p+1)-1)). XOR-sum means XOR over all elements. This property holds also for the XOR-triangle based on the nonnegative integers ordered in sequence.
%H A346298 Rémy Sigrist, <a href="/A346298/b346298.txt">Table of n, a(n) for n = 0..7448</a>
%H A346298 Thomas Scheuerle, <a href="/A346298/a346298.pdf">Triangle based on n = 0..149, drawn as colored surfaces bitwise for bit 0-7</a>. This shows interesting Sierpinski-like structures.
%H A346298 Thomas Scheuerle, <a href="/A346298/a346298.svg">Triangle based on n = 0..149, colored by number</a>.
%H A346298 Thomas Scheuerle, <a href="/A346298/a346298_1.pdf">Triangle based on n = 0..149, colored by parity</a>. Interestingly the amounts of red and green are approximately equal.
%H A346298 Rémy Sigrist, <a href="/A346298/a346298.txt">C++ program</a>.
%F A346298 a(2^n) = A345237(2^n).
%F A346298 a(2^n + m) XOR a(m) = A345237(2^p + q) XOR A345237(q) if 2^n + m = 2^p + q.
%F A346298 a(2^m + 2^n + 2^p + ...) = A345237(k) XOR A345237(k - 2^m) XOR A345237(k - 2^n) XOR A345237(k - 2^p) XOR A345237(k - 2^m - 2^n) XOR A345237(k - 2^m - 2^p) XOR A345237(k - 2^m - 2^n - 2^p) XOR ..., k = 2^m + 2^n + 2^p + ... .
%F A346298 Sum_{k=0..n} a(k) <= Sum_{k=0..n} A345237(k).
%F A346298 ( Sum_{k=0..n} a(k) + Sum_{k=0..n} A345237(k) )^0.4202... < n and > n - 30 at least for n < 500.
%e A346298   0   1   2   4   3   7   5   8  16 ... <-- sequence
%e A346298    \ / \ / \ / \ / \ / \ / \ / \ /         a(0),a(1),a(2),...
%e A346298     1   3   6   7   4   2  13  24 ... <----------+
%e A346298      \ / \ / \ / \ / \ / \ / \ /                 |
%e A346298       2   5   1   3   6  15  21 ... <-+         2nd row is
%e A346298        \ / \ / \ / \ / \ / \ /        |       a(0) XOR a(1),
%e A346298         7   4   2   5   9  26 ...     |       a(1) XOR a(2),
%e A346298          \ / \ / \ / \ / \ /          |       a(2) XOR a(3),
%e A346298           3   6   7  12  19 ...       |            etc.
%e A346298            \ / \ / \ / \ /            |
%e A346298             5   1  11  31 ...         |
%e A346298              \ / \ / \ /              |
%e A346298               4  10  20 ...           |
%e A346298                \ / \ /                |
%e A346298                14  30 ...            3rd row is
%e A346298                  \ /     (a(0) XOR a(1)) XOR (a(1) XOR a(2)),
%e A346298                  16 ...  (a(1) XOR a(2)) XOR (a(2) XOR a(3)),
%e A346298                                          etc.
%e A346298 We show why a(2^n) = A345237(2^n) by reproducing the same process with a randomly chosen set of octonion units: {e0,e1,e2,e5,e6}. XOR is replaced by multiplication.
%e A346298   e0  e1  e2  e5  e6
%e A346298     \/  \/  \/  \/
%e A346298     e1  e3  e7 -e3
%e A346298       \/  \/  \/
%e A346298      -e2 -e4 -e4
%e A346298         \/  \/
%e A346298        -e6 -e0
%e A346298           \/
%e A346298           e6
%o A346298 (MATLAB)
%o A346298 function a = A346298(max_n)
%o A346298     a(1) = 0;
%o A346298     for n = 1:max_n
%o A346298         t = 1;
%o A346298         while ~isok([a t])
%o A346298             t = t+1;
%o A346298         end
%o A346298         a = [a t];
%o A346298     end
%o A346298 end
%o A346298 function [ ok ] = isok( in )
%o A346298     ok = (length(in) == length(unique(in)));
%o A346298     x = in;
%o A346298     if ok
%o A346298         for k = 1:(length(x)-1)
%o A346298             x = bitxor(x(1:end-1),x(2:end));
%o A346298             ok = ok && (length(x) == length(unique(x)));
%o A346298             if ~ok
%o A346298                 break;
%o A346298             end
%o A346298         end
%o A346298     end
%o A346298 end
%o A346298 (C++) See Links section.
%Y A346298 Cf. A345237, A338047 (XOR binomial transform).
%K A346298 nonn,base
%O A346298 0,3
%A A346298 _Thomas Scheuerle_, Jul 13 2021