login
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.
3

%I #69 Oct 31 2022 05:54:50

%S 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,

%T 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,

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

%N 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.

%C 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.

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

%C 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.

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

%C n=1 0, ...

%C n=2 0,1, ...

%C n=3 0,1, ...

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

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

%C 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,...

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

%C n=1 0,

%C n=2 2,0,

%C n=3 0,1,2,0, 2,0,

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

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

%C 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,

%C 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.

%C Maximum values for each block are given by A338205.

%C 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):

%C 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) }.

%C 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.

%C 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):

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

%C _Kevin Ryde_ suggested to me:

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

%C 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, ...

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

%H Thomas Scheuerle, <a href="/A338203/a338203.txt">Shows values for up to 2^8 formated to visualize patterns</a>

%e Triangle begins:

%e 0;

%e 0, 0;

%e 0, 1, 2, 0;

%e 0, 1, 0, 1, 2, 0, 2, 0;

%e 0, 1, 3, 2, 4, 4, 0, 1, 2, 0, 5, 3, 1, 4, 2, 0;

%e ...

%e n=4: Four-bit wordlength. k=5 in binary: 0101

%e 0101 - 1010 = 1011 (2^4 + 5 - 10) Iteration 1

%e 1011 - 1101 = 1110 (2^4 + 11 - 13) Iteration 2

%e 1110 - 0111 = 0111 (14 - 7) Iteration 3

%e 0111 - 1110 = 1001 (2^4 + 7 - 14) Iteration 4

%e a((2^n -1)+k) = 4.

%e a(1+2+4+8 +5) = 4.

%e 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):

%e 1110 - 0111 = 0111 (14 - 7) Iteration 1

%e 0111 - 1110 = 1001 (2^4 + 7 - 14) Iteration 2

%e 110 - 011 = 011 (6 - 3) Iteration 1

%e 011 - 110 = 101 (2^3 + 3 - 6) Iteration 2

%o (MATLAB)

%o sequence = [];

%o for numberofBits = 1: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 = [sequence iterations_list];

%o end

%o (PARI)

%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} \\ _Andrew Howroyd_, Oct 17 2020

%Y Cf. A338205 (max row values).

%K nonn,tabf,base

%O 0,6

%A _Thomas Scheuerle_, Oct 16 2020