A358799 -id:A358799 - cp's OEIS frontend

A358919 a(0) = 0, and for any n >= 0, a(n+1) is the sum of the lengths of the runs of consecutive terms a(i), ..., a(j) with 0 <= i <= j <= n such that a(i) XOR ... XOR a(j) = a(n) (where XOR denotes the bitwise XOR operator).

0, 1, 3, 1, 4, 1, 5, 5, 10, 4, 12, 18, 1, 13, 8, 22, 44, 7, 52, 1, 19, 35, 10, 43, 53, 7, 68, 1, 31, 24, 56, 73, 8, 126, 105, 35, 71, 36, 71, 60, 70, 1, 124, 180, 10, 172, 41, 182, 40, 288, 1, 232, 15, 201, 4, 271, 6, 213, 1, 233, 14, 230, 25, 216, 9, 157, 115

Offset: 0

Rémy Sigrist, Dec 06 2022

The sequence is unbounded (if the sequence was bounded, with greatest value m, then, by the pigeonhole principle, some value, say v, would appear infinitely many times, and the next value after the (m+1)-th occurrence of v would be > m, a contradiction).

			The first terms, alongside the corresponding pairs (i,j), are:
  n   a(n)  (i,j)'s
  --  ----  ---------------------------------
   0     0  N/A
   1     1  (0,0)
   2     3  (0,1), (1,1)
   3     1  (2,2)
   4     4  (0,1), (1,1), (3,3)
   5     1  (4,4)
   6     5  (0,1), (1,1), (3,3), (5,5)
   7     5  (3,4), (4,5), (6,6)
   8    10  (3,4), (4,5), (4,7), (6,6), (7,7)
   9     4  (6,8), (8,8)
  10    12  (3,5), (3,7), (4,4), (5,6), (9,9)
  11    18  (0,8), (1,8), (10,10)
  12     1  (11,11)

Rémy Sigrist, Table of n, a(n) for n = 0..15722
Rémy Sigrist, C program
Rémy Sigrist, Scatterplot of the first 350000 terms

Cf. A358799, A358918.

C
```
See Links section.
```

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

Original entry on oeis.org

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

Rémy Sigrist, Dec 06 2022

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.

			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)

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)

Cf. A358799, A358919.

C
```
See Links section.
```

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

cp's OEIS Frontend

A358919 a(0) = 0, and for any n >= 0, a(n+1) is the sum of the lengths of the runs of consecutive terms a(i), ..., a(j) with 0 <= i <= j <= n such that a(i) XOR ... XOR a(j) = a(n) (where XOR denotes the bitwise XOR operator).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

C