A339602 a(n) = (a(n-2) XOR A030101(a(n-1))) + 1, a(0) = 0, a(1) = 1.

0, 1, 2, 1, 4, 1, 6, 3, 6, 1, 8, 1, 10, 5, 16, 5, 22, 9, 32, 9, 42, 29, 62, 3, 62, 29, 42, 9, 36, 1, 38, 25, 54, 3, 54, 25, 38, 1, 40, 5, 46, 25, 62, 7, 58, 17, 44, 29, 60, 19, 38, 11, 44, 7, 44, 11, 34, 27, 58, 13, 50, 31, 46, 3, 46, 31, 50, 13, 58, 27, 34

Offset: 0

Author

Thomas Scheuerle, Dec 09 2020

Keywords

• nonn
• base
• look

Comments

Is this sequence periodic? The related sequence A114375 was found to be nonperiodic, however the same argument does not hold here as the bitreversal operation used here maps different values onto the same. E.g. 111000 -> 111 111 -> 111. Every time this sequence develops a not yet seen value a(n) = 2^m, the space of combinations increases from (2^(m-1))^2 to (2^m)^2 reducing the probability to hit an already seen pair of values for [a(n-2),a(n-1)].

This sequence contains some palindromic parts. Example a(55)..a(72): 11, 34, 27, 58, 13, 50, 31, 46, 3, 46, 31, 50, 13, 58, 27, 34, 11.

a(n) <> a(n-1). a(2k) = 2m. a(2k+1) = 2m+1.

a(n) = 2^k, k > 0 for each k will exist only once in this sequence, if it is never periodic. In this case the 2^k will be in increasing sequence ordered.

Conjecture: Let p be an odd number, then a(n) = p will be more frequently found in this sequence than a(n) = p+1 (tested for n = 0..10^7 with primes > 2, but seems to be true for all odd too).

Examples

			a(5) = 1 binary: 1; a(6) = 6 binary: 110, binary bitreversed: 11;
so a(7) = binary: (001 XOR 11)+1 = 11 decimal: 3.
		

Links

• Robert Israel, Table of n, a(n) for n = 0..10000
• Thomas Scheuerle, Interesting staircase pattern in this sequence.

Crossrefs

Cf. A030101, A114375.

Programs

MATLAB

function a = calc_A339602(length)
    % a(0) = 0  not in output of program
    a(1) = 1; % part of definition
    an_2 = 0; % a(0)
    an_1 = a(1);
    for n = 2:length
        an_1_old = an_1;
        an_1 = bitxor(an_2,bitreverse(an_1))+1;
        an_2 = an_1_old;
        a(n) = an_1;
    end
end
function r = bitreverse(k) % A030101(k)
    r = 0;
    m = floor(log2(k))+1;
    for i = 1:m
        r = bitset(r,m-i+1,bitget(k,i));
    end
end

Maple

bitrev:= proc(n) local L,i;
  L:= convert(n,base,2);
  add(L[-i]*2^(i-1),i=1..nops(L))
end proc:
A:= Array(0..100):
A[0]:= 0: A[1]:= 1:
for n from 2 to 100 do
  A[n]:= Bits:-Xor(A[n-2],bitrev(A[n-1]))+1
od:
seq(A[i],i=0..100); # Robert Israel, Dec 25 2020

Mathematica

f[n_] := FromDigits[Reverse @ IntegerDigits[n, 2], 2]; a[0] = 0; a[1] = 1; a[n_] := a[n] = BitXor[a[n - 2], f[a[n - 1]]] + 1; Array[a, 100, 0] (* Amiram Eldar, Dec 10 2020 *)

PARI

f(n) = fromdigits(Vecrev(binary(n)), 2); \\ A030101
lista(nn) = {my(x=0, y=1); print1(x, ", ", y, ", "); for (n=2, nn, z = bitxor(x, f(y)) +1; print1(z, ", "); x = y; y = z;);} \\ Michel Marcus, Dec 10 2020