A338203 Triangle read by rows: T(n,k) is the number of iterations needed to make the n-bit binary representation of k palindromic by binary-subtracting its bit reversal, 0 <= k < 2^n.

0, 0, 0, 0, 1, 2, 0, 0, 1, 0, 1, 2, 0, 2, 0, 0, 1, 3, 2, 4, 4, 0, 1, 2, 0, 5, 3, 1, 4, 2, 0, 0, 1, 3, 2, 0, 1, 3, 2, 4, 4, 0, 1, 4, 4, 0, 1, 2, 0, 5, 3, 2, 0, 5, 3, 1, 4, 2, 0, 1, 4, 2, 0, 0, 1, 3, 2, 2, 5, 6, 3, 3, 3, 5, 6, 0, 1, 3, 2, 4, 4, 0, 1, 6, 6, 2, 5, 1, 1

Offset

0,6

Comments

All operations are performed with n bits. In particular, the bit-reversal of k considers k as an n-bit binary word and k is a palindrome if it is equal to its bit reversal in this sense. The subtraction is performed modulo 2^n.

The sequence is divided into blocks of length 2^n, n = 1, 2, 3, ...

There are interesting structures visible if you write each block of the sequence in a new line. Then it becomes visible that each block contains its previous block interrupted by new parts.

Left part of table (k from 0 to ...):

n=1 0, ...

n=2 0,1, ...

n=3 0,1, ...

n=4 0,1, 3,2,4,4, ...

n=5 0,1,3,2, 0,1,3,2,4,4,0,1, 4,4,...

n=6 0,1,3,2,2,5,6,3,3,3,5,6,0,1,3,2,4,4,0,1,6,6,2,5,1,1,3,3,4,4,...

Right part of table (k continued to last element):

n=1 0,

n=2 2,0,

n=3 0,1,2,0, 2,0,

n=4 0,1,2,0, 5,3,1,4, 2,0,

n=5 0,1,2,0,5,3, 2,0,5,3,1,4,2,0, 1,4,2,0,

n=6 0,1,2,0,5,3,4,2,2,6,4,3,7,5,2,0,5,3,1,4,2,0,4,6,4,2,5,1,4,3,1,4,2,0,

There is no formal proof known to the writer that this algorithm never gets stuck in a loop, yet no loop found by computation up to 32 bits.

Maximum values for each block are given by A338205.

For all even n the sequence T(n+1,0..(n+1)^k-1) contains only copied values of the sequence for T(n,0..n^k-1):

n = 2m, T(n+1,0..2^(n+1)) = {T(n,0..2^m-1),T(n,0..2^m-1),T(n,2^m..2*2^m-1),T(n,2^m..2*2^m-1),...,T(n,2^n-2^m..2^n-1),T(n,2^n-2^m..2^n-1) }.

This happens because removing the middle bit in any bitsequence k, taken from a row with odd n, does not change its number of iterations.

For all odd n some parts of sequence T(n+1,0..(n+1)^k-1) are already contained in sequence T(n,0..n^k-1):

n = 2m, m > 0, [k/(2^m)] + [k/(2^(m+1))] is even (inner pair of bits is equal, e.g., ...00...), T(n,k) = T(n-1,[k/(2^m)]*2^(m-1) + k mod (2^(m-1)) ).

Kevin Ryde suggested to me:

"Should be approaching an argument for why no cycles, as it must be hard to avoid 2-equal-bits middle for very long ..."

To verify this, a calculation for all even k up to 20. This is the maximum number of iterations until middle bits become equal for row k: 2, 3, 6, 9, 11, 13, 16, 18, 23, 26, ...

It appears to be well behaved. Probably < 2^(k-2) for all n > 2.

Links

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

Thomas Scheuerle, Shows values for up to 2^8 formated to visualize patterns

Example

Triangle begins:
  0;
  0, 0;
  0, 1, 2, 0;
  0, 1, 0, 1, 2, 0, 2, 0;
  0, 1, 3, 2, 4, 4, 0, 1, 2, 0, 5, 3, 1, 4, 2, 0;
  ...
n=4: Four-bit wordlength. k=5 in binary: 0101
  0101 - 1010 = 1011 (2^4 + 5 - 10)   Iteration 1
  1011 - 1101 = 1110 (2^4 + 11 - 13)  Iteration 2
  1110 - 0111 = 0111 (14 - 7)         Iteration 3
  0111 - 1110 = 1001 (2^4 + 7 - 14)   Iteration 4
a((2^n -1)+k) = 4.
a(1+2+4+8 +5) = 4.
Below is an example in which two equal inner bits lead to same number of iterations as in the case of a one-bit-smaller word (one of the inner bits removed):
  1110 - 0111 = 0111 (14 - 7)         Iteration 1
  0111 - 1110 = 1001 (2^4 + 7 - 14)   Iteration 2
   110 -  011 = 011 (6 - 3)           Iteration 1
   011 -  110 = 101 (2^3 + 3 - 6)     Iteration 2

Prog

(MATLAB)
sequence = [];
for numberofBits = 1: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 = [sequence iterations_list];
end
(PARI)
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} \\ Andrew Howroyd, Oct 17 2020

Crossrefs

Cf. A338205 (max row values).

Sequence in context: A001878 A056558 A320808 * A324930 A179519 A091979

Adjacent sequences: A338200 A338201 A338202 * A338204 A338205 A338206

Keyword

nonn,tabf,base

Author

Thomas Scheuerle, Oct 16 2020

Status

approved