login
a(n) the maximum number of iterations needed to make the binary representation of a 2n-bit number palindromic by subtracting its bit reversal.
1

%I #39 May 08 2021 08:33:44

%S 0,2,5,7,14,16,18,27,31,33,41,46,50,57,61,70

%N a(n) the maximum number of iterations needed to make the binary representation of a 2n-bit number palindromic by subtracting its bit reversal.

%C a(n) is the maximum value in row 2n of A338203.

%C It appears that this is also the maximum value in row 2n+1.

%e n=1 two bit wordlength.

%e 00 already palindromic -> 0 iterations,

%e 01 - 10 = 11 -> 1 iteration,

%e 10 - 01 = 01,

%e 01 - 10 = 11 -> 2 iterations,

%e 11 already palindromic -> 0 iterations.

%e We have a maximum of 2 iterations here thus a(1)=2.

%o (MATLAB)

%o sequence(1) = 0; % value for null bits

%o for numberofBits = 1:2:maxNumberofBits

%o numbersPerWordlength = 2^numberofBits;

%o for n = 1:numbersPerWordlength

%o iterations = 0;

%o word = n-1;

%o while word > 0

%o word_reversed = 0;

%o % reverse bit order

%o for i = 1:numberofBits

%o word_reversed = bitset(word_reversed,numberofBits-i+1,bitget(word,i));

%o end

%o % binary subtraction with worlength of numbersPerWordlength

%o if word >= word_reversed

%o word = word-word_reversed;

%o else

%o word = numbersPerWordlength + word - word_reversed;

%o end

%o if word > 0 % if == 0 it was already a palindrome

%o iterations = iterations+1;

%o end

%o end

%o iterations_list(n) = iterations;

%o end

%o sequence(numberofBits+1) = max(iterations_list);

%o end

%o (PARI) \\ here T(n,k) gives A338203(n,k).

%o bitrev(w,b)={my(r=0); for(i=1, w, r=(r<<1) + bitand(b,1); b>>=1); r}

%o T(n,b) = {my(t=0, r=bitrev(n,b)); while(r<>b, t++; b-=r; if(b<0, b+=2^n); r=bitrev(n,b)); t}

%o a(n) = {my(r=0); for(b=0, 4^n-1, r=max(r, T(2*n,b))); r} \\ _Andrew Howroyd_, Oct 16 2020

%Y Cf. A338203.

%K nonn,base,more

%O 0,2

%A _Thomas Scheuerle_, Oct 16 2020

%E a(14)-a(15) from _Michael S. Branicky_, Dec 08 2020