cp's OEIS Frontend

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

%I A358918 #20 Dec 12 2022 15:00:16
%S A358918 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,
%T A358918 26,18,20,28,30,26,22,28,30,30,32,3,28,30,32,3,28,38,40,22,34,46,26,
%U A358918 41,31,45,42,40,37,41,31,58,60,53,54,57,57,57,57,57,57,57
%N 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).
%C A358918 The sequence has periodic behavior over large intervals (see illustrations in Links section).
%C A358918 This sequence is unbounded:
%C A358918 - let b(k) = a(0) XOR ... XOR a(k),
%C A358918 - if the sequence was bounded with greatest value m,
%C A358918 - then the sequence b would be bounded by m*(m+1)/2,
%C A358918 - and some value in b, say v, would appear infinitely many times,
%C A358918 - so we can find occurrences of v in b at distance m' > m,
%C A358918   say b(k) = b(k + m') = v,
%C A358918 - so a(k+1) XOR a(k+2) XOR ... XOR a(k+m') = 0,
%C A358918 - and a(k+1) XOR a(k+2) XOR ... XOR a(k+m'+1) = a(k+m'+1),
%C A358918   and a(k+m'+2) >= m' > m, a contradiction.
%H A358918 Rémy Sigrist, <a href="/A358918/b358918.txt">Table of n, a(n) for n = 0..10000</a>
%H A358918 Thomas Scheuerle, <a href="/A358918/a358918.png">log_2(abs(first differences of a(0...2000)))</a>
%H A358918 Thomas Scheuerle, <a href="/A358918/a358918_1.png">a(0...2000) colored by the sign of the first differences</a>
%H A358918 Rémy Sigrist, <a href="/A358918/a358918.txt">C program</a>
%H A358918 Rémy Sigrist, <a href="/A358918/a358918_2.png">Scatterplot of the first 1000000 terms</a> (numbers correspond to "local" periods)
%e A358918 The first terms, alongside an appropriate pair (i,j), are:
%e A358918   n   a(n)  (i,j)
%e A358918   --  ----  -------
%e A358918    0     0  N/A
%e A358918    1     1  (0,0)
%e A358918    2     2  (0,1)
%e A358918    3     1  (2,2)
%e A358918    4     2  (0,1)
%e A358918    5     4  (0,3)
%e A358918    6     6  (0,5)
%e A358918    7     2  (4,5)
%e A358918    8     7  (0,6)
%e A358918    9     9  (0,8)
%e A358918   10     1  (9,9)
%e A358918   11     6  (2,7)
%e A358918   12     7  (2,8)
%o A358918 (C) See Links section.
%o A358918 (MATLAB)function a = A358918( max_n )
%o A358918     a = 0; xr = 0;
%o A358918     for n = 2:max_n
%o A358918         r = 0;
%o A358918         xr(n) = bitxor(xr(n-1),a(end));
%o A358918         f = find(xr==a(end),1,'last');
%o A358918         if ~isempty(f)
%o A358918             r = f-1;
%o A358918         end
%o A358918         x = xr(2:end);
%o A358918         for k = length(a)-1:-1:1
%o A358918             x(1:k) = bitxor(x(1:k),ones(1,k)*a(length(a)-k));
%o A358918             x(1:k) = bitxor(x(1:k),a([1:k]+(length(a)-k)));
%o A358918             f = find(x==a(end),1,'last');
%o A358918             if ~isempty(f)
%o A358918                 if r < f
%o A358918                     r = f;
%o A358918                 end
%o A358918             end
%o A358918         end
%o A358918         a(n) = r;
%o A358918     end
%o A358918 end % _Thomas Scheuerle_, Dec 08 2022
%Y A358918 Cf. A358799, A358919.
%K A358918 nonn,base
%O A358918 0,3
%A A358918 _Rémy Sigrist_, Dec 06 2022