A358918 a(0) = 0, and for any n >= 0, a(n+1) is the length of the longest run of consecutive terms a(i), ..., a(j) with 0 <= i <= j <= n such that a(i) XOR ... a(j) = a(n) (where XOR denotes the bitwise XOR operator).

0, 1, 2, 1, 2, 4, 6, 2, 7, 9, 1, 6, 7, 9, 12, 9, 12, 13, 14, 17, 1, 14, 17, 18, 20, 18, 20, 22, 26, 18, 20, 28, 30, 26, 22, 28, 30, 30, 32, 3, 28, 30, 32, 3, 28, 38, 40, 22, 34, 46, 26, 41, 31, 45, 42, 40, 37, 41, 31, 58, 60, 53, 54, 57, 57, 57, 57, 57, 57, 57

Offset: 0

Author

Rémy Sigrist, Dec 06 2022

Keywords

• nonn
• base

Comments

The sequence has periodic behavior over large intervals (see illustrations in Links section).

This sequence is unbounded:

- let b(k) = a(0) XOR ... XOR a(k),

- if the sequence was bounded with greatest value m,

- then the sequence b would be bounded by m*(m+1)/2,

- and some value in b, say v, would appear infinitely many times,

- so we can find occurrences of v in b at distance m' > m,

say b(k) = b(k + m') = v,

- so a(k+1) XOR a(k+2) XOR ... XOR a(k+m') = 0,

- and a(k+1) XOR a(k+2) XOR ... XOR a(k+m'+1) = a(k+m'+1),

and a(k+m'+2) >= m' > m, a contradiction.

Examples

			The first terms, alongside an appropriate pair (i,j), are:
  n   a(n)  (i,j)
  --  ----  -------
   0     0  N/A
   1     1  (0,0)
   2     2  (0,1)
   3     1  (2,2)
   4     2  (0,1)
   5     4  (0,3)
   6     6  (0,5)
   7     2  (4,5)
   8     7  (0,6)
   9     9  (0,8)
  10     1  (9,9)
  11     6  (2,7)
  12     7  (2,8)
		

Links

• Rémy Sigrist, Table of n, a(n) for n = 0..10000
• Thomas Scheuerle, log_2(abs(first differences of a(0...2000)))
• Thomas Scheuerle, a(0...2000) colored by the sign of the first differences
• Rémy Sigrist, C program
• Rémy Sigrist, Scatterplot of the first 1000000 terms (numbers correspond to "local" periods)

Crossrefs

Cf. A358799, A358919.

Programs

C

See Links section.

MATLAB

function a = A358918( max_n )
    a = 0; xr = 0;
    for n = 2:max_n
        r = 0;
        xr(n) = bitxor(xr(n-1),a(end));
        f = find(xr==a(end),1,'last');
        if ~isempty(f)
            r = f-1;
        end
        x = xr(2:end);
        for k = length(a)-1:-1:1
            x(1:k) = bitxor(x(1:k),ones(1,k)*a(length(a)-k));
            x(1:k) = bitxor(x(1:k),a([1:k]+(length(a)-k)));
            f = find(x==a(end),1,'last');
            if ~isempty(f)
                if r < f
                    r = f;
                end
            end
        end
        a(n) = r;
    end
end % Thomas Scheuerle, Dec 08 2022