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.

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, 31, 68, 23, 36, 65, 14, 128, 33, 26, 56, 61, 75, 19, 129, 77, 102, 92, 46, 121, 147, 190, 58, 119, 67, 200, 78, 139, 38, 25, 96, 256, 49, 76, 138, 34, 66, 265, 207, 184, 268

Offset: 0

Author

Thomas Scheuerle, Jul 13 2021

Keywords

• nonn
• base

Comments

This sequence is conjectured to be a permutation of the nonnegative integers.

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.

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.

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.

Examples

			  0   1   2   4   3   7   5   8  16 ... <-- sequence
   \ / \ / \ / \ / \ / \ / \ / \ /         a(0),a(1),a(2),...
    1   3   6   7   4   2  13  24 ... <----------+
     \ / \ / \ / \ / \ / \ / \ /                 |
      2   5   1   3   6  15  21 ... <-+         2nd row is
       \ / \ / \ / \ / \ / \ /        |       a(0) XOR a(1),
        7   4   2   5   9  26 ...     |       a(1) XOR a(2),
         \ / \ / \ / \ / \ /          |       a(2) XOR a(3),
          3   6   7  12  19 ...       |            etc.
           \ / \ / \ / \ /            |
            5   1  11  31 ...         |
             \ / \ / \ /              |
              4  10  20 ...           |
               \ / \ /                |
               14  30 ...            3rd row is
                 \ /     (a(0) XOR a(1)) XOR (a(1) XOR a(2)),
                 16 ...  (a(1) XOR a(2)) XOR (a(2) XOR a(3)),
                                         etc.
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.
  e0  e1  e2  e5  e6
    \/  \/  \/  \/
    e1  e3  e7 -e3
      \/  \/  \/
     -e2 -e4 -e4
        \/  \/
       -e6 -e0
          \/
          e6
		

Links

• Rémy Sigrist, Table of n, a(n) for n = 0..7448
• Thomas Scheuerle, Triangle based on n = 0..149, drawn as colored surfaces bitwise for bit 0-7. This shows interesting Sierpinski-like structures.
• Thomas Scheuerle, Triangle based on n = 0..149, colored by number.
• Thomas Scheuerle, Triangle based on n = 0..149, colored by parity. Interestingly the amounts of red and green are approximately equal.
• Rémy Sigrist, C++ program.

Crossrefs

Cf. A345237, A338047 (XOR binomial transform).

Programs

MATLAB

function a = A346298(max_n)
    a(1) = 0;
    for n = 1:max_n
        t = 1;
        while ~isok([a t])
            t = t+1;
        end
        a = [a t];
    end
end
function [ ok ] = isok( in )
    ok = (length(in) == length(unique(in)));
    x = in;
    if ok
        for k = 1:(length(x)-1)
            x = bitxor(x(1:end-1),x(2:end));
            ok = ok && (length(x) == length(unique(x)));
            if ~ok
                break;
            end
        end
    end
end
(C++) See Links section.

Formula

a(2^n) = A345237(2^n).

a(2^n + m) XOR a(m) = A345237(2^p + q) XOR A345237(q) if 2^n + m = 2^p + q.

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

Sum_{k=0..n} a(k) <= Sum_{k=0..n} A345237(k).

( Sum_{k=0..n} a(k) + Sum_{k=0..n} A345237(k) )^0.4202... < n and > n - 30 at least for n < 500.