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

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

Offset

0,2

Comments

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

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

Links

Table of n, a(n) for n=0..15.

Example

n=1 two bit wordlength.
00 already palindromic -> 0 iterations,
01 - 10 = 11 -> 1 iteration,
10 - 01 = 01,
01 - 10 = 11 -> 2 iterations,
11 already palindromic -> 0 iterations.
We have a maximum of 2 iterations here thus a(1)=2.

Prog

(MATLAB)
  sequence(1) = 0; % value for null bits
for numberofBits = 1:2:maxNumberofBits
    numbersPerWordlength = 2^numberofBits;
    for n = 1:numbersPerWordlength
        iterations = 0;
        word = n-1;
        while word > 0
            word_reversed = 0;
            % reverse bit order
            for i = 1:numberofBits
                word_reversed = bitset(word_reversed, numberofBits-i+1, bitget(word, i));
            end
            % binary subtraction with worlength of numbersPerWordlength
            if word >= word_reversed
              word = word-word_reversed;
            else
              word = numbersPerWordlength + word - word_reversed;
            end
            if word > 0 % if == 0 it was already a palindrome
              iterations = iterations+1;
            end
        end
        iterations_list(n) = iterations;
    end
    sequence(numberofBits+1) = max(iterations_list);
end
(PARI) \\ here T(n, k) gives A338203(n, k).
bitrev(w, b)={my(r=0); for(i=1, w, r=(r<<1) + bitand(b, 1); b>>=1); r}
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}
a(n) = {my(r=0); for(b=0, 4^n-1, r=max(r, T(2*n, b))); r} \\ Andrew Howroyd, Oct 16 2020

Crossrefs

Cf. A338203.

Sequence in context: A305993 A193718 A007438 * A230301 A031457 A044990

Adjacent sequences: A338202 A338203 A338204 * A338206 A338207 A338208

Keyword

nonn,base,more

Author

Thomas Scheuerle, Oct 16 2020

Extensions

a(14)-a(15) from Michael S. Branicky, Dec 08 2020

Status

approved