meditationatae

Just another WordPress.com site

The b-numbers again

If we write the (hypothetical, from now on understood) sequence from TM #4 (chaotic), 5-state, 2-symbol tape of Marxen and Buntrock in rows of 8, the 3rd column has a complex structure.

Suppose we use “index 1”-notation, which just means that the first term of the sequence, 3, is written s(1) instead of s(0) as would be the case with arrays in C, C++, and so on.

Then the third column is made up of s(3) = 5, s(11), s(19), and in general s(8j + 3) for some integer j with 0<= j < oo.

Empirically,  s(j) <= j+2. When j is congruent to 3 modulo 8, so that s(j) is a third-column term, it happens that:

s(j) = j+2 exactly.

When this happens, in column 3, I call j+2 a b-number (basic number). Or in other words, if k is such that s(k-2) = k, and

k == 5 (mod 3), and of course k >2, then by definition k is a basic number or b-number.

When k == 5 (mod 3), but s(k-2) is not k, then I’ve called k a forbidden number. This is justified by studying the binary expansion of s(k-2)  when k is a forbidden number.

Empirical study gives some credence to the belief that, when k is not a b-number, s(k-2) can be obtained from ‘k’ by omitting one or more of the most significant bits of k, all consecutive bits, while always leaving perhaps 3 bits of ‘k’ to yield 101_(Base 2) = 5_(Base 10).

Moreover, a first look gave me a clue that when k is forbidden, then s(k-2) can be obtained from the binary expansion of k by omitting the most significant ‘1’ bit from k in base 2, and going on striking-out mentally the most significant ‘1’ bits (starting at the leftmost bit) and stopping when and only when the modified number is a b-number. Thus, if k is forbidden, s(k-2) would still be a b-number or basic number.

The new feature I hadn’t looked at previously is the count of b-numbers by bit-length.

The following table has this , with a coming explanation:

n count(n)
======================
10 22
11 32
12 48
13 71
14 106
15 158
16 234
17 348
18 518
19 772
20 1152

n is a bit-length of a positive integer.
Examples: 6 has bit-length 3, 2^k has
bit length k+1, 100 has bit-length 7,
ans 2^k – 1 has bit-length k.

count(n) is the number of b-numbers with bit-length equal to n.
So there are 22 b-numbers with 10 bits, which means in the
range 512 to 1023 inclusive. And so on up to 20 bits.

You’ll see that c(n+1) is approximately (3/2)*c(n),
better than chance in my opinion.

In other words, while there are 48 b-numbers
in the range 2048 to 4095, there are only
23 in the range 4096 to 8191 (which is
twice as long).
To if we increase n by +1, the frequency of
b-numbers is reduced by a factor of 4 approximately.

Perhaps these correspond to two extra “pseudo-random”
boolean 0/1 conditions for a 13-bit b-number, as
compared to a 12-bit b-number. This line of
inquiry has not so far been pursued further.

If you look at the first few dozen b-numbers,
you might notice that 2^k – 3 is a b-number
for k = 3, 4, 5, 6, 7, … 15, …
There are other “magic numbers” like 3.
While consistent, these “magic numbers”
and their patterns still give complicated
sequences.

Perhaps I missed something that could be guessed
from the fact that c(n+1) is approximately (3/2)*c(n).

I find this problem of pattern recognition both
tantalizing and frustrating, because it is
produced by such a seemingly simple 5-state,
2-symbol Turing machine, starting with a
blank tape.

The first 100 b-numbers :

5
13
21
29
37
45
53
61
77
85
93
101
109
117
125
149
173
181
189
205
213
221
229
237
245
253
309
341
365
373
381
405
429
437
445
461
469
477
485
493
501
509
629
693
725
749
757
765
821
853
877
885
893
917
941
949
957
973
981
989
997
1005
1013
1021
1205
1237
1261
1277
1397
1461
1493
1517
1525
1533
1653
1717
1749
1773
1781
1789
1845
1877
1901
1909
1917
1941
1965
1973
1981
1997
2005
2013
2021
2029
2037
2045
2229
2285
2485
2517

 

 

Advertisements

Written by meditationatae

September 23, 2017 at 7:01 am

Posted in History

One Response

Subscribe to comments with RSS.


Comments are closed.

%d bloggers like this: