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

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.

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.

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.

Example

  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

Prog

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

Crossrefs

Cf. A345237, A338047 (XOR binomial transform).

Sequence in context: A215673 A352716 A120619 * A084385 A073885 A256283

Adjacent sequences: A346295 A346296 A346297 * A346299 A346300 A346301

Keyword

nonn,base

Author

Thomas Scheuerle, Jul 13 2021

Status

approved